旋轉字元串

題目描述：

定義字元串的左旋轉操作：把字元串前面的若幹個字元移動到字元串的尾部。如把字元串abcdef左旋轉2位得到字元串cdefab。請實作字元串左旋轉的函數，要求對長度為n的字元串操作的時間複雜度為O(n)，空間複雜度為O(1)。

類似的問題，設計一個算法，把一個含有N個元素的數組循環右移K位，要求時間複雜度為O（N），且隻允許使用兩個附加變量。

解法一：分析：我們先試驗簡單的辦法，可以每次将數組中的元素右移一位，循環K次。

abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。

import junit.framework.TestCase;public class ReserveString extends TestCase {
 public String RightShift(String s, int K) {
  int length = s.length(); // 擷取字元串長度
  char c[] = new char[s.length()]; // 擷取字元串數組
  for (int i = 0; i < s.length(); i++) {
   c[i] = s.charAt(i);
  }
  while (K > 0) { // 一個字元一個字元移動
   K--;
   char t = c[length - 1];
   for (int i = length - 1; i > 0; i--)
    c[i] = c[i - 1];
   c[0] = t;
  }
  return new String(c);
 } public void test() {
  String s = "1234abcd";
  System.out.println("翻轉以後的字元串為" + RightShift(s, 4));
 }
}      

雖然這個算法可以實作數組的循環右移，但是算法複雜度為O（K * N），不符合題目的要求，要繼續探索。

解法一改進：大家開始可能會有這樣的潛在假設，K<N。事實上，很多時候也的确是這樣的。但嚴格來說，我們不能用這樣的“慣性思維”來思考問題。尤其在程式設計的時候，全面地考慮問題是很重要的，K可能是一個遠大于N的整數，在這個時候，上面的解法是需要改進的。仔細觀察循環右移的特點，不難發現：每個元素右移N位後都會回到自己的位置上。是以，如果K > N，右移K-N之後的數組序列跟右移K位的結果是一樣的，進而可得出一條通用的規律：

右移K位之後的情形，跟右移K’= K % N位之後的情形一樣，

import junit.framework.TestCase;

public class ReserveString extends TestCase {

  public String RightShift(String s, int K) {
    int length=s.length();                         //擷取字元串長度
    K%=length;                                     //右移K位之後的情形，跟右移K’= K % N位之後的情形一樣，
    char c[] = new char[s.length()];               //擷取字元串數組
    for (int i = 0; i < s.length(); i++) {
      c[i] = s.charAt(i);
    }
    while (K > 0) {                                //一個字元一個字元移動
      K--;
      char t = c[length - 1];
      for (int i = length - 1; i > 0; i--)
        c[i] = c[i - 1];
      c[0] = t;
    }
    return new String(c);
  }

  public void test() {
    String s = "1234abcd";
    System.out.println("翻轉以後的字元串為"+RightShift(s,43333333));
  }

}      

可見，增加考慮循環右移的特點之後，算法複雜度降為O（N^２），這跟K無關，與題目的要求又接近了一步。但時間複雜度還不夠低，接下來讓我們繼續挖掘循環右移前後，數組之間的關聯。 

解法二：三次翻轉算法

假設原數組序列為abcd1234，要求變換成的數組序列為1234abcd，即循環右移了4位。比較之後，不難看出，其中有兩段的順序是不變的：1234和abcd，可把這兩段看成兩個整體。右移K位的過程就是把數組的兩部分交換一下。

變換的過程通過以下步驟完成：

 逆序排列abcd：abcd1234 → dcba1234；

 逆序排列1234：dcba1234 → dcba4321；

 全部逆序：dcba4321 → 1234abcd。

public void Reverse( char arr[], int b, int e)
  {
       for(; b < e; b++, e--)
       {
            char temp = arr[e];
            arr[e] = arr[b];
            arr[b] = temp;
       }
  }

  public String  RightShift_Three(String s, int K)
  {    int N=s.length();
       K %= N;
       char c[] = new char[s.length()];               //擷取字元串數組
      for (int i = 0; i < s.length(); i++) {
        c[i] = s.charAt(i);
      }
       Reverse(c, 0, N-K-1);
       Reverse(c, N - K, N - 1);
       Reverse(c, 0, N - 1);
       return new String(c) ;
  }      

這樣，我們就可以線上性時間内實作右移操作了。

稍微總結下：

1、第一個想法 ，是一個字元一個字元的右移，是以，複雜度為O（N*K）

2、後來，它改進了，通過這條規律：右移K位之後的情形，跟右移K’= K % N位之後的情形一樣

複雜度為O（N^2）