算法：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要少的。