程序员面试题狂想曲：第一章、左旋转字符串


作者：July。
时间：二零一一年四月十四日。
说明：狂想曲，谓之思绪纷飞，行文杂乱无章，想到什么，记下什么，思维奇特而跳跃。
出处：http://blog.csdn.net/v_JULY_v。
-------------------------------------------
序
    一个懒散的午夜，程序员躺在椅子上，静静点上一支烟，瞅着屏幕上那一行一行如行云流水般的代码，赏心悦目，渐觉困意，便慢慢闭上了双眼，养神...。
    而后，冥冥中房间里似缓缓响起一首钢琴曲，叫不出名字，却铿锵有力且清脆无比，忽而激荡，忽而平静。激荡处，如波涛翻滚，怒洋咆哮，平静处，如潺潺流水，鸟语花香。
    半响，程序员突然睁开眼睛，关掉编译器，打开记事本，信笔由缰，急速记录下他那杂乱无章，和奇特跳跃的思绪，他怕此刻不赶紧记下来，以后，风吹云散.....于是，世间就有了，程序员面试题狂想曲，一乐章的诞生。
    此曲终日弹奏，绵绵不绝，终至广为流传，飘进了千万人的耳中，余音不去....

前言
    本人整理微软等公司面试100题系列，包括原题整理，资源上传，帖子维护，答案整理，勘误，修正与优化工作，包括后续全新整理的80道，总计180道面试题，已有半年的时间了。
    关于这180道面试题的一切详情，请参见：横空出世，席卷Csdn [评微软等数据结构+算法面试180题]。
    一直觉得，这180道题中的任何一题都值得自己反复思考，反复研究，不断修正，不断优化。之前的答案整理由于时间仓促，加之受最开始的认识局限，更兼水平有限，所以，这180道面试题的答案，有很多问题都值得进一步商榷与完善。
    特此，想针对这180道面试题，再写一个系列，叫做：程序员面试题狂想曲系列。如你所见，我一般确定要写成一个系列的东西，一般都会永久写下去的。
    “他似风儿一般奔跑，很多人渐渐的停下来了，而只有他一直在飞，一直在飞....”
    
    ok，本次系列以之前本人最初整理的微软面试100题中的第26题、左旋转字符串，为开篇，希望就此问题进行彻底而深入的阐述。还是那句话，有任何问题，请不吝指正。谢谢。
 
第一节、左旋转字符串
题目描述：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。 

    一听左旋，右旋之类的，便想到了红黑树中有关左旋，右旋的操作，不过，本题显然与此无关。ok，我最初在之前上传的答案：答案V0.3版[第21-40题答案]中，整理并提供了以下俩种思路：

思路一：
//其实此思路一比较混乱，且代码也有点问题，建议着重看思路二：
此思路一，引自网友zhedahht（http://zhedahht.blog.163.com/blog/#m）。
    
    分析：如果不考虑时间和空间复杂度的限制，最简单的方法莫过于把这道题看成是把字符串分成前后两部分，通过旋转操作把这两个部分交换位置。
    于是我们可以新开辟一块长度为n+1的辅助空间，把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分拷贝到新空间的后半部分。不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也是O(n)。
    因此，我们另寻思路，咱们试着把字符串看成有两段组成的，记为XY。左旋转相当于要把字符串XY变成YX。
我们先在字符串上定义一种翻转的操作，即翻转字符串中字符的先后顺序：把X翻转后记为XT,显然有(XT)T=X。
我们首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。
接着再对XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。
分析到这里我们再回到原来的题目：我们要做的仅仅是把字符串分成两段，
第一段为前面m个字符，其余的字符分到第二段。再定义一个翻转字符串的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。
最初的代码如下（后来，我们将知道这段代码有几处错误，下文将具体阐述）：//引自：http://zhedahht.blog.163.com/blog/#m。
//2011.04.15更新：
//因为本人的问题，未在醒目处注明上述链接，引起cadcisdhht误会及易做图，向其严重致歉。
//July、updated，2011.04.15。
#include "string.h"
// Move the first n chars in a string to its end 
char* LeftRotateString(char* pStr, unsigned int n)
{
    if(pStr != NULL)
    {
        int nLength = static_cast<int>(strlen(pStr));
        if(nLength > 0 || n == 0 || n > nLength)   //1、这里有问题，下文具体阐述。
        {
            char* pFirstStart = pStr;
            char* pFirstEnd = pStr + n - 1;
            char* pSecondStart = pStr + n;
            char* pSecondEnd = pStr + nLength - 1;
            
            // reverse the first part of the string
            ReverseString(pFirstStart, pFirstEnd);
            // reverse the second part of the strint
            ReverseString(pSecondStart, pSecondEnd);
            // reverse the whole string
            ReverseString(pFirstStart, pSecondEnd);
        }
    }
    
    return pStr;
}
// Reverse the string between pStart and pEnd
void ReverseString(char* pStart, char* pEnd)
{
    if(pStart == NULL || pEnd == NULL)     //2、这里也有问题，下文具体阐述。
    {
        while(pStart <= pEnd)
        {
            char temp = *pStart;
            *pStart = *pEnd;
            *pEnd = temp;
            
            pStart ++;
            pEnd --;
        }
    }
} 
思路二（请着重看此思路）：
先看下网友litaoye 的回复：
26.左旋转字符串
跟panda所想，是一样的，即，
以abcdef为例
1. ab->ba
2. cdef->fedc
原字符串变为bafedc
3. 整个翻转：cdefab  
  //只要俩次翻转，且时间复杂度也为O（n）。
    在此，本人再奉献另外一种思路，即为本思路二：
abc defghi，要abc移动至最后
abc defghi->def abcghi->def ghiabc
一俩指针，p1指向ch[0]，p2指向 ch[m-1]，
p2每次移动m 的距离，p1 也跟着相应移动，每次移动过后，交换。
第一步，交换abc 和def ，
abc defghi->def abcghi
第二步，交换abc 和 ghi，
def abcghi->def ghiabc
整个过程，看起来，就是abc 一步一步 向后移动
abc defghi
def abcghi
def ghi abc  
  //最后的 复杂度是O（m+n）  
以下是朋友颜沙针对上述过程给出的图解：

 
    各位读者注意了：由上述例子九个元素的序列abcdefghi，您已经看到，m=3时，p2恰好指到了数组最后一个元素，于是，上述思路没有问题。但如果上面例子中c的后面还有元素列?
    即，如果是要左旋十个元素的序列：abcdefghij，ok，下面，就举这个例子，对abcdefghij序列进行左旋转操作：
如果abcdef ghij要变成defghij abc：
  abcdef ghij
1. def abc g

补充：综合编程 , 其他综合 ,