好的,现在,回到咱们的左旋转字符串的问题中来,对于这个左旋转字符串的问题,咱们可以如下这样考虑:
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、如上注释中所述:
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的高效与简洁。
第二节、两指针逐步翻转
先看下网友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、各位读者注意了: