程序员编程艺术第一章、左旋转字符串

目录

序

前言

第一节、左旋转字符串

第二节、两个指针逐步翻转

第三节、通过递归转换，缩小问题之规模

第四节、stl::rotate 算法的步步深入

第五节、总结

前言
    本人整理微软等公司面试100题系列，包括原题整理，资源上传，帖子维护，答案整理，勘误，修正与优化工作，包括后续全新整理的80道，总计180道面试题，已有半年的时间了。

    关于这180道面试题的一切详情，请参见：横空出世，席卷Csdn [评微软等数据结构+算法面试180题]。

    一直觉得，这180道题中的任何一题都值得自己反复思考，反复研究，不断修正，不断优化。之前的答案整理由于时间仓促，加之受最开始的认识局限，更兼水平有限，所以，这180道面试题的答案，有很多问题都值得进一步商榷与完善。

    特此，想针对这180道面试题，再写一个系列，叫做：程序员编程艺术系列。如你所见，我一般确定要写成一个系列的东西，一般都会永久写下去的。

    “他似风儿一般奔跑，很多人渐渐的停下来了，而只有他一直在飞，一直在飞....”
    
    ok，本次程序员编程艺术系列以之前本人最初整理的微软面试100题中的第26题、左旋转字符串，为开篇，希望就此问题进行彻底而深入的阐述。然以下所有任何代码仅仅只是全部测试正确了而已，还有很多的优化工作要做。欢迎任何人，不吝赐教。谢谢。

第一节、左旋转字符串
题目描述：

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。 

编程之美上有这样一个类似的问题，咱们先来看一下：

设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O（N），
且只允许使用两个附加变量。

分析：

我们先试验简单的办法，可以每次将数组中的元素右移一位，循环K次。
abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。
RightShift(int* arr, int N, int K)
{
     while(K--)
     {
          int t = arr[N - 1];
          for(int i = N - 1; i > 0; i --)
               arr[i] = arr[i - 1];
          arr[0] = t;
     }
}

虽然这个算法可以实现数组的循环右移，但是算法复杂度为O（K * N），不符合题目的要求，要继续探索。

假如数组为abcd1234，循环右移4位的话，我们希望到达的状态是1234abcd。
不妨设K是一个非负的整数，当K为负整数的时候，右移K位，相当于左移（-K）位。
左移和右移在本质上是一样的。

解法一：
大家开始可能会有这样的潜在假设，K<N。事实上，很多时候也的确是这样的。但严格来说，我们不能用这样的“惯性思维”来思考问题。
尤其在编程的时候，全面地考虑问题是很重要的，K可能是一个远大于N的整数，在这个时候，上面的解法是需要改进的。
仔细观察循环右移的特点，不难发现：每个元素右移N位后都会回到自己的位置上。因此，如果K > N，右移K-N之后的数组序列跟右移K位的结果是一样的。

进而可得出一条通用的规律：
右移K位之后的情形，跟右移K’= K % N位之后的情形一样，如代码清单2-34所示。
//代码清单2-34
RightShift(int* arr, int N, int K)
{
     K %= N;
     while(K--)
     {
          int t = arr[N - 1];
          for(int i = N - 1; i > 0; i --)
               arr[i] = arr[i - 1];
          arr[0] = t;
     }
}
可见，增加考虑循环右移的特点之后，算法复杂度降为O（N^２），这跟K无关，与题目的要求又接近了一步。但时间复杂度还不够低，接下来让我们继续挖掘循环右移前后，数组之间的关联。

解法二：
假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。
变换的过程通过以下步骤完成：
 逆序排列abcd：abcd1234 → dcba1234；
 逆序排列1234：dcba1234 → dcba4321；
 全部逆序：dcba4321 → 1234abcd。
伪代码可以参考清单2-35。
//代码清单2-35
Reverse(int* arr, int b, int e)
{
     for(; b < e; b++, e--)
     {
          int temp = arr[e];
          arr[e] = arr[b];
          arr[b] = temp;
     }
}

RightShift(int* arr, int N, int k)
{
     K %= N;
     Reverse(arr, 0, N – K - 1);
     Reverse(arr, N - K, N - 1);
     Reverse(arr, 0, N - 1);
}

这样，我们就可以在线性时间内实现右移操作了。

