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个步骤操作即可：
- 首先分为俩部分，X:ab，Y:cd；
- 将X反转，即得：ab->ba；将Y反转，即得：cd->dc。
- 反转上述得到的结果字符串，即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);
}
