程序员编程艺术(算法卷):第一章、左旋转字符串 (3)

好的,现在,回到咱们的左旋转字符串的问题中来,对于这个左旋转字符串的问题,咱们可以如下这样考虑:
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、各位读者注意了:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzsszg.html