程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 左旋字符串

左旋字符串

編輯:C++入門知識

 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^2),這跟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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved