26.左旋转字符串（字符串）

题目：

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

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

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

 

思路：

设字符串为 abcdefg 要左旋两个， $$表示操作范围，|表示要旋转的轴线，将操作范围分为两个部分。每次把范围小的部分与范围大的部分的靠近|的位置交换。范围相同则直接交换。

1. $ab|cdefg$

      2     5

2. cd$ab|efg$

          2    3

3. cdef&ab|g&

             2 1

4. cdef&a|g&b

           1   1

5. cdefgab       完成。

代码用的递归实现。但是我不知道我用了循环中的int i和一些辅助的变量。是不是不符合辅助空间O(1)的要求了？

#include 
     
      #include 
      
       void swap(char * c1, char * c2){    char c = *c1;    *c1 = *c2;    *c2 = c;}void exchange(char * s1, char * s2, int n){    for(int i = 0; i < n; i++)    {        swap(s1,s2);        s1++;        s2++;    }}void rotate(char * in, int n, int len){    n = n % len; //判断左旋字符数是否超过字符串长度    int l = n, r = len - l;    if(l < r)    {        len -= l;        exchange(in, in + l, l);        rotate(in + l, l, len);    }    else if(l > r)    {        exchange(in + len - r, in + len - 2 * r, r);        len -= r;        rotate(in, len - r, len);    }    else    {        exchange(in, in + l, l);    }}void leftrotate(char * in, int n){    rotate(in, n, strlen(in));}int main(){    char s[] = "abcdefghi";    leftrotate(s, 10);    return 0;}
      
     

 

网上有个很巧妙的思路：

分析：如果将字符串分为AB两部分，其中A表示要移动到字符串尾部的字符串，B表示剩余部分，我们先分别将A和B逆置，然后再将字符串作为一个整体来逆置，这样起到的效果是第一步先得到ATBT，然后得到（ATBT）T，即BA。

 

网上有STL的讲解，还没看