题目
题目来源leetcode
leetcode地址：剑指 Offer 58 - II. 左旋转字符串，难度：简单。
题目描述(摘自leetcode)：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。 示例 1： 输入: s = "abcdefg", k = 2 输出: "cdefgab" 示例 2： 输入: s = "lrloseumgh", k = 6 输出: "umghlrlose" 限制： 1 <= k < s.length <= 10000
本地调试代码：
class Solution { public String reverseLeftWords(String s, int n) { ... } public static void main(String[] args) { System.out.println((new Solution().reverseLeftWords("lrloseumgh", 6))); } }
题解
NO1：反转字符串（核心）
思路： 对原始字符数组进行操作，首先整体进行反转，之后对两个区间进行反转。
代码：未申请额外空间，直接在原始串上操作
public String reverseLeftWords(String s, int n) { //步骤1：整体进行反转，例如："lrloseumgh" => "hgmuesolrl" char[] chars = s.toCharArray(); reverse(chars, 0, chars.length - 1); //步骤2：前后两个区间进行反转 reverse(chars, 0, chars.length - 1 - n);//"hgmuesolrl" => "umghesolrl" reverse(chars, chars.length - n, chars.length - 1);//"umghesolrl" => "umghlrlose" return new String(chars); } /** * 反转字符数组指定范围内容：[begin,end] */ public void reverse(char[] chars, int begin, int end) { for (int i = begin, j = end; i < j; i++, j--) { chars[i] ^= chars[j]; chars[j] ^= chars[i]; chars[i] ^= chars[j]; } }
该解法执行用时2ms，竟然只击败了49.27%，我看了下击败100%的题解，使用的substring与append拼接的方式，在下面NO3中有题解。
NO2：字符数组填充
思路：创建一个新的字符数组，依次填充即可。
代码：时间复杂度O(n)
public String reverseLeftWords(String s, int n) { char[] chars = new char[s.length()]; int k = 0; //非左转的先遍历填充 for (int i = n; i < s.length(); i++) { chars[k++] = s.charAt(i); } //需左转的后遍历填充 for (int i = 0; i < n; i++) { chars[k++] = s.charAt(i); } return new String(chars); }
NO3：借助API（效率最高）
刚开始看到题解我也有点懵，用API反而效率更高啥情况，之后去研究了下，与底层实现有关。该题主要还是核心重点放在NO1题解的思路解法上。
思路：其实与NO2思路填充完全一致，只不过这里使用API来进行字符串截取与拼接。
为什么快？与substring有关，其底层使用的是System.arraycopy进行拷贝。①在NO2中写的for循环拷贝方式若是没有被编译器优化，就是遍历数组操作的字节码，接着执行引擎会根据这些字节码循环获取数组的每个元素再执行拷贝。②而System.arraycopy为JVM内部固有方法，通过手工编写汇编或其他优化方法来进行Java数组拷贝，该方式比for循环更高效尤其数组越大越明显。
参考文章，上述内容摘自：【java】System.arraycopy为什么快
代码：
public String reverseLeftWords(String s, int n) { StringBuilder strBuilder = new StringBuilder(); strBuilder.append(s.substring(n)); strBuilder.append(s.substring(0,n)); return strBuilder.toString(); }
