本节内容

344.反转字符串
541. 反转字符串II
剑指Offer 05.替换空格
151.翻转字符串里的单词
剑指Offer58-II.左旋转字符串

344.反转字符串※

建议：本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下平时刷题什么时候用库函数，什么时候不用库函数

题目链接： https://leetcode.cn/problems/reverse-string/
文章讲解： https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

https://www.yuanql.top/2023/06/14/02_leetcode/344.%20%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2/

题目分析

方法一：双指针，对撞指针，一个指向前面，一个指向最后面，然后交换双方的数值，直到全部交换完毕。
结束条件 left >= right。

方案一

class Solution {
    public void reverseString(char[] s) {
        int left = 0,  // 对撞指针的左指针
                right = s.length - 1;  // 对撞指针的右指针
        char temp;
        while (left <= right) {
            temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:49.5 MB,击败了31.02% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

思想基本与方案一一致。

对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。

以字符串hello为例，过程如下：

代码实现

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

// 第二种方法用temp来交换数值更多人容易理解些
class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while(l < r){
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

541. 反转字符串II※

建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。

题目链接： https://leetcode.cn/problems/reverse-string-ii/
文章讲解： https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html

https://www.yuanql.top/2023/06/14/02_leetcode/541.%20%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%20II/

题目分析

分段进行处理，先将有规律的进行处理，一段一段进行
最后剩余不足的内容进行特殊处理，以此方法来解答此问题。

方案一

class Solution {
    public String reverseStr(String s, int k) {
        int length = s.length(), // 字符串s的长度
                left, right, // 交换字符串使用的双指针
                index = 0; // 记录第几个循环

        char temp; // 交换时的临时变量
        StringBuilder result = new StringBuilder(s);

        for (; (2 * k * (index + 1)) < length; index++) {
            left = 2 * k * index;
            right = 2 * k * index + k - 1;
            reverse(left, right, result);
        }

        if ((2 * k * index + k) < length) {
            left = 2 * k * index;
            right = 2 * k * index + k - 1;
            reverse(left, right, result);
        } else {
            left = 2 * k * index;
            right = length - 1;
            reverse(left, right, result);
        }
        return result.toString();
    }

    private void reverse(int left, int right, StringBuilder result) {
        char temp; // 交换时的临时变量
        while (left < right) {
            temp = result.charAt(left);
            result.setCharAt(left, result.charAt(right));
            result.setCharAt(right, temp);
            left++;
            right--;
        }
    }
}

结果

解答成功:
执行耗时:1 ms,击败了69.91% 的Java用户
内存消耗:42.3 MB,击败了34.14% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

改进

突然发现本次编写的算法还不如以前在写的方法简单： https://www.yuanql.top/2023/06/14/02_leetcode/541.%20%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%20II/

人生是螺旋向前的

class Solution {
    public String reverseStr(String s, int k) {
        char[] sChar = s.toCharArray();
        int n = sChar.length, left = 0;

		// 将数据分段
        do {
            if ((left + k) >= n) {
                func(sChar, left, n - 1);
            } else {
                func(sChar, left, left + k -1);
            }
            left = left + 2 * k;
        } while( left < n );

        return new String(sChar);
    }

	// 交换相关参数
    public void func(char[] s, int left, int right) {
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }
}

代码随想录

https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html

一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

代码实现

//解法一
class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while (start < length) {
            // 找到k处和2k处
            StringBuffer temp = new StringBuffer();
            // 与length进行判断，如果大于length了，那就将其置为length
            int firstK = (start + k > length) ? length : start + k;
            int secondK = (start + (2 * k) > length) ? length : start + (2 * k);

            //无论start所处位置，至少会反转一次
            temp.append(s.substring(start, firstK));
            res.append(temp.reverse());

            // 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
            if (firstK < secondK) { //此时剩余长度一定大于k。
                res.append(s.substring(firstK, secondK));
            }
            start += (2 * k);
        }
        return res.toString();
    }
}

//解法二（似乎更容易理解点）
//题目的意思其实概括为 每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转 
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}


// 解法二还可以用temp来交换数值，会的人更多些
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0;i < ch.length;i += 2 * k){
            int start = i;
            // 判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1,start + k - 1);
            while(start < end){
                
                char temp = ch[start];
                ch[start] = ch[end];
                ch[end] = temp;

                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

剑指Offer 05.替换空格※

建议：对于线性数据结构，填充或者删除，后序处理会高效的多。好好体会一下。

题目链接： https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
文章讲解： https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html

https://www.yuanql.top/2023/06/14/02_leetcode/%E5%89%91%E6%8C%87%20Offer%2005.%20%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC/

题目分析

方案一

class Solution {
    public String replaceSpace(String s) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                result.append("%20");
            } else {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.5 MB,击败了40.78% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

首先扩充数组到每个空格替换成”%20”之后的大小。 (分析了一下其代码，对应java而言，其并不是一个好方法，因为对于java而言，其String 是 final的，如果对其进行修改的话，其都要重新new一个String对象)

然后从后向前替换空格，也就是双指针法，过程如下：

i指向新长度的末尾，j指向旧长度的末尾。

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

代码实现

//使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
public static String replaceSpace(String s) {
        if (s == null) {
            return null;
        }
        //选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
        //使用 sb 逐个复制 s ，碰到空格则替换，否则直接复制
        for (int i = 0; i < s.length(); i++) {
            //s.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
            //if (" ".equals(String.valueOf(s.charAt(i)))){}
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

//方式二：双指针法
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

151.翻转字符串里的单词※

建议：这道题目基本把刚刚做过的字符串操作都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。

题目链接： https://leetcode.cn/problems/reverse-words-in-a-string/
文章讲解： https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html

https://www.yuanql.top/2023/06/14/02_leetcode/151.%20%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E5%8D%95%E8%AF%8D/

题目分析

将字符串 s 从后向前遍历，设置一个标志位来确认空格与非空格的转换时机。
因为是倒叙进行遍历的，所以得到数据之后要对其进行反转操作，在将其放入到result中。

方案一

class Solution {
    public String reverseWords(String s) {
        StringBuilder result = new StringBuilder(),
                temp = new StringBuilder();
        boolean flag = false;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                if (flag) {
                    result.append(temp.reverse());
                    result.append(' ');
                    temp = new StringBuilder();
                }
                flag = false;
            } else {
                flag = true;
                temp.append(s.charAt(i));
            }
        }
        if (flag) {
            result.append(temp.reverse());
            temp = new StringBuilder();
        } else {
            result.deleteCharAt(result.length() - 1);
        }
        return result.toString();
    }
}

结果

解答成功:
执行耗时:4 ms,击败了80.99% 的Java用户
内存消耗:40.9 MB,击败了67.44% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html

这道题目可以说是综合考察了字符串的多种操作。

一些同学会使用split库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了，失去了它的意义。

所以这里我还是提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。

不能使用辅助空间之后，那么只能在原字符串上下功夫了。

想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

所以解题思路如下：

移除多余空格
将整个字符串反转
将每个单词反转

举个例子，源字符串为：”the sky is blue “

移除多余空格 : “the sky is blue”
字符串反转：”eulb si yks eht”
单词反转：”blue is sky the”

这样我们就完成了翻转字符串里的单词。

代码实现

class Solution {
   /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }



    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
        // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

//解法二：创建新字符数组填充。时间复杂度O(n)
class Solution {
    public String reverseWords(String s) {
        //源字符数组
        char[] initialArr = s.toCharArray();
        //新字符数组
        char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回
        int newArrPos = 0;
        //i来进行整体对源字符数组从后往前遍历
        int i = initialArr.length-1;
        while(i>=0){
            while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格
            //此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
            int right = i;
            while(i>=0 && initialArr[i] != ' '){i--;} 
            //指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
            for (int j = i+1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' ';//空格
                }
            }
        }
        //若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr,0,newArrPos-1);
        }
    }
}

//解法三：双反转+移位，在原始数组上进行反转。空间复杂度O(1)
class Solution {
    /**
     * 思路：
     *	①反转字符串  "the sky is blue " => " eulb si yks eht"
     *	②遍历 " eulb si yks eht"，每次先对某个单词进行反转再移位
     *	   这里以第一个单词进行为演示：" eulb si yks eht" ==反转=> " blue si yks eht" ==移位=> "blue si yks eht"
     */
    public String reverseWords(String s) {
        //步骤1：字符串整体反转（此时其中的单词也都反转了）
        char[] initialArr = s.toCharArray();
        reverse(initialArr, 0, s.length() - 1);
        int k = 0;
        for (int i = 0; i < initialArr.length; i++) {
            if (initialArr[i] == ' ') {
                continue;
            }
            int tempCur = i;
            while (i < initialArr.length && initialArr[i] != ' ') {
                i++;
            }
            for (int j = tempCur; j < i; j++) {
                if (j == tempCur) { //步骤二：二次反转
                    reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题
                }
                //步骤三：移动操作
                initialArr[k++] = initialArr[j];
                if (j == i - 1) { //遍历结束
                    //避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界
                    if (k < initialArr.length) {
                        initialArr[k++] = ' ';
                    }
                }
            }
        }
        if (k == 0) {
            return "";
        } else {
            //参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
            return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
        }
    }

    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];
        }
    }
}

