算法:8.旋转字符串

https://www.lintcode.com/problem/rotate-string/description

描述

给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转)。

样例

对于字符串 .

挑战

在数组上原地旋转,使用O(1)的额外空间

思路

最开始的想法是很简单的,就是将数组元素整段挪动。实现见下面的第一个实现代码。使用System.arraycopy直接搬运整段数组,需要offset的额外的存储空间。

代码

直接粗暴的实现

这种实现还可以微调一下,将额外空间控制在不大于 str.length/2 即原数组大小的1/2。通过比较offset和str.length/2的大小决定将左半部分还是右半部分拷贝到临时数组中。就不再贴具体代码了。

对于问题还有另外一个解决办法,就是将后面offset大小的部分和前面offset部分进行元素值的交换。 比如 “abcdefg”,offset=3。我们先将后面3个和前面三个进行交换,交换以后数组变为 “efgdabc” ,注意到交换后前面offset部分的数组元素的位置已经正确了。观察到后面“dabc”部分,我们再重复一次前面的操作,只不过这次的开始交换位置是从“d”的位置开始的,交换的变化过程为 "dabc"->"adbc"->"abdc"->"abcd",可以看到这次交换完成以后整个字符数组变为"efgabcd"已经完成旋转的目标了。

递归算法的思想就是每次交换后面[str.length-offset,str.length-1]部分和前面[0,offset-1]大小的数组元素,不过每次的前面位置的起始坐标都在变化,没交换一次起始左边就向右移动offset个位置,以start标记所以前面部分的起始元素坐标,那么没交换一次,start都要增加offset,前面offset个元素的坐标范围是[start, start+offset-],另外还需要注意的时,交换之后剩下的再次递归处理的元素个数就是str.length-start了,这时候可能发生 offset > str.length-start的情况,所以在处理时需要对offset进行取模的操作。

递归法实现:

上面的代码很容易消除递归,消除递归后实现如下:

细节进一步优化:

offset = offset%(str.length-start);

可替换为

while(offset>=(str.length-start)) {

    offset -= (str.length-start);

}

考虑极端的情况,假如offset=str.length-1.那么第一次交换之后,str.length-start=1了,这时候while将需要执行offset次,O(n)的效率,不过offset收敛是较快的。while循环还是可以提高一点点效率的。

到此,挑战目标基本实现了。

最后看一下九章的一个精华答案

小结

九章的精华答案确实很巧妙,操作次数在2n次。而上面实现的非递归算法,操作次数是比2n要少的。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180717G1RKBZ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券