稍微总结下：
编程之美上，
（限制书中思路的根本原因是，题目要求：“且只允许使用两个附加变量”，去掉这个限制，思路便可如泉喷涌）
1、第一个想法 ，是一个字符一个字符的右移，所以，复杂度为O（N*K）
2、后来，它改进了，通过这条规律：右移K位之后的情形，跟右移K’= K % N位之后的情形一样
复杂度为O（N^2）
3、直到最后，它才提出三次翻转的算法，得到线性复杂度。

下面，你将看到，本章里我们的做法是：
1、三次翻转，直接线性
2、两个指针逐步翻转，线性
3、stl的rotate算法，线性

好的，现在，回到咱们的左旋转字符串的问题中来，对于这个左旋转字符串的问题，咱们可以如下这样考虑：
1.1、思路一：

对于这个问题，咱们换一个角度，可以这么做：
将一个字符串分成两部分，X和Y两个部分，在字符串上定义反转的操作X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么我们可以得到下面的结论：(X^TY^T)^T=YX。显然我们这就可以转化为字符串的反转的问题了。

不是么?ok,就拿abcdef 这个例子来说（非常简短的三句，请细看，一看就懂）：
1、首先分为俩部分，X:abc，Y:def；
2、X->X^T，abc->cba， Y->Y^T，def->fed。
3、(X^TY^T)^T=YX，cbafed->defabc，即整个翻转。

我想，这下，你应该了然了。
然后，代码可以这么写（已测试正确）：

1.2、答案V0.3版中，第26题勘误：

    之前的答案V0.3版[第21-40题答案]中，第26题、贴的答案有误，那段代码的问题，最早是被网友Sorehead给指出来的：

第二十六题：
楼主的思路确实很巧妙，我真没想到还有这种方法，学习了。
不过楼主代码中存在问题，主要是条件判断部分：
函数LeftRotateString中 if (nLength > 0 || n == 0 || n > nLength)
函数ReverseString中 if (pStart == NULL || pEnd == NULL)

    当时，以答案整理因时间仓促，及最开始考虑问题不够周全为由，没有深入细看下去。后来，朋友达摩流浪者再次指出了上述代码的问题：

  26题 这句 if(nLength > 0 || n == 0 || n > nLength)，有问题吧?
  还有一句，应该是if(!(pStart == NULL || pEnd == NULL))，吧。

    而后，修改如下（已测试正确）

 

1. //zhedahht  
2. //July、k，updated  
3. //copyright @2011.04.14，by July。  
4. //引用，请注明原作者，出处。  
5. #include <string.h>  
6. #include <iostream>  
7. using namespace std;  
8.   
9. void Swap(char* a,char* b)  //特此把交换函数，独立抽取出来。当然，不排除会有人认为，此为多此一举。  
10. {  
11.     char temp =*a;  
12.     *a = *b;  
13.     *b = temp;  
14. }  
15.   
16. // Reverse the string between pStart and pEnd  
17. void ReverseString(char* pStart, char* pEnd)  
18. {  
19.     if(*pStart != '/0' && *pEnd != '/0')     
20.         //这句也可以是：if(pStart != NULL && pEnd != NULL)。  
21.     {  
22.         while(pStart <= pEnd)  
23.         {  
24.             Swap(pStart,pEnd);   //交换  
25.   
26.             pStart++;  
27.             pEnd--;  
28.         }  
29.     }  
30. }  
31.   
32. // Move the first n chars in a string to its end   
33. char* LeftRotateString(char* pStr, unsigned int n)  
34. {  
35.     if(pStr != NULL)  
36.     {  
37.         int nLength = static_cast<int>(strlen(pStr));  
38.         if(nLength >0 && n != 0 && n<nLength)   //n可以=0,也可以说不该=0。  
39.             //nLength是整个字符串的长度，n是左边的一部分，所以应该是n<nLength。  
40.             //之前上传的答案（代码），就错在这里，最初的为n>nLength,当然，就是错的了。July、k，updated。  
41.         {  
42.             char* pFirstStart = pStr;  
43.             char* pFirstEnd = pStr + n - 1;  
44.             char* pSecondStart = pStr + n;  
45.             char* pSecondEnd = pStr + nLength - 1;  
46.               
47.             // reverse the first part of the string  
48.             ReverseString(pFirstStart, pFirstEnd);  
49.             // reverse the second part of the strint  
50.             ReverseString(pSecondStart, pSecondEnd);  
51.             // reverse the whole string  
52.             ReverseString(pFirstStart, pSecondEnd);  
53.         }  
54.     }  
55.     return pStr;  
56. }  
57.   
58. int main()  
59. {  
60.     char a[11]="hello July";   //2、修正，以一个数组实现存储整个字符串  
61.     char *ps=a;  
62.     LeftRotateString(ps, 6);  
63.     for(;*ps!='/0';ps++)  
64.         cout<<*ps;  
65.     cout<<endl;  
66.     ps=NULL;   //代码规范  
67.     return 0;  
68. }  

