Q 左旋轉字符串
* 題目：定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。
* 如把字符串abcdef左旋轉2位得到字符串cdefab。
* 請實現字符串左旋轉的函數。要求時間對長度為n的字符串操作的復雜度為O(n)，輔助內存為O(1)。
C++實現：
解法一：不考慮時間和空間的限制。設移動的位數為k。則循環k次，每次移動1位。這樣的空間復雜度是O(1)，時間復雜度是O(n*k)。如果k小於n，則O(n^2)。
解法二：最直接的方法。開辟一塊大小為n的內存，將前k個字符拷貝到後k個位置。將後面的n-k個字符拷貝到新空間前n-k個位置。這種方法時間復雜度為O(n)，空間復雜度為O(n)。
解法三：反轉前k個字符，然後反轉後n-k個字符，最後反轉整個字符串。時間復雜度為O(n)，空間復雜度為O(1)。
解法四：參考《STL源碼剖析》中算法一章的rotate()方法。假如字符串為abcdefgh，需要左移3位。令first指向第一個元素a，令i = middle指向第k+1個元素d(迭代器的前開後閉原則)。
第一步：defabcgh (abc先結束，下一步目的是abc和def後面的元素gh整體交換)
第二步：defghcab (gh先結束， 下一步目的是c和原gh後的字符(結束符)進行交換，即可看成c與ab進行交換)
第三步：defghacb (c先結束， 下一步目的是c和a後面的元素b交換)
第四步：defghabc (結束)
這種方法的時間復雜度為O(n)，空間復雜度為O(1)。
解法一實現：
abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。
RightShift(int* arr, int N, int K)
{
while(K--)
{
int t = arr[N - 1];
for(int i = N - 1; i > 0; i --)
arr[i] = arr[i - 1];
arr[0] = t;
}
}
解法三實現：
假設原數組序列為abcd1234，要求變換成的數組序列為1234abcd，即循環右移了4位。比較之後，不難看出，其中有兩段的順序是不變的：1234和abcd，可把這兩段看成兩個整體。右移K位的過程就是把數組的兩部分交換一下。
變換的過程通過以下步驟完成：
逆序排列abcd：abcd1234 → dcba1234；
逆序排列1234：dcba1234 → dcba4321；
全部逆序：dcba4321 → 1234abcd。
偽代碼可以參考清單2-35。
//代碼清單2-35
Reverse(int* arr, int b, int e)
{
for(; b < e; b++, e--)
{
int temp = arr[e];
arr[e] = arr[b];
arr[b] = temp;
}
}
RightShift(int* arr, int N, int k)
{
K %= N;
Reverse(arr, 0, N – K - 1);
Reverse(arr, N - K, N - 1);
Reverse(arr, 0, N - 1);
}
另外一種方法：
大家開始可能會有這樣的潛在假設，K<N。事實上，很多時候也的確是這樣的。但嚴格來說，我們不能用這樣的“慣性思維”來思考問題。
尤其在編程的時候，全面地考慮問題是很重要的，K可能是一個遠大於N的整數，在這個時候，上面的解法是需要改進的。
仔細觀察循環右移的特點，不難發現：每個元素右移N位後都會回到自己的位置上。因此，如果K > N，右移K-N之後的數組序列跟右移K位的結果是一樣的。
進而可得出一條通用的規律：
右移K位之後的情形，跟右移K’= K % N位之後的情形一樣，如代碼清單2-34所示。
//代碼清單2-34
RightShift(int* arr, int N, int K)
{
K %= N;
while(K--)
{
int t = arr[N - 1];
for(int i = N - 1; i > 0; i --)
arr[i] = arr[i - 1];
arr[0] = t;
}
}
可見，增加考慮循環右移的特點之後，算法復雜度降為O（N^２），這跟K無關，與題目的要求又接近了一步。但時間復雜度還不夠低，接下來讓我們繼續挖掘循環右移前後，數組之間的關聯。
java實現：
public class LeftRotateString {
public static void main(String[] args) {
String data = "abcdef";
String re = leftRotateString(data, 2);
System.out.println(re);
}
/*
* abcdef->ab.cdef->ba.fedc->cdefab
*/
public static String leftRotateString(String str, int n) {
if (str == null || str.length() == 0) {
return str;
}
if (n <= 0 || n >= str.length()) {
return str;
}
int begin = 0;
int end = str.length() - 1;
char[] letters = str.toCharArray();
reverseString(letters, begin, n - 1);
reverseString(letters, n, end);
reverseString(letters, begin, end);
return new String(letters);
}
// public static String reverseString(String str,int begin,int end){
public static String reverseString(char[] letters, int begin, int end) {
/*
* of course we can do it like this: StringBuilder sb=new
* StringBuilder(str); sb.reverse().toString(); but we are learning
* algorithm so let's 'reinvent the wheel'.
*/
if (begin >= end) {
return null;
}
for (int i = begin, j = end; i < j; i++, j--) {
char tmp = letters[i];
letters[i] = letters[j];
letters[j] = tmp;
}
return new String(letters);
}
}
另外值得提一下的是，利用java實現字符串反轉，有多種方式，如下：
import java.util.Stack;
public class ReverseString {
public String reverse(String str) {
StringBuffer sb = new StringBuffer();
for (int i = str.length() - 1; i >= 0; i--) {
sb.append(str.charAt(i));
}
return sb.toString();
}
public static String reverse1(String s) {
int length = s.length();
if (length <= 1)
return s;
String left = s.substring(0, length / 2);
String right = s.substring(length / 2, length);
return reverse1(right) + reverse1(left);
}
public static String reverse2(String s) {
int length = s.length();
String reverse = "";
for (int i = 0; i < length; i++)
reverse = s.charAt(i) + reverse;
return reverse;
}
public static String reverse3(String s) {
char[] array = s.toCharArray();
String reverse = "";
for (int i = array.length - 1; i >= 0; i--)
reverse += array[i];
return reverse;
}
public static String reverse4(String s) {
return new StringBuffer(s).reverse().toString();
}
public static String reverse5(String orig) {
char[] s = orig.toCharArray();
int n = s.length - 1;
int halfLength = n / 2;
for (int i = 0; i <= halfLength; i++) {
char temp = s[i];
s[i] = s[n - i];
s[n - i] = temp;
}
return new String(s);
}
public static String reverse6(String s) {
char[] str = s.toCharArray();
int begin = 0;
int end = s.length() - 1;
while (begin < end) {
str[begin] = (char) (str[begin] ^ str[end]);
str[end] = (char) (str[begin] ^ str[end]);
str[begin] = (char) (str[end] ^ str[begin]);
begin++; www.2cto.com
end--;
}
return new String(str);
}
public static String reverse7(String s) {
char[] str = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length; i++)
stack.push(str[i]);
String reversed = "";
for (int i = 0; i < str.length; i++)
reversed += stack.pop();
return reversed;
}
/*
public String reverse8(String str) {
char[] cstr = str.toCharArray();
int n = cstr.length;
for(int i=0; i<n/2; i++) {
char temp = cstr[i];
cstr[i] = cstr[n-i-1];
cstr[n-i-1] = temp;
}
return new String(cstr);
}
*/
public static void main(String[] args) {
// String str = "abcdef";
// System.out.println(new ReverseString().reverse8(str));
}
}
作者：mingyunduoshou
