22. 微软面试题：左旋字符串

题目：

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。

例如把字符串"abcdef" 左旋2位 得到字符串“cdefab"。请实现字符串左旋转的函数。

要求时间对长度n的字符串操作的复杂度位O(n)，辅助内存为O(1).

分析：

这题的难点是辅助内存只能只用O(1)，相当于只能进行字符串中字符的替换操作，如果需要移动字符串，则需要m*n次替换操作，这样复杂度也上来了，O(n*n).

只能想技巧了。

实现如下：

#include
   
    
#include
    
      using namespace std; void reverse(char* str, int i, int j) { while( i < j) { char chr = str[i]; str[i] = str[j]; str[j] = chr; i ++; j --; } } void leftRotate(char* srcstr, int k) { int len = strlen(srcstr); if(len <= 1) return; k = k%len; reverse(srcstr, 0, k - 1); reverse(srcstr, k, len -1); reverse(srcstr, 0, len -1); } int main() { char str[] = "abcdef"; cout << "string: " << str << endl; leftRotate(str, 2); cout << "rotate string, 2: " << str << endl; return 0; }
    
   

输出结果如下：

string: abcdef
rotate string, 2: cdefab