上述，修正的俩处错误，如下所示：
1、如上注释中所述：        
if(nLength >0 && n<nLength)  
//nLength是整个字符串的长度吧，n是左边的一部分，所以应该是n<nLength。

 

2、至于之前的主函数为什么编写错误，请看下面的注释：
int main()
{
    char *ps="hello July";  //本身没错，但你不能对ps所指的字符串做任何修改。
    //这句其实等价于：const char *ps = "hello July"
    LeftShiftString( ps, 4 );  //而在这里，试图修改ps所指的字符串常量，所以将出现错误。
    puts( ps );
    return 0;
}

当然，上面的解释也不是完全正确的，正如ivan所说：从编程实践来说，不完全对。
如果在一个大的工程里面，你怎么知道ps指向的是""字符串，还是malloc出来的东西？  
那么如何决定要不要对ps进行delete?

不过，至少第26题的思路一的代码，最终完整修正完全了。

1.3、updated:
    可能你还是感觉上述代码，有点不好理解，ok，下面再给出一段c实现的代码。
然后，我们可以看到c的高效与简洁。

 

1. //copyright@ yiyibupt&&July  
2. //已测试正确，July、updated，2011.04.17.  
3. //不要小看每一段程序，July。  
4. #include <cstdio>  
5. #include <cstring>  
6.   
7. void rotate(char *start, char *end)  
8. {  
9.     while(start != NULL && end !=NULL && start<end)  
10.     {  
11.         char temp=*start;  
12.         *start=*end;  
13.         *end=temp;  
14.         start++;  
15.         end--;  
16.     }  
17.       
18. }  
19.   
20. void leftrotate(char *p,int m)  
21. {  
22.     if(p==NULL)  
23.         return ;  
24.     int len=strlen(p);  
25.     if(m>0&&m<=len)  
26.     {  
27.         char *xfirst,*xend;  
28.         char *yfirst,*yend;  
29.         xfirst=p;  
30.         xend=p+m-1;  
31.         yfirst=p+m;  
32.         yend=p+len-1;  
33.         rotate(xfirst,xend);  
34.         rotate(yfirst,yend);  
35.         rotate(p,p+len-1);  
36.     }  
37. }  
38.   
39. int main(void)  
40. {     
41.     char str[]="abcdefghij";  
42.     leftrotate(str,3);  
43.     printf("%s/n",str);  
44.     return 0;  
45. }  

 

第二节、两指针逐步翻转
    先看下网友litaoye 的回复：26.左旋转字符串跟panda所想，是一样的，即，
以abcdef为例
1. ab->ba
2. cdef->fedc
原字符串变为bafedc
3. 整个翻转：cdefab  
  //只要俩次翻转，且时间复杂度也为O（n）。

2.1、在此，本人再奉献另外一种思路，即为本思路二：
abc defghi，要abc移动至最后
abc defghi->def abcghi->def ghiabc

定义俩指针，p1指向ch[0]，p2指向ch[m]；
一下过程循环m次，交换p1和p2所指元素，然后p1++, p2++；。

第一步，交换abc 和def ，
abc defghi->def abcghi
第二步，交换abc 和 ghi，
def abcghi->def ghiabc

整个过程，看起来，就是abc 一步一步 向后移动
abc defghi
def abcghi
def ghi abc  
  //最后的 复杂度是O（m+n）  

以下是朋友颜沙针对上述过程给出的图解：

2.2、各位读者注意了：

    由上述例子九个元素的序列abcdefghi，您已经看到，m=3时，p2恰好指到了数组最后一个元素，于是，上述思路没有问题。但如果上面例子中i 的后面还有元素列?

    即，如果是要左旋十个元素的序列：abcdefghij，ok，下面，就举这个例子，对abcdefghij序列进行左旋转操作：

如果abcdef ghij要变成defghij abc：
  abcdef ghij
1. def abc ghij
2. def ghi abc j      //接下来，j 步步前移
3. def ghi ab jc
4. def ghi a j bc
5. def ghi j abc 

 下面，再针对上述过程，画个图清晰说明下，如下所示：

  ok，咱们来好好彻底总结一下此思路二：（就4点，请仔细阅读）：

