题目
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
若把字符串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; }
rotate算法
上述思想在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; }
