左旋字符串

Details:

把字符串前面的若干个字符移动到字符串尾部，例如把 abcd 左旋转 2 位得到字符串 cdba。要求时间复杂度为 O(n)，空间复杂度为 O(1)。

solution 1：step by step

void left_shift_one(char* a,int n)
{
     assert(a !=NULL);
     char m=a[0];//保存第一个字符
     for(int i=0;i<n;i++)
     {
         a[i]=a[i++];
     }
     a[n-1]=m;
}

然后向左移动k次即可

void left_shift(char*a,int n,int k){
     while(k--)
     {
        left_shift_one(a,n);
     }
}

solution 2：三步反转法

//此解法可见与《编程珠玑》
例如字符串 abcd ，若要让cd翻转到ab的前头，只要按下述3个步骤操作即可：

1. 首先分为俩部分，X:ab，Y:cd；
2. 将X反转，即得：ab->ba；将Y反转，即得：cd->dc。
3. 反转上述得到的结果字符串，即badc给予反转，得cdab。

void reverse(char *a,int start,int end)
{
  while(end>start)
  {
    char t=a[start];
    a[start++]=a[end];
    a[end--]=t;
  }
}
void left_shift(char *a,int n,int m)
{
  int k=m%n;//考虑移位超过n的情况
  reverse(a,0,k-1);
  reverse(a,k,n-1);
  reverse(a,0,n-1);
}