左旋字符串

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;

publ

补充：软件开发 , C++ ,