1、首先让p1=ch[0]，p2=ch[m]，即让p1，p2相隔m的距离；

2、判断p2+m-1是否越界，如果没有越界转到3，否则转到4（abcdefgh这8个字母的字符串，以4左旋，那么初始时p2指向e，p2+4越界了，但事实上p2至p2+m-1是m个字符，可以再做一个交换）。

3、不断交换*p1与*p2，然后p1++，p2++，循环m次，然后转到2。

4、此时p2+m-1 已经越界，在此只需处理尾巴。过程如下：

   4.1 通过n-p2得到p2与尾部之间元素个数r，即我们要前移的元素个数。

   4.2 以下过程执行r次：

       ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；

（特别感谢tctop组成员big的指正，tctop组的修订wiki页面为：http://tctop.wikispaces.com/）

    所以，之前最初的那个左旋转九个元素abcdefghi的思路在末尾会出现问题的（如果p2后面有元素就不能这么变，例如，如果是处理十个元素，abcdefghij 列?对的，就是这个意思），解决办法有两个：

方法一（即如上述思路总结所述）：
def ghi abc jk
当p1指向a，p2指向j时，由于p2+m越界，那么此时p1，p2不要变
这里p1之后（abcjk)就是尾巴，处理尾巴只需将j,k移到abc之前，得到最终序列，代码编写如下：

  方法二：
def ghi abc jk
当p1指向a，p2指向j时，那么交换p1和p2，
此时为:
def ghi jbc ak

p1++，p2++,p1指向b，p2指向k，继续上面步骤得:
def ghi jkc ab

p1++，p2不动,p1指向c，p2指向b，p1和p2之间（cab)也就是尾巴，
那么处理尾巴（cab)需要循环左移一定次数（而后的具体操作步骤已在下述程序的注释中已详细给出）。

    根据方案二，不难写出下述代码（已测试正确）：

注意：上文中都是假设m<n，且如果鲁棒点的话令m=m%n，这样m允许大于n。另外，各位要记得处理指针为空的情况。      

 还可以看下这段代码：

 

1. /* 
2.  * myinvert2.cpp 
3.  * 
4.  *  Created on: 2011-5-11 
5.  *      Author: BigPotato 
6.  */  
7. #include<iostream>  
8. #include<string>  
9. #define positiveMod(m,n) ((m) % (n) + (n)) % (n)  
10.   
11. /* 
12.  *左旋字符串str，m为负数时表示右旋abs（m）个字母 
13.  */  
14. void rotate(std::string &str, int m) {  
15.     if (str.length() == 0)  
16.         return;  
17.     int n = str.length();  
18.     //处理大于str长度及m为负数的情况,positiveMod可以取得m为负数时对n取余得到正数  
19.     m = positiveMod(m,n);  
20.     if (m == 0)  
21.         return;  
22.     //    if (m % n <= 0)  
23.     //        return;  
24.     int p1 = 0, p2 = m;  
25.     int round;  
26.     //p2当前所指和之后的m-1个字母共m个字母，就可以和p2前面的m个字母交换。  
27.     while (p2 + m - 1 < n) {  
28.         round = m;  
29.         while (round--) {  
30.             std::swap(str[p1], str[p2]);  
31.             p1++;  
32.             p2++;  
33.         }  
34.     }  
35.     //剩下的不足m个字母逐个交换  
36.     int r = n - p2;  
37.     while (r--) {  
38.         int i = p2;  
39.         while (i > p1) {  
40.             std::swap(str[i], str[i - 1]);  
41.             i--;  
42.         }  
43.         p2++;  
44.         p1++;  
45.     }  
46. }  
47.   
48. //测试  
49. int main(int argc, char **argv) {  
50.     //    std::cout << ((-15) % 7 + 7) % 7 << std::endl;  
51.     //    std::cout << (-15) % 7 << std::endl;  
52.     std::string ch = "abcdefg";  
53.     int len = ch.length();  
54.     for (int m = -2 * len; m <= len * 2; m++) {  
55.         //由于传给rotate的是string的引用，所以这里每次调用都用了一个新的字符串  
56.         std::string s = "abcdefg";  
57.         rotate(s, m);  
58.         std::cout << positiveMod(m,len) << ": " << s << std::endl;  
59.     }  
60.    
61.     return 0;  
62. }  

 

