代码随想录刷题笔记（DAY 8）

今日总结：最后一道题解决的比较糟糕，后续会补上新解法，今天还是将中心放在了前端。

Day 8

01. 反转字符串（No. 344）

题目链接

代码随想录题解

1.1 题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：

输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

1.2 笔记

非常简单的一道题目，而且题目给的就是一个 char 数组，简单的回顾一下反转的写法

char temp = s[left];
s[left] = s[right];
s[right] = temp;

反转的次数为 s.length / 2 向下取整，写出代码

1.3 代码

class Solution {
    public void reverseString(char[] s) {
        int n = s.length / 2;
        int left = 0;
        int right = s.length - 1;
        while (n-- > 0) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

02. 反转字符串 II（No. 541）

题目链接

代码随想录题解

2.1 题目

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：

输入：s = “abcd”, k = 2
输出：“bacd”

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

2.2 笔记

这道题比前面那个复杂的多，有很多条件需要考虑，我们先来尝试读懂题意：

我们可以声明两个指针，这两个指针表明一个 [nk, n2k] 的范围，这个范围不断向后移动，每次出现一次这个范围我们就将前 k 个元素反转。

比如第一次反转的是 [0, k] 第二次是 [2k + 1, 3k]

前面的都很好理解，就是当最后一个 2k 跃出数组的时候（比如上图的 8k），对于这一组的 7k 就要分两种情况了

• 如果 7k 也在数组外的话，我们就将 6k + 1 到数组结尾的内容全部反转
• 否则就只反转 [6k + 1, 7k]的部分。

看了上面的步骤，我们需要一个函数，能够将我们指定起点到指定终点的内容执行反转，有了上题的经验，这个应该很容易写出来

    public void reverseCharArrayByIndex(int indexLeft, int indexRight) {
        // 反转在范围内的下标
        int length = (indexRight - indexLeft + 1) / 2;
        while (length-- > 0) {
            char temp = x[indexLeft];
            x[indexLeft] = x[indexRight];
            x[indexRight] = temp;
            indexLeft++;
            indexRight--;
        }
    }

接下来，就要用两个指针去遍历了，第一个指针right每次移动 2k 的距离，第二个指针指向的是 right - 2k + 1 的位置这个 +1 就是我们上面比如 2k + 1 中要加的这个 1，是为了更新范围的。

循环结束的时间就是当我们发现 right 跃出数组的时候，这时候我们就可以对上面出现的两种情况来分别求解了

2.3 代码

class Solution {
    char[] x;
    public String reverseStr(String s, int k) {
        x = s.toCharArray();
        int left = 0; // k 处的下标
        int right = (2 * k - 1); // 2k 处的下标
        int n = 1;// 记录是第几个 2k
        while (true) {
            // 表示遍历到终点了
            if (right >= x.length - 1) {
                // 最后一次处理放在循环结束后做
                break;
            }
            reverseCharArrayByIndex(left, left + k - 1);
            n++; // 表明下一次
            right = n * 2 * k - 1;
            left = right - 2 * k + 1;            
        }
        if (x.length - left > k) {
            reverseCharArrayByIndex(left, left + k - 1);
        } else {
            reverseCharArrayByIndex(left, x.length - 1);
        }
        return String.valueOf(x);
    }
    public void reverseCharArrayByIndex(int indexLeft, int indexRight) {
        // 反转在范围内的下标
        int length = (indexRight - indexLeft + 1) / 2;
        while (length-- > 0) {
            char temp = x[indexLeft];
            x[indexLeft] = x[indexRight];
            x[indexRight] = temp;
            indexLeft++;
            indexRight--;
        }
    }
}

03. 反转字符串中的单词

题目链接

代码随想录题解

3.1 题目

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：

输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

3.2 笔记

这道题目目前只是做出了一个解法，时间复杂度很高，我这里先将这个方法讲述一下，后面学到新方法会补上。

我们先利用 split 函数将字符串按照空格分割，得到一个数组，然后我们会得到一个新的数组，这个数组中可能包含空字符串。

我们对这个新的字符串数组进行反转，

这时可能会有疑惑，这里面不相干的元素不会影响我们反转吗？

我们假想一个数组，在里面随意添加好多不相干的元素，将这个数组反转之后把不相干的元素去掉，结果和直接反转数组效果是一样的。

反转后依次取出元素，如果里面的不是 “” 空字符串我们就将它前面加上空格，再拼接到结果字符串中

为什么是前面呢？

因为可以规避最后一个元素后面多加一个空格的情况，转化为处理第一位多加空格的情况，只需要返回一个 res.substring(1); 即可，而不是要写 res.substring(0, res.length - 1);

3.3 代码

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        int n = words.length / 2;
        int left = 0;
        int right = words.length - 1;
        String res = "";
        while (n-- > 0) {
            String temp = words[left];
            words[left] = words[right];
            words[right] = temp;
            left++;
            right--;
        }
        for (int i = 0; i < words.length; i++) {
            if (words[i] != "") {
                res += " " + words[i];
            }            
        }
        return res.substring(1);
    }
}