定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
若把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(1);
类似题目还有剑指Offer.58题
本题与2.17数组循环移位相似，这里我们用同样的方法。如果不理解，请看2.17数组循环移位。
C
#include<stdio.h>
#include<string.h>
void swap(char* arr, int front, int later)//交换函数
{
char tmp = arr[front];
arr[front] = arr[later];
arr[later] = tmp;
}
void Reverse(char* arr, int start, int end)//反转函数 范围[start, end);
{
int i = 0;
for(i = start; i < (start + end) >> 1; i++)
{
swap(arr, i, end - 1 - (i - start));
}
}
char* LeftString(char* arr, int pos)//左旋转字符串
{
int len = strlen(arr);
pos = len - pos % len;//左转pos次相当于右转len-pos次
Reverse(arr, 0, len);
Reverse(arr, 0, pos);
Reverse(arr, pos, len);
return arr;
}
int main()
{
char arr[] = "abcdef";
int pos = 2;
LeftString(arr, pos);
printf("%s\n", arr);
return 0;
}
我们用俩个指针，前指针指向开头，后指针指向旋转的位数。具体操作看图
子字符串“cab”尾巴我们又分为三种情况。
1、abc。提前完成任务，这种情况是字符串的长度刚好是左移次数的倍数。如：abcdef，pos=3;
2、cab。这种情况是len%pos = 2。如abcdefgh,pos=3; 向右交换一轮
3、bca。这种情况是len%pos = 1。如abcdefg,pos=3;向右交换俩轮
发现 交换次数=pos-len%pos
具体实现如下
C
#include<stdio.h>
#include<string.h>
#include<assert.h>
void swap(char* arr, int front, int later)//交换函数
{
char tmp = arr[front];
arr[front] = arr[later];
arr[later] = tmp;
}
char* LeftString(char* arr, int pos)//左旋转字符串
{
assert(arr != NULL);
assert(pos > 0);
int len = strlen(arr);
pos = pos % len;
int cycle = (len - pos);//第一轮交换的次数
int front = 0;//前指针
int later = pos;//后指针
//第一轮先交换到底
while (cycle != 0)
{
swap(arr, front, later);
front++;
later++;
cycle--;
}
cycle = pos - len % pos;//余数为0情况一，其他情况通通右移
while (cycle != 0)
{
int i = 0;
for (i = 0; i < pos - 1; i++)
{
swap(arr, front + i, front + i + 1);
}
cycle--;
front++;
}
return arr;
}
int main()
{
char arr[] = "abcdefgh";
int pos = 3;
LeftString(arr, pos);
printf("%s\n", arr);
return 0;
}
双指针+交换2
上面是指针一次走到底。然后再把尾巴复原。
这次我们这交换pos的整数倍的字符，剩余的单独处理。图示如下
第一轮的交换代码没有任何变化，只有循环次数有变。循环次数就是字符串总长度减去pos剩余的长度且还是pos的整数倍。cycle = (len - pos) / pos * pos;
我们来分析这次的尾巴。abcgh
因为剩余长度范围为[0,pos-1]。长度不是很大，我们可以选择一步一步的移动也可以在再来一次字符串旋转（len=5，pos=3）。这里我选取的是一步一步的移动（g、h分别依次向左移动）。
C
#include<stdio.h>
#include<string.h>
#include<assert.h>
void swap(char* arr, int front, int later)//交换函数
{
char tmp = arr[front];
arr[front] = arr[later];
arr[later] = tmp;
}
char* LeftString(char* arr, int pos)//左旋转字符串
{
assert(arr != NULL);
assert(pos > 0);
int len = strlen(arr);
pos = pos % len;
int cycle = (len - pos) / pos * pos;//第一轮交换的次数
int front = 0;//前指针
int later = pos;//后指针
//第一轮先交换到底
while (cycle != 0)
{
swap(arr, front, later);
front++;
later++;
cycle--;
}
cycle = len % pos;//余数为0情况一，其他情况通通右移
while (cycle != 0)
{
int i = later;
while (i > front)
{
swap(arr, i, i - 1);
i--;
}
cycle--;
later++;
}
return arr;
}
int main()
{
char arr[] = "abcdefgh";
int pos = 3;
LeftString(arr, pos);
printf("%s\n", arr);
return 0;
}
上述思想在C++中有一个相似的算法STL::rotate这里我引用程序员编程艺术书中代码，有改动。
核心：对字符串长度和旋转长度的最大公约数。作为循环次数。然后每次循环里面先把第一个元素保存下来，然后以旋转长度为单位跳着赋值。如下图
C++
#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int m, int n)
{
int r = m % n;
while (r != 0)
{
m = n;
n = r;
r = m % n;
}
return n;
}
//这里的mid相当于pos，范围是[begin,end)
void my_rotate(char* arr,int begin, int mid, int end)
{
int len = end - begin;
int k = mid - begin;
//gcd最大公约数函数是GUN编译器自带的，这里我自己实现
int d = gcd(len, k);
int i = 0;
int j = 0;
for (i = 0; i < d; i++)
{
int tmp = arr[i];
int last = i;
for (j = (i + k) % len; j != i; j = (j + k) % len)
{
arr[last] = arr[j];
last = j;
}
arr[last] = tmp;
}
}
int main()
{
string str = "abcdefgh";
int pos = 3;
my_rotate((char*)str.c_str(), 0, pos, str.length());
cout << str.c_str() << endl;
return 0;
}