第三节、通过递归转换，缩小问题之规模

    本文最初发布时，网友留言bluesmic说：楼主，谢谢你提出的研讨主题，很有学术和实践价值。关于思路二，本人提一个建议：思路二的代码，如果用递归的思想去简化，无论代码还是逻辑都会更加简单明了。

    就是说，把一个规模为N的问题化解为规模为M(M<N)的问题。
    举例来说，设字符串总长度为L，左侧要旋转的部分长度为s1，那么当从左向右循环交换长度为s1的小段，直到最后，由于剩余的部分长度为s2(s2==L%s1)而不能直接交换。

    该问题可以递归转化成规模为s1+s2的，方向相反(从右向左)的同一个问题。随着递归的进行，左右反复回荡，直到某一次满足条件L%s1==0而交换结束。

     举例解释一下：
    设原始问题为：将“123abcdefg”左旋转为“abcdefg123”，即总长度为10，旋转部("123")长度为3的左旋转。按照思路二的运算，演变过程为“123abcdefg”->"abc123defg"->"abcdef123g"。这时，"123"无法和"g"作对调，该问题递归转化为：将“123g”右旋转为"g123"，即总长度为4，旋转部("g")长度为1的右旋转。

updated：

Ys：

Bluesmic的思路没有问题，他的思路以前很少有人提出。思路是通过递归将问题规模变小。当字符串总长度为n，左侧要旋转的部分长度为m，那么当从左向右循环交换长度为m的小段直到剩余部分为m’(n % m)，此时m’ < m，已不能直接交换了。

此后，我们换一个思路，把该问题递归转化成规模大小为m’ +m，方向相反的同一问题。随着递归的进行，直到满足结束条件n % m==0。

  举个具体事例说明，如下：

1、对于字符串abc def ghi gk，

将abc右移到def ghi gk后面，此时n = 11，m = 3，m’ = n % m = 2;

abc def ghi gk -> def ghi abc gk

2、问题变成gk左移到abc前面，此时n = m’ + m = 5，m = 2，m’ = n % m 1;

abc gk -> a gk bc

3、问题变成a右移到gk后面，此时n = m’ + m = 3，m = 1，m’ = n % m = 0;

a gk bc-> gk a bc。 由于此刻，n % m = 0，满足结束条件，返回结果。

    即从左至右，后从右至左，再从左至右，如此反反复复，直到满足条件，返回退出。

    代码如下，已测试正确（有待优化）：

非常感谢。

    稍后，由下文，您将看到，其实上述思路二的本质即是下文将要阐述的stl rotate算法，详情，请继续往下阅读。

第四节、stl::rotate 算法的步步深入
思路三：