/*
 * 解法四：时间复杂度 O(n)
 * 参考卡哥 c++ 代码的三步骤：先移除多余空格，再将整个字符串反转，最后把单词逐个反转
 * 有别于解法一 ：没有用 StringBuilder  实现，而是对 String 的 char[] 数组操作来实现以上三个步骤
 */
class Solution {
    //用 char[] 来实现 String 的 removeExtraSpaces，reverse 操作
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1.去除首尾以及中间多余空格
        chars = removeExtraSpaces(chars);
        //2.整个字符串反转
        reverse(chars, 0, chars.length - 1);
        //3.单词反转
        reverseEachWord(chars);
        return new String(chars);
    }

    //1.用 快慢指针 去除首尾以及中间多余空格，可参考数组元素移除的题解
    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //先用 fast 移除所有空格
            if (chars[fast] != ' ') {
                //在用 slow 加空格。 除第一个单词外，单词末尾要加空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //相当于 c++ 里的 resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }

    //双指针实现指定范围内字符串反转，可参考字符串反转题解
    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            System.out.println("set a wrong right");
            return;
        }
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

    //3.单词反转
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}

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

建议：题解中的解法如果没接触过的话，应该会想不到

题目链接： https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
文章讲解： 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

https://www.yuanql.top/2023/06/15/02_leetcode/%E5%89%91%E6%8C%87%20Offer%2058%20-%20II.%20%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2/

