旋转字符串

一：问题描述：

编程珠玑第二章的第二个问题是字符串（或者理解为向量）旋转问题，具体描述如下：

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();
 }