3.1、数组循环移位
    下面，我将再具体深入阐述下此STL 里的rotate算法，由于stl里的rotate算法，用到了gcd的原理，下面，我将先介绍此辗转相除法，或欧几里得算法，gcd的算法思路及原理。

    gcd，即辗转相除法，又称欧几里得算法，是求最大公约数的算法，即求两个正整数之最大公因子的算法。此算法作为TAOCP第一个算法被阐述，足见此算法被重视的程度。

    gcd算法：给定俩个正整数m，n（m>=n），求它们的最大公约数。（注意，一般要求m>=n，若m<n，则要先交换m<->n。下文，会具体解释）。以下，是此算法的具体流程：
    1、[求余数]，令r=m%n，r为n除m所得余数（0<=r<n）；
    2、[余数为0?]，若r=0，算法结束，此刻，n即为所求答案，否则，继续，转到3；
    3、[重置]，置m<-n，n<-r，返回步骤1.

    此算法的证明，可参考计算机程序设计艺术第一卷：基本算法。证明，此处略。

    ok，下面，举一个例子，你可能看的更明朗点。
    比如，给定m=544，n=119，
      则余数r=m%n=544%119=68; 因r!=0，所以跳过上述步骤2，执行步骤3。；
      置m<-119，n<-68，=>r=m%n=119%68=51;
      置m<-68，n<-51，=>r=m%n=68%51=17；
      置m<-51，n<-17，=>r=m%n=51%17=0，算法结束，

    此时的n=17，即为m=544，n=119所求的俩个数的最大公约数。

    再解释下上述gcd(m，n)算法开头处的，要求m>=n 的原因：举这样一个例子，如m<n，即m=119，n=544的话，那么r=m%n=119%544=119,
    因为r!=0,所以执行上述步骤3，注意，看清楚了：m<-544，n<-119。看到了没，尽管刚开始给的m<n，但最终执行gcd算法时，还是会把m，n的值交换过来，以保证m>=n。

    ok，我想，现在，你已经彻底明白了此gcd算法，下面，咱们进入主题，stl里的rotate算法的具体实现。//待续。

    熟悉stl里的rotate算法的人知道，对长度为n的数组(ab)左移m位，可以用stl的rotate函数（stl针对三种不同的迭代器，提供了三个版本的rotate）。但在某些情况下，用stl的rotate效率极差。

    对数组循环移位，可以采用的方法有（也算是对上文思路一，和思路二的总结）：

      flyinghearts：
      ① 动态分配一个同样长度的数组，将数据复制到该数组并改变次序，再复制回原数组。（最最普通的方法）
      ② 利用ba=(br)^T(ar)^T=(arbr)^T，通过三次反转字符串。（即上述思路一，首先对序列前部分逆序，再对序列后部分逆序，再对整个序列全部逆序）
      ③ 分组交换（尽可能使数组的前面连续几个数为所要结果）：
      若a长度大于b，将ab分成a0a1b，交换a0和b，得ba1a0，只需再交换a1 和a0。
      若a长度小于b，将ab分成ab0b1，交换a和b0，得b0ab1，只需再交换a 和b0。
      通过不断将数组划分，和交换，直到不能再划分为止。分组过程与求最大公约数很相似。
      ④ 所有序号为 (j+i *m) % n (j 表示每个循环链起始位置，i 为计数变量，m表示左旋转位数，n表示字符串长度)，会构成一个循环链（共有gcd(n,m)个，gcd为n、m的最大公约数），每个循环链上的元素只要移动一个位置即可，最后整个过程总共交换了n次（每一次循环链，是交换n/gcd(n,m)次，总共gcd(n,m)个循环链。所以，总共交换n次）。

    stl的rotate的三种迭代器，即是，分别采用了后三种方法。

    在给出stl rotate的源码之前，先来看下我的朋友ys对上述第④ 种方法的评论：
    ys：这条思路个人认为绝妙，也正好说明了数学对算法的重要影响。

    通过前面思路的阐述，我们知道对于循环移位，最重要的是指针所指单元不能重复。例如要使abcd循环移位变成dabc(这里m=3,n=4)，经过以下一系列眼花缭乱的赋值过程就可以实现：
    ch[0]->temp, ch[3]->ch[0], ch[2]->ch[3], ch[1]->ch[2], temp->ch[1];  （*）
    字符串变化为：abcd->_bcd->dbc_->db_c->d_bc->dabc;
是不是很神奇？其实这是有规律可循的。

    请先看下面的说明再回过头来看。
 对于左旋转字符串，我们知道每个单元都需要且只需要赋值一次，什么样的序列能保证每个单元都只赋值一次呢？

      1、对于正整数m、n互为质数的情况，通过以下过程得到序列的满足上面的要求：
 for i = 0: n-1
      k = i * m % n;
 end

    举个例子来说明一下，例如对于m=3,n=4的情况，
        1、我们得到的序列：即通过上述式子求出来的k序列，是0, 3, 2, 1。
        2、然后，你只要只需按这个顺序赋值一遍就达到左旋3的目的了：
    ch[0]->temp, ch[3]->ch[0], ch[2]->ch[3], ch[1]->ch[2], temp->ch[1];   （*） 

    ok，这是不是就是按上面（*）式子的顺序所依次赋值的序列阿?哈哈，很巧妙吧。当然，以上只是特例，作为一个循环链，相当于rotate算法的一次内循环。

     2、对于正整数m、n不是互为质数的情况（因为不可能所有的m，n都是互质整数对），那么我们把它分成一个个互不影响的循环链，正如flyinghearts所言，所有序号为 (j + i * m) % n（j为0到gcd(n, m)-1之间的某一整数，i = 0:n-1）会构成一个循环链，一共有gcd(n, m)个循环链，对每个循环链分别进行一次内循环就行了。

    综合上述两种情况，可简单编写代码如下：

后来有网友针对上述的思路④，给出了下述的证明：
    1、首先，直观的看肯定是有循环链，关键是有几条以及每条有多长，根据(i+j *m) % n这个表达式可以推出一些东东，一个j对应一条循环链，现在要证明(i+j *m) % n有n/gcd(n,m)个不同的数。
    2、假设j和k对应的数字是相同的， 即(i+j*m)%n = (i+k*m)%n， 可以推出n|(j-k)*m，m=m’*gcd(n.m), n=n’*gcd(n,m), 可以推出n’|(j-k)*m’，而m’和n’互素，于是n’|(j-k)，即(n/gcd(n,m))|(j-k)，
    3、所以(i+j*m) % n有n/gcd(n,m)个不同的数。则总共有gcd(n，m)个循环链。符号“|”是整除的意思。
