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

由上述例子九个元素的序列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],即让p1p2相隔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页面为:

    所以,之前最初的那个左旋转九个元素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。另外,各位要记得处理指针为空的情况。      

还可以看下这段代码:

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

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

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