剑指58-II 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
 限制：
1 <= k < s.length <= 10000

思路

「不能申请额外空间，只能在本串上操作」。

不能使用额外空间的话，模拟在本串操作要实现左旋转字符串的功能还是有点困难的。

可以通过局部反转+整体反转 达到左旋转的目的。

具体步骤为：

1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串

「最后就可以得到左旋n的目的，而不用定义新的字符串，完全在本串上操作。」

例如 ：示例1中 输入：字符串abcdefg，n=2

1. 反转区间为前n的子串 ：bacdefg
2. 反转区间为n到末尾的子串：bagfedc
3. 反转整个字符串：cdefgab

最终得到左旋2个单元的字符串：cdefgab

代码

public class 左旋转字符串 {
    public static void main(String[] args) {
        String s = "abcdefg";
        char[] chars = s.toCharArray();
        String s1 = new String(chars);
        System.out.println("s1"+s1);

        reverseString(chars,0,1);
        String s2 = new String(chars);
        System.out.println("s2"+s2);

        reverseString(chars,2,chars.length-1);
        String s3 = new String(chars);
        System.out.println("s3"+s3);

        reverseString(chars,0,chars.length-1);
        String s4 = new String(chars);
        System.out.println("s4"+s4);

    }
    // 反转区间为前n的子串 ：bacdefg
    // 反转区间为n到末尾的子串：bagfedc
    // 反转整个字符串：cdefgab
    public static void  reverseString(char[] chars,int start,int end) {
        char[] c = new char[chars.length];
        for (int i = start, j = end; i < j; i++, j--) {
            char temp = chars[i];
            chars[i] =  chars[j];
            chars[j]= temp;
        }
    }

}

---