以上的3点关于为什么一共有gcd(n, m)个循环链的证明，应该是来自qq3128739xx的，非常感谢这位朋友。

3.2、以下，便是摘自sgi stl v3.3版中的stl_algo_h文件里，有关rotate的实现的代码：

 

1. // rotate and rotate_copy, and their auxiliary functions  
2. template <class _EuclideanRingElement>  
3. _EuclideanRingElement __gcd(_EuclideanRingElement __m,  
4.                             _EuclideanRingElement __n)  
5. {  //gcd(m,n)实现  
6.     while (__n != 0) {  
7.         _EuclideanRingElement __t = __m % __n;  
8.         __m = __n;  
9.         __n = __t;  
10.     }  
11.     return __m;   //....  
12. }  
13.   
14. //③ 分组交换（尽可能使数组的前面连续几个数为所要结果）：  
15. //若a长度大于b，将ab分成a0a1b，交换a0和b，得ba1a0，只需再交换a1 和a0。  
16. //若a长度小于b，将ab分成ab0b1，交换a和b0，得b0ab1，只需再交换a 和b0。  
17. //通过不断将数组划分，和交换，直到不能再划分为止。分组过程与求最大公约数很相似。  
18. template <class _ForwardIter, class _Distance>  
19. _ForwardIter __rotate(_ForwardIter __first,  
20.                       _ForwardIter __middle,  
21.                       _ForwardIter __last,  
22.                       _Distance*,  
23.                       forward_iterator_tag)   
24. {  
25.     if (__first == __middle)  
26.         return __last;  
27.     if (__last  == __middle)  
28.         return __first;  
29.       
30.     _ForwardIter __first2 = __middle;  
31.     do {  
32.         swap(*__first++, *__first2++);  //  
33.         if (__first == __middle)  
34.             __middle = __first2;  
35.     } while (__first2 != __last);  
36.       
37.     _ForwardIter __new_middle = __first;  
38.     __first2 = __middle;  
39.       
40.     while (__first2 != __last)   
41.     {  
42.         swap (*__first++, *__first2++);  //  
43.         if (__first == __middle)  
44.             __middle = __first2;  
45.         else if (__first2 == __last)  
46.             __first2 = __middle;  
47.     }  
48.       
49.     return __new_middle;  
50. }  
51.   
52. //②利用ba=(br)^T(ar)^T=(arbr)^T，通过三次反转字符串。  
53. //（即上述思路一，首先对序列前部分逆序，再对序列后部分逆序，再对整个序列全部逆序）  
54. template <class _BidirectionalIter, class _Distance>  
55. _BidirectionalIter __rotate(_BidirectionalIter __first,  
56.                             _BidirectionalIter __middle,  
57.                             _BidirectionalIter __last,  
58.                             _Distance*,  
59.                             bidirectional_iterator_tag)   
60. {  
61.     __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);  
62.     if (__first == __middle)  
63.         return __last;  
64.     if (__last  == __middle)  
65.         return __first;  
66.       
67.     __reverse(__first,  __middle, bidirectional_iterator_tag());  //交换序列前半部分  
68.     __reverse(__middle, __last,   bidirectional_iterator_tag());  //交换序列后半部分  
69.       
70.     while (__first != __middle && __middle != __last)  
71.         swap (*__first++, *--__last);   //整个序列全部交换  
72.       
73.     if (__first == __middle)  //  
74.     {  
75.         __reverse(__middle, __last,   bidirectional_iterator_tag());  
76.         return __last;  
77.     }  
78.     else {  
79.         __reverse(__first,  __middle, bidirectional_iterator_tag());  
80.         return __first;  
81.     }  
82. }  
83.   
84. //④ 所有序号为 (i+t*k) % n (i为指定整数，t为任意整数)，  
85. //会构成一个循环链（共有gcd(n,k)个，gcd为n、k的最大公约数），  
86. //每个循环链上的元素只要移动一个位置即可，总共交换了n次。  
87. template <class _RandomAccessIter, class _Distance, class _Tp>  
88. _RandomAccessIter __rotate(_RandomAccessIter __first,  
89.                            _RandomAccessIter __middle,  
90.                            _RandomAccessIter __last,  
91.                            _Distance *, _Tp *)   
92. {  
93.     __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);  
94.     _Distance __n = __last   - __first;  
95.     _Distance __k = __middle - __first;  
96.     _Distance __l = __n - __k;  
97.     _RandomAccessIter __result = __first + (__last - __middle);  
98.       
99.     if (__k == 0)  
100.         return __last;  
101.       
102.     else if (__k == __l) {  
103.         swap_ranges(__first, __middle, __middle);  
104.         return __result;  
105.     }  
106.       
107.     _Distance __d = __gcd(__n, __k);    //令d为gcd(n,k)  
108.       
109.     for (_Distance __i = 0; __i < __d; __i++) {  
110.         _Tp __tmp = *__first;  
111.         _RandomAccessIter __p = __first;  
112.           
113.         if (__k < __l) {  
114.             for (_Distance __j = 0; __j < __l/__d; __j++) {  
115.                 if (__p > __first + __l) {  
116.                     *__p = *(__p - __l);  
117.                     __p -= __l;  
118.                 }  
119.                   
120.                 *__p = *(__p + __k);  
121.                 __p += __k;  
122.             }  
123.         }     
124.         else {  
125.             for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {  
126.                 if (__p < __last - __k) {  
127.                     *__p = *(__p + __k);  
128.                     __p += __k;  
129.                 }  
130.                   
131.                 *__p = * (__p - __l);  
132.                 __p -= __l;  
133.             }  
134.         }  
135.           
136.         *__p = __tmp;  
137.         ++__first;  
138.     }  
139.       
140.     return __result;  
141. }  

 

