剑指OfferII-58.左旋转字符串

剑指OfferII-58.左旋转字符串

题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如，输入字符串“abcdefg”和数字2，该函数将返回左旋转两位得到的结果“cdefgab”。

解法一：字符数组

我对于这道题的第一反应是，我可以声明一个char型数组，来对字符串中的字符进行操作，最后再将char型数组转为字符串返回

思路是这样的

• 声明一个index指针，指向char型数组的倒数第k个位置
• 从该指针的位置开始一直到数组的末尾，插入字符串中的前k的字符，也就是待旋转的字符
• 插入完成后，再将字符s剩下的字符依次插入数组中，完成拼接
• 返回

    public String reverseLeftWords(String s, int n) {//申请额外的数组空间char[] ans = new char[s.length()];//申请一个指针，指针指向的位置是char数组对应的前n个字符串末尾的位置int index = s.length()-n;for(int i=0;i<n;i++){//将前n个字符放到char数组末尾ans[index++] = s.charAt(i);}//将后部分要旋转的字符填充完后，再平移前面的字符for(int i=n,j=0;i<s.length();i++){ans[j++] = s.charAt(i);}return new String(ans);}

解法二：原地反转

为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。

那么我们可以想一下上一题目反转字符串中的单词 (opens new window)中讲过，使用整体反转+局部反转就可以实现反转单词顺序的目的。

这道题目也非常类似，依然可以通过局部反转+整体反转 达到左旋转的目的。

步骤如下：

• 1、反转区间为[0,n]的子串
• 2、反转区间为[n,s.length()]的子串
• 3、反转整个字符串

如图所示

    public String reverseLeftWords(String s, int n) {int len = s.length();StringBuilder sb = new StringBuilder(s);//反转区间为[0,n]的子串reverseString(sb,0,n-1);//反转区间为[n,s.length()]的子串reverseString(sb,n,len-1);//反转整个字符串return sb.reverse().toString();}public void reverseString(StringBuilder sb,int start,int end){while(start<end){char temp = sb.charAt(start);sb.setCharAt(start,sb.charAt(end));sb.setCharAt(end,temp);start++;end--;}}