旋转字符串
一：问题描述：
编程珠玑第二章的第二个问题是字符串（或者理解为向量）旋转问题，具体描述如下：
rotate a one-dimensional vector of n elements left by i positions. eg: with n = 8; i = 3, the vector abcdefgh is rotated to defghabc.
这个问题在编程之美中也出现了，问题描述：
设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O（N），且只允许使用两个附加变量。
下面的内容主要参考了编程之美中的几个算法，编程珠玑中的思想，以及网上牛人的总结，当然这些之间都是有很大关联的。
二：问题分析与解答：
1、
看到这个问题后我的第一印象是采用循环移位：
把字符用二进制表示，即0101的字符串，然后进行循环移位，这个是可行的，自己还去找了下循环移位如何实现，下面是c语言循环移位的一种实现：
假设串的长度是N，要循环移位k位，那么：
循环右移：(a>>k) | (a<<(N-k)) //即a先右移k位，然后再左移N-k位，然后进行或|运算就实现了循环右移。
循环左移：(a<<k) | (a>>(N-k)) //即a先左移k位，然后再右移N-k位，然后进行或运算就实现了循环左移
当然，如果对于数组的话，这个方法是不太方便的，对于字符串倒是可以。
2、另外一种比较直接的想法就是直接进行交换
比如要将前i个数移到后面的位置即从abcdefgh ---> defghabc。那么就可以认为是进行三次移动，类似插入排序。
具体步骤是先将a备份，然后让bcdefgh向左移动一个位置，如此循环下去，很容易知道这个思想的时间复杂度是O(i*n)
具体实现如下：
void rotate(int *array, int len, int pos)
{
int temp ;
while(pos—)
{
temp = array[0];
for(k=1; k<n; k++)
{
array[k-1] = array[k];
}
array[n-1] = temp;
}
}
显然这样的方法是可行的，但复杂度不满足要求。
3、下面的这种方法很是巧妙，而且很高效
利用的思想是(x^r y^r)^r = yx (其中x^r表示对x进行逆序操作)
例如：字符串是abcdefgh，i=3
那么可以看作x=abc；y=defgh
则x^r = cba; y^r = hgfed（类似线性代数的转置吧）
则(x^r y^r) = cbahgfed
因此(x^r y^r)^r = defghabc = yx
因此需要是三次反转就可以实现字符串的旋转了，用伪代码表示为：
reverse(0, i-1);
reverse(i, n-1);
reverse(0,n-1);
其中reverse(x, y)表示反转从x到y的字符串。因此对应上面的例子就是
reverse(0,2);
reverse(3, 7);
reverse(0,7);
而反转就是一个小的循环，下面是reverse的一个简化实现：
可以从上图知道，这个算法的时间复杂度是线性的，满足要求。
4、下面还有几个神奇的算法思想值得学习和分享
a:假设i＜n-i，最容易想到的是，前i个字符串最终一定要放在最后面i个位置。把这前后两个i位的字符串进行交换，则接下来的问题变成对前面长度为n-i的字符串进行同样的操作。如果i>n-i，则交换后变成对后面n-i个字符串进行操作。
这个思想在Gries and Mills的报告中称为Successive swap
伪代码如下：
if(i == 0 || i == n)
return;
k = p = i;
j = n –p;
while(k != j)
{
if(k > j)
swap(p-k, p, j);
k –= j;
else
swap(p-k, p+j-k; k);
j –= k;
}
swap(p-k, p, k);
其中swap(a, b, m)表示交换x[a…a+m-1] 和 x[b…b+m-1]
下面是一个简单的实现：
b、编程珠玑中的所谓juggling code，在课后习题中利用了gcd（最大公约数）
juggling code是看明白了，但为什么利用gcd确实不太明白啊，而且STL中也是利用的gcd，后面还得研究研究。
juggling的思想如下：先将x[0]保存起来，然后进行下面的操作:x[i]--->x[0]; x[2i]--->x[i]; x[3i]--->x[2i]…最后将x[0]的备份放到x[ki]的位置。如果这个过程没有移动所有的元素，那么继续保存x[1]重复上面的操作，当然是将x[i+1]--->x[1]; x[2i+1]--->x[i+1]…
这种思想是比较容易理解的，但后面利用了gcd的思想，没有深入的理解。
c、STL中的rotate
在C++中STL中实现了rotate操作，说实话原理我还真没看明白--！是利用了上面的b思想，而且利用的gcd，这应该是有一定的数学因素吧。
改天再研究研究~~~
参考文献：
1、编程珠玑
2、http://blog.csdn.net/v_JULY_v/archive/2011/04/14/6322882.aspx 程序员编程艺术（算法卷）：第一章、左旋转字符串 这篇文章基本上是总结了所有的思路，赞LZ。同时这个博客收集了大量的经典问题而且讨论的很深入，值得自己研究学习啊
3、http://philoscience.iteye.com/blog/1010964 这篇文章参考了Gries and Mills的一篇总结报告，＜swap section>（其实也是编程珠玑上提到的）但说时候这篇文章我一直没找到，注册了个帐号想从LZ这里下，但要注册三天才可以下载 –！
4、编程之美数组循环移位的章节
5、网络上其他牛人的blog，这里不再一一列出
另外相关的java实现：
/**
* 将"abc1234" 循环右移4位 or 将"abc1234"循环左移3位
*
* 时间复杂度 O(n2)
* @param target
* @param k
*/
public static void shift(char[] target,int k){
int length = target.length;
int m = k % length;
while(k-- > 0){
char f = target[length-1];
for(int i=length-1;i>0;i--){
target[i]=target[i-1];
}
target[0] = f;
}
System.out.println(String.copyValueOf(target));
}
/**
* 将"abc1234" ---> "1234abc"
* 高效算法：abc -- x 1234 -- y 将x y -- > y x 即可
* (x^r y^r)^r = yx ： x^r cba y^r 4321 -- (cba4321) ^ r ---> 1234abc 哈哈
* @param target
* @param k
*/
public static void advanceShift(char[] target,int k){
char[] x = Arrays.copyOfRange(target, 0, 3);
char[] y = Arrays.copyOfRange(target, 3, target.length);
x = reverce(x);
y = reverce(y);
target = reverce((String.copyValueOf(x)+String.copyValueOf(y)).toCharArray());
System.out.println(String.copyValueOf(target));
}
private static char[] reverce(char[] target){
StringBuffer sb = new StringBuffer();
for(int i=target.length-1;i>=0;i--){
sb.append(target[i]);
}
return sb.toString().toCharArray();
}