由于上述stl rotate源码中，方案④ 的代码，较复杂，难以阅读，下面是对上述第④ 方案的简单改写：

1. //对上述方案4的改写。  
2. //④ 所有序号为 (i+t*k) % n (i为指定整数，t为任意整数)，....  
3. //copyright@ hplonline && July 2011.04.18。  
4. //July、sahala、yansha，updated，2011.06.02。  
5. void my_rotate(char *begin, char *mid, char *end)  
6. {     
7.     int n = end - begin;     
8.     int k = mid - begin;     
9.     int d = gcd(n, k);     
10.     int i, j;     
11.     for (i = 0; i < d; i ++)     
12.     {     
13.         int tmp = begin[i];     
14.         int last = i;     
15.           
16.         //i+k为i右移k的位置，%n是当i+k>n时从左重新开始。  
17.         for (j = (i + k) % n; j != i; j = (j + k) % n)    //多谢laocpp指正。     
18.         {     
19.             begin[last] = begin[j];         
20.             last = j;     
21.         }         
22.         begin[last] = tmp;     
23.     }     
24. }   

 

    对上述程序的解释：关于第二个for循环中，j初始化为（i+）%n，程序注释中已经说了，i+k为i右移k的位置，%n是当i+k>n时从左重新开始。为什么要这么做呢?很简单，n个数的数组不管循环左移多少位，用上述程序的方法一共需要交换n次。当i+k>=n时i+k表示的位置在数组中不存在了，所以又从左边开始的(i+k)%n是下一个交换的位置。

1. 好比5个学生,，编号从0开始，即0 1 2 3 4，老师说报数，规则是从第一个学生开始，中间隔一个学生报数。报数的学生编号肯定是0 2 4 1 3。这里就相当于i为0，k为2，n为5 
2. 然后老师又说，编号为0的学生出列，其他学生到在他前一个报数的学生位置上去，那么学生从0 1 2 3 4=》2 3 4 _ 1，最后老师说，编号0到剩余空位去，得到最终排位2 3 4 0 1。此时的结果，实际上就是相当于上述程序中左移k=2个位置了。而至于为什么让 编号为0 的学生 出列。实际是这句：int last = i; 因为要达到这样的效果0 1 2 3 4 => 2 3 4 0 1，那么2 3 4 必须要移到前面去。怎么样，明白了么?。

关于本题，不少网友也给出了他们的意见，具体请参见此帖子微软100题，维护地址。 

第五节、总结 
     如nossiac所说，对于这个数组循环移位的问题，真正最靠谱的其实只有俩种：一种是上文的思路一，前后部分逆置翻转法，第二种是思路三，即stl 里的rotate算法，其它的思路或方法，都是或多或少在向这俩种方法靠拢。

    下期更新：程序员面试题狂想曲：第二章。时间：本周周日04.24晚。非常感谢各位朋友的，支持与关注。本人宣告：本程序员面试题狂想曲系列，永久更新。
本章完。

本文转自博客园知识天地的博客，原文链接：程序员编程艺术第一章、左旋转字符串，如需转载请自行联系原博主。