面试题58 - II. 左旋转字符串

题目：

面试题58 - II. 左旋转字符串

题解：

1. 题解一：字符串切片

2. 题解二：列表遍历拼接

3. 题解三：字符串遍历拼接

4. 题解四：三步翻转法（优先）

算法思想：
1. 第一步：先对前 n 个字符进行翻转；
2. 第二步：然后对后面的部分进行翻转；
3. 第三步：最后对整体进行翻转。

证明：

代码：

1. 代码一：字符串切片

// 方法1：字符串切片
public static String reverseLeftWords(String s, int n) {
    return s.substring(n, s.length()) + s.substring(0, n);
}

2. 代码二：列表遍历拼接

// 方法2：列表遍历拼接
public static String reverseLeftWords(String s, int n) {
    StringBuilder res = new StringBuilder();
    for(int i = n; i < s.length(); i++)
    {
        res.append(s.charAt(i));
    }
    for(int i = 0; i < n; i++)
    {
        res.append(s.charAt(i));
    }
    return res.toString();
}

3. 代码三：字符串遍历拼接

// 方法3：字符串遍历拼接
public static String reverseLeftWords(String s, int n) {
    String res = "";
    for(int i = n; i < s.length(); i++)
    {
        res += s.charAt(i);
    }
    for(int i = 0; i < n; i++)
    {
        res += s.charAt(i);
    }
    return res;
}

4. 代码四：三步翻转法（优先）

public class 面试题58_2 {

    // 方法4：三步翻转法
    public static String reverseLeftWords(String s, int n) {
        char c[] = s.toCharArray();
        reverse(c, 0, n - 1); // 第一步：先对前 n 个字符进行翻转
        reverse(c, n, c.length - 1); // 第二步：然后对后面的部分进行翻转
        reverse(c, 0, c.length - 1); // 第三步：最后对整体进行翻转
        return String.valueOf(c);
    }

    public static void reverse(char c[], int i, int j)
    {
        while(i < j)
        {
            char temp = c[i];
            c[i] = c[j];
            c[j] = temp;
            i++;
            j--;
        }
    }

    public static void main(String[] args) {
        String s1 = "abcdefg";
        int k1 = 2;
        String res1 = reverseLeftWords(s1, k1);
        System.out.println(res1);

        String s2 = "lrloseumgh";
        int k2 = 6;
        String res2 = reverseLeftWords(s2, k2);
        System.out.println(res2);
    }
}

参考：

1. 面试题58 - II. 左旋转字符串（切片 / 列表 / 字符串，清晰图解）
2. java关于substring(a)与substring(a,b)的用法
3. 小技巧----“三步翻转法”
4. 字符串翻转练习—三步翻转法

效率分析：