题目分析

方案一

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder result = new StringBuilder(s);

        for (int i = 0; i < n; i++) {
            result.append(result.charAt(0));
            result.deleteCharAt(0);
        }

        return result.toString();
    }
}

结果

解答成功:
执行耗时:10 ms,击败了6.18% 的Java用户
内存消耗:42.3 MB,击败了30.40% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( m )

方案一的改进

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder result = new StringBuilder();

        for (int i = n; i < s.length(); i++) {
            result.append(s.charAt(i));
        }

        for (int i = 0; i < n; i++) {
            result.append(s.charAt(i));
        }

        return result.toString();
    }
}

结果

解答成功:
执行耗时:4 ms,击败了31.82% 的Java用户
内存消耗:42.5 MB,击败了13.53% 的Java用户

代码随想录

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

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

不能使用额外空间的话，模拟在本串操作要实现左旋转字符串的功能还是有点困难的。

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

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

具体步骤为：

反转区间为前n的子串
反转区间为n到末尾的子串
反转整个字符串

最后就可以达到左旋n的目的，而不用定义新的字符串，完全在本串上操作。

例如：示例1中输入：字符串abcdefg，n=2

代码实现

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverseString(sb,0,n-1);
        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--;
            }
        }
}

总结

字符串涉及到字符串位置交换的时候，为了使得空间复杂度为 O(1)，可以多次反转以实现其功能。‘

在这篇文章344.反转字符串 (opens new window)，第一次讲到反转一个字符串应该怎么做，使用了双指针法。

然后发现541. 反转字符串II (opens new window)，这里开始给反转加上了一些条件，当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章。

后来在151.翻转字符串里的单词 (opens new window)中，要对一句话里的单词顺序进行反转，发现先整体反转再局部反转是一个很妙的思路。

最后再讲到本题，本题则是先局部反转再整体反转，与151.翻转字符串里的单词 (opens new window)类似，但是也是一种新的思路。

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

07、第四章字符串part01

http://yuanql.top/2023/07/19/02_1_代码随想录算法训练营18期/07、第四章字符串part01/

作者

Qingli Yuan

发布于

2023年7月19日

许可协议

2023年7月19日每日一题--874. 模拟行走机器人上一篇

2023年7月18日每日一题--1851. 包含每个查询的最小区间下一篇

07、第四章 字符串part01

本节内容

344.反转字符串※

题目分析

方案一

结果

分析

代码随想录

代码实现

541. 反转字符串II※

题目分析

方案一

结果

分析

改进

代码随想录

代码实现

剑指Offer 05.替换空格※

题目分析

方案一

结果

分析

代码随想录

代码实现

151.翻转字符串里的单词※

题目分析

方案一

结果

分析

代码随想录

代码实现

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

题目分析

方案一

结果

分析

方案一的改进

结果

代码随想录

代码实现

总结

07、第四章字符串part01