作者：July。
时间：二零一一年四月十四日。
出处：http://blog.csdn.net/v_JULY_v。
-------------------------------------------
前言
本人整理微软等公司面试100题系列，包括原题整理，资源上传，帖子维护，答案整理，勘误，修正与优化工作，包括后续全新整理的80道，总计180道面试题，已有半年的时间了。
一直觉得，最初的这100道题中的任何一题都值得自己反复思考，反复研究，不断修正，不断优化。之前的答案整理由于时间仓促，加之受最开始的认识局限，更兼水平有限，所以，这100道面试题的答案，有很多问题都值得进一步商榷与完善。
特此，想针对这180道面试题，再写一个系列，叫做：程序员面试题狂想曲狂想曲系列。如你所见，我一般确定要写成一个系列的东西，一般都会永久写下去的。
我似风儿一般奔跑，很多人渐渐的停下来了，而只有我一直在飞，一直在飞....
ok，本次系列以之前本人整理的微软面试100题中的第26题为开篇，希望就此问题彻底而深入的阐述。还是那句话，有任何问题，请不吝指正。谢谢。
左旋转字符串
题目描述：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。
我最初在之前上传的答案：答案V0.3版[第21-40题答案]中，提供了以下俩种思路：
思路一：
//引自网友zhedahht。
分析：如果不考虑时间和空间复杂度的限制，最简单的方法莫过于把这道题看成是把字符串分成前后两部分，通过旋转操作把这两个部分交换位置。
于是我们可以新开辟一块长度为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个字符，其余的字符分到第二段。再定义一个翻转字符串的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。
最初的代码如下（后来，我们将知道这段代码有几处错误，下文将具体阐述）：
////引自网友zhedahht。
#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 --;
}
}
}
思路二：
针对262 楼 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 ，就变成了 abcdef->defabc
第一步，
abc defghi->def abcghi
第二步，继续交换，
def abcghi->def ghiabc
整个过程，看起来，就是abc 一步一步 向后移动
abc defghi
def abcghi
def ghi abc
//最后的 复杂度是O（m+n）
再举一个例子，
如果123 4567890要变成4567890 123：
123 4567890
1. 456 123 7890
2. 456789 123 0
3. 456789 12 0 3
4. 456789 1 0 23
5. 4567890 123 //最后三步，相当于0前移，p1已经不动。
欢迎，就此第26题，继续讨论。
思路二，基本上没有什么问题，下面，我将具体针对思路一，具体而深入的阐述。
一步一步修正思路二的代码
很快，第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))，吧。
我终于意识到，上述那段引自网友zhedahht的代码的严重错误了，修改后，如下（但，还是有问题）:
//以下是原来引自zhedahht的代码：
#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 && nLength<n && n != 0 ) //这里还是有问题，下面将阐述。
{
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)) // 或许，该改成这样。
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;
}
}
}
然后，我编写如下的主函数，测试下后，发现这段代码还是有问题（并因大意，又引进了一个新问题）：
int main()
{
char *ps="hello July"; //新的问题出现
LeftRotateString(ps, 4);
for(;*ps!='\0';ps++)
cout<<*ps;
return 0;
}
再费劲周折，上述代码，最终完整修正如下，测试也已通过，正确：
修正的俩处错误，如下所示：
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题的思路二的代码，最终完整修正完全了。
其它的四种思路
思路三：
有匿名网友指出：STL里面的rotate算法不错，
就是对m和n求最小公倍数，然后将数组分为gcd(m,n)组分别进行循环移位。
代码大概是：
void rotate(string s, int m)
{
int n = s.length();
int g = gcd(m,n);
int a = n/g;
for(int i =0;i<g;i++)
{
int tmp = s[i];
for(int j = 0; j<a; j++)
{
s[(i+j*a)%n] = s[(i+j*a+m)%n];
}
s[(i+j*g)%n] = tmp;
}
}
所用到的原理就是对于互质正整数a,b, 对于m*a%b m = 0...b-1,可以取到0到b-1中所有的值且并不重复
，并且连续两个相邻的值在循环关系中相差m个位置 ，对这个数组进行循环左移就可以完成数组的左旋。
同理，当,a,b不互质时，就要将数组分为gcd(a,b)个子数组，对每个数组分别移位，
可以证明，这样分组 这些子数组间不会相互干扰 。
另外，网友大肥指出另一种算法，不过，这个方法，在之前的答案V0.3版中已经提到过：
1.给2个指针p1和p2,p1=p2=ch[0];
2.移动p2到ch[m-1]假设之间的距离是m
while( p1 != p2 )
{
swap( *p1, *p2 );
p1++;
if( p2+1 )
p2++;
}
这样我们可以做一个模拟的过程
abcdefgh 我们要移动abc到最后
那么有 abcdefghij => defabcghij(这个时候p1在a，p2在f)
=> defghiabcj(p1在a，p2在i)
=> defghijbca
=> defghijacb
=> defghijabc(完成)
最后3步p2没有移动。
时间复杂度就是O(n+m) = O(n), swap也就只要O(1)的空间就好！
思路四：
另外一位网友对第26题的思路：
考虑了一下取GCD的道理：
这总长为n，前半段长为p，那么从下标0开始进行替换运算，每次下标均增加p，这里的加法是在群[Zn, +]上的运算。而这样能够涉及到的元素，其实是p的生成群H=(p)。
如果H不等于Zn的话，就有一部分元素没有移位。而Lagrange定理告诉我们，H的基数一定是n的约数，我
们还有对每一个陪集进行移位。
设生成群H的基数为k，则p*k = 0(群Zn上的运算)，放在普通的整数运算上，为p* k = 0 mod n或p * k = m*n，得出k=m*n/p=m*b*gcd(p,n)/a*gcd(n,p)，所以k = b = n / gcd(n, p)，根据Lagrange定理，陪集个数为gcd(p, n)。
他的代码为：
void rotate_left(char *str, int left)
{
int n = strlen(str);
int g = gcd(n, left);
char tmp;
int cur, start, next;
for(start = 0; start < g; start++){
tmp = str[start];
next = cur = start;
do{
cur = next;
next = (cur + left) % n;
str[cur] = str[next];
}while(next != start);
str[cur] = tmp;
}
}
思路五：
j_yeen：
原来代码有点小问题，仔细研究，不难看出当len,与旋转长度都为偶数的时候，循环数组需要分2次处理。
下面给出修正后的代码：
void LeftRotate(char *str, unsigned len, unsigned k)
{
char tmp_c = str[0];
unsigned next_pos = 0;
if(len % 2 == 0 && k % 2 == 0)
///长度与需要旋转的长度同为偶
{
for(unsigned i = 0; i < len / 2; ++i)
{
///交换偶数位置
}
tmp_c = str[1];
next_pos = 1;
for(i = 0; i < len / 2 ; ++i)
{
///交换奇数位置
}
}
else ///长度或需要旋转长度之一为奇数
{
for(unsigned i = 0; i < len; ++i)
{
}
}
}
思路六：
damon：
不清楚为什么思路二，那段代码要这么写，是否是为了增加复杂性或者就是为了讲述算法，考虑到这个问题，其实与整数左移类似，可以考虑使用一个内存缓冲区来进行相关操作。
//newrain021011
#include <string.h>
#include <stdio.h>
char* LeftShiftString(char* pStr, unsigned int n)
{
int length = strlen( pStr );
char* temp_str = new char[n+1]; // 在C99中可以直接使用堆栈缓冲区来创建这个缓冲区区域。
memcpy(temp_str, pStr, n);
memcpy(pStr, pStr+n, length-n);
memcpy(pStr+length-n, temp_str, n);
delete[] temp_str;
return pStr;
}
int main()
{
char *ps="hello July";
LeftShiftString( ps, 4 );
puts( ps );
return 0;
}
同样，他的主函数的编写，也犯了一个与我上面同样的一个错误，我把它修正如下：
思路七：
当然，Sorehead出了最先指出思路二的代码的错误，他也给出了他自己的思路和代码：
第二十六题：
下面说说自己的思路，我想到的是另外两种方法：
方法一：
刚看到这题时，我觉得这个很简单嘛，就按照普通的字符串移动处理方式做不就可以了。
例如abcdef左旋转2位，就以2位单位把字符串切分成多段，分别交换即可。
首先是cd与ab交换，结果是cdabef，
然后是ef与ab交换，结果是cdefab，这已经完成目标了。
看上去没啥问题，但这种方法在字符串长度和旋转位数不符合某种关系时，是会出现问题的。
例如abcdefgh左旋转3位，按照思路先交换abc与def，结果是defabcgh，
接下来的abc与gh进行交换就存在问题了，因为这两个字符串长度不匹配，中间交换的部分空间是重合的，这时候就不大好做了。
关键就是解决最后这个尾巴问题，解决思路就是利用左、右旋转分别转化为右、左旋转来做，因为长度为len的字符串左旋转n次实际上和右旋转len-n次是等同的，是否转换要看n和len-n谁小。
还是以abcdefgh左旋转3位为例，字符串长度为8，由于3小于8-3=5，
1、先对3的整数倍部分进行左旋转操作，结果是defabcgh；
2、然后对abcgh做处理，右旋转2位，结果是aghbc；
3、再对agh做处理，左旋转1位，结果是gha，至此操作完毕。
方法二：
方法一的思路看上去有点复杂，我换了一个思路来解决这个问题，从单个字符的角度出发，就是把该字符左移n位而已。
还是以abcdefgh左旋转3位为例，从a开始，把a左移3位到f的位置，然后把f左移3位到c的位置，再把c左移3位到h的位置，一直循环下去，直到再次到最开始时a的位置。
和方法一正好相反，这种方法解决上面的例子没有问题，但解决abcdef左旋转2位时反而出现问题了，按照上面的操作，循环完毕后结果是cbedaf，这明显不对。
看来简单的一个循环是解决不了问题的，那到底要多少个循环呢，通过分析，循环的个数其实就是字符串长度len和左旋转次数n的最大公因子。
当我把两种方法代码都写完后，发现这两种方法其实是异曲同工的，方法二中最大公因子的计算采用的是辗转相除法，而方法一其实也是辗转处理的方法。不同的是，方法一把辗转处理放到字符串上，而方法二是用这种方法实现求得公因子。
但我觉得还是楼主的方法从代码上看上去更简单。
其实对于交换，是可以不需要辅助空间的，可以使用加法和异或操作直接进行数据交换，不过加法可能会有溢出的问题，所以还是异或操作更好。
他也给出了具体的代码，具体请参见此帖子的第617、618楼。完。
思路二，思路六的完整代码
最后，再总结一下思路二，和思路六的俩段代码，如下：
至此，全部的七种思路完。
本文完。
最新评论