字符串算法之字符串循环左移

问题描述：给定一个字符串S[0...N-1],要求把S的前k个字符移到S的尾部，如把S的字符串“abcded"前面的前两个字符“a”,“b”移到字符串的尾部，得到新字符串“cdefab”，即字符串循环左移k位

算法要求：时间复杂度为O（n）,空间复杂度为O(1);

暴力移位法：

暴力移位每次移动一位，移动K次即可；

时间复杂度为O(KN),空间复杂度为O(1);

三次拷贝：

即建立一个数组，分三次拷贝

时间复杂度为O(N),空间复杂度为O(K)

翻转算法：

类似于矩阵转置，设X="ab", Y="cdef "

X " = "ba",

Y " = " fedc " ,

( X " Y " ) " = " cdefab " ;

算法实现代码：

void reverseString(char *s, int from , int to)
{
    while(from<to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}
void leftRotateString(char*s, int n, int m)
{
    m %= n;
    reverseString(s,0,m-1);
    reverseString(s,m,n-1);
    reverseString(s,0,n-1);
}