字符串移动

题目要求，就是把字符串循环移位，这个是比较常见的面试题了，要时间复杂度O(n)，空间复杂度O(1)。

        这个题是比较常见的面试题了，《编程珠玑》上有，应该还有不少书上也有。

        比如把字符串abcdefgh右循环移位4位，就编程了efghabcd。

       我们可以考虑如下3个步骤：

       先把abcd翻转变为dcba，再把efgh翻转变为hgfe。这样，原来的串变为了dcbahgfe 最后把整个儿翻转变为 efghabcd。

      我们用到的操作只是翻转。于是只需要实现对一个串翻转的函数就好了。

[cpp] view
plaincopy

1. void reverse(char *s,int from,int to) {  
2.     int i,j;  
3.         for (i = from, j = to; i < j; ++i, --j)  {  
4.             char t = s[i];  
5.                     s[i] = s[j];  
6.                     s[j] = t;  
7.         }  
8. }     

        另外还要注意如果循环移动k位的话，相当于循环右移k % n 位，否则k很大的话就不是O(n)时间复杂度了。接下来我们所要做的就是控制好下标，实现3次翻转：     

[cpp] view
plaincopy

1. void shiftRight(char *s,int n,int k) {  
2.     if (k %= n) {  
3.         reverse(s, 0, k - 1);  
4.         reverse(s, k, n - 1);  
5.         reverse(s, 0, n - 1);  
6.     }  
7. }