剑指 Offer - 43 - 左旋转字符串

Question

题目

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出。例如，字符序列 S='abcXYZdef' ,要求输出循环左移 3 位后的结果，即 XYZdefabc 。是不是很简单？OK，搞定它！

解析

两种思路。

1、思路一

简单的做法：

• 直接将 [n, str.length()] 先加到 res 字符串；
• 然后将 [0, n] 之间的字符串加入到 res 即可；

public class Solution {
    public String LeftRotateString(String str, int n) {
        if(str == null ||str.length() == 0 )
            return "";
        if(n == str.length() || n == 0)
            return str;
        StringBuilder res = new StringBuilder(str.substring(n));
        res.append(str.substring(0, n));
        return res.toString();
    }
}

2、思路二

剑指 Offer 的解法：

• 将字符串分成两部分，第一部分记为前 n 个字符部分记为 A ，后面的部分记为 B ；
• 其实这个题目就是要你从 AB 转换到 BA ；
• 做法就是 (1)、先将 A 部分字符串翻转；(2)、然后将 B 字符串翻转；(3)、最后将整个字符串翻转；
• 也就是(A^TB^T)^T = BA；

代码:

public class Solution {
    public void reverse(char[] chs, int L, int R) {
        for (; L < R; L++, R--) {
            char c = chs[L];
            chs[L] = chs[R];
            chs[R] = c;
        }
    }
    public String LeftRotateString(String str, int n) {
        if (str == null || str.length() == 0) return "";
        if (n == str.length() || n == 0)
            return str;
        char[] chs = str.toCharArray();
        reverse(chs, 0, n - 1);
        reverse(chs, n, str.length() - 1);
        reverse(chs, 0, str.length() - 1);
        return new String(chs);
    }
}