剑指Offer58-II.左旋转字符串

水深无声 2023-10-13 22:07 30阅读 0赞

### 剑指Offer58-II.左旋转字符串 ###

*  题干背景
 *  重要思路
 *  代码实现
 *   *  按思路的方案一
     *  步骤反转效果相同的方案二

# 题干背景 #

[力扣入口-剑指Offer58-II.左旋转字符串][-_Offer58-II.]

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

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

示例 2：  
输入: s = “lrloseumgh”, k = 6  
输出: “umghlrlose”

限制：  
1 <= k < s.length <= 10000

# 重要思路 #

1.  解析中的代码是为了满足本题提升的难度：**不能申请额外空间，只能在本串上操作**。
2.  具体步骤：反转区间为前n的子串 -》反转区间为n到末尾的子串 -》反转整个字符串，或者整个过程反过来也是可以的。  
    ![在这里插入图片描述][87643975b28b4690bfdf8107e4b062e2.png]

# 代码实现 #

## 按思路的方案一 ##

注意这里使用了StringBuilder里的setCharAt和reverse。

// 剑指Offer58-II.左旋转字符串
    public String reverseLeftWords(String s, int n){
        
        int len = s.length();
        StringBuilder builder = new StringBuilder(s);
        revString(builder, 0, n-1);
        revString(builder, n, len-1);
        return builder.reverse().toString();
    }
    
    public void revString(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--;
        }
    }

## 步骤反转效果相同的方案二 ##

// 剑指Offer58-II.左旋转字符串 - 解法二
    // 空间复杂度：O(1)。用原始数组来进行反转操作
    // 思路为：先整个字符串反转，再反转前面的，最后反转后面 n 个
    public String reverseLeftWords(String s, int n) {
        
        char[] chars = s.toCharArray();
        rev(chars, 0, chars.length - 1);
        rev(chars, 0, chars.length - 1 - n);
        rev(chars, chars.length - n, chars.length - 1);
        return new String(chars);
    }
    
    public void rev(char[] chars, int left, int right){
        
        while(left < right){
        
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

**参考资料**：[题目：剑指Offer58-II.左旋转字符串][Offer58-II.]

[-_Offer58-II.]: https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
[87643975b28b4690bfdf8107e4b062e2.png]: https://img-blog.csdnimg.cn/87643975b28b4690bfdf8107e4b062e2.png
[Offer58-II.]: https://programmercarl.com/%E5%89%91%E6%8C%87Offer58-II.%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC