给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串“cdefab”。请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1)。

Java 代码

public static void main(String[] args) {
        String s = "abcdef";
        char[] chars = s.toCharArray();
        leftRotateString(chars, s.length(), 2);//
    }

    public static void reverseString(char[] chars, int from, int to){
       // System.out.println("start: from= " + from + " ,to= "+ to);
        while (from < to) {
            System.out.println("ing: from= " + from + " ,to= "+ to);
            char t = chars[from];
            // System.out.println("while->t:" + t);
            chars[from++] = chars[to];
            chars[to--] = t;
            System.out.println("ing-2: from= " + from + " ,to= "+ to);
            System.out.println(chars);
        }
    }

    /**
     *
     * @param s 字符数组
     * @param n 字符串长度
     * @param m 要移动的字符长度
     */
    public static void leftRotateString(char[] s,int n,int m) {
        m %= n;               //若要左移动大于n位,那么和%n 是等价的
        System.out.println("n= " + n + " m= "+ m);
        reverseString(s, 0, m - 1); //反转[0..m - 1],套用到上面举的例子中,就是X->X^T,即 abc->cba
        //System.out.println(s);
        reverseString(s, m, n - 1); //反转[m..n - 1],例如Y->Y^T,即 def->fed
        //System.out.println(s);
        reverseString(s, 0, n - 1); //反转[0..n - 1],即如整个反转,(X^TY^T)^T=YX,即 cbafed->defabc。
        //System.out.println(s);
    }

将字符串 "abcdef" 前两个字符挪到字符串后面:“cdefab”。

  1. 将字符串 abcdef 分为两部分,ab、cdef;
  2. 将 ab 变为 ba;
  3. 将 cdef 变为 fedc,此时字符串为 bafedc;
  4. 将 bafedc 倒转过来即为 cdefba

上面代码输出结果为:

n= 6 m= 2
ing: from= 0 ,to= 1
ing-2: from= 1 ,to= 0
bacdef
ing: from= 2 ,to= 5
ing-2: from= 3 ,to= 4
bafdec
ing: from= 3 ,to= 4
ing-2: from= 4 ,to= 3
bafedc
ing: from= 0 ,to= 5
ing-2: from= 1 ,to= 4
cafedb
ing: from= 1 ,to= 4
ing-2: from= 2 ,to= 3
cdfeab
ing: from= 2 ,to= 3
ing-2: from= 3 ,to= 2
cdefab

再放一个多此一举的图片:


原文:https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/01.01.html