代码随想录算法训练营第七天｜LeetCode 344.反转字符串、541.反转字符串II、卡码网54.替换数字、151.翻转字符串里的单词、卡玛网55.右旋转字符串

344.反转字符串

题目描述：

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

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

示例一:

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

示例二：

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

提示：

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

解题思路：

1. 关键词提取：反转、原地修改

2. 解法：

   1. 双指针法，左指针和右指针，从两边向中间靠拢。
   2. 每次互换指针对应的字符。
   3. 结束条件是指针相遇。

   代码如下：

   class Solution {
   public:
       void reverseString(vector<char>& s) {
           // 左右指针，一个最左侧，一个最右侧
           int left = 0;
           int right = s.size() - 1;
           // 两边向内靠拢，相遇则结束
           while(left < right) {
               // 交换左右指针的字符
               char tmp = s[left];
               s[left] = s[right];
               s[right] = tmp;
               // 指针向中间移动
               left++;
               right--;
           }
       }
   };

总结：

1. 暴力解法是：

   1. 新建一个数组，负责存放将当前数组的值反转以后的值
   2. 从后往前遍历当前数组，将值从前往后放到新建数组中
   3. 将新建数组的值拷贝至当前数组，并且返回当前数组

2. 其实还可以通过栈来做这件事情：

   1. 新建一个栈，负责存放当前数组的值
   2. 从前往后遍历当前数组，将值压栈
   3. 再次从前往后遍历当前数组，出栈，将栈顶的值放到当前数组中，最后返回当前数组

3. 代码随想录提供的是双指针方法，跟反转链表的解法一致。

   1. 理解中，还是降维的一种方式。将两次遍历降维成一次遍历。在其他的算法题中，遇到多次遍历的时候，都可以想一下双指针法降维。
   2. 有个思路值得深思的，就是在刷题的时候，尽量不用系统的库函数，想办法去实现底层的逻辑，这样子可以保持着一种求知的状态，对细节做好把控。很多时候就是因为封装好的函数太方便，就导致都依赖于这种遍历性，缺少独立思考的能力。

541.反转字符串II

题目描述：

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

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

示例一:

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例二：

输入：s = "abcd", k = 2
输出："bacd"

提示：

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

解题思路：

1. **关键词提取：**每2k个字符、反转k个字符、全部字符
2. 解法：
   1. 局部反转。间隔是2k，局部是k。
   2. 遍历的时候，可以以2k作为每次遍历的条件。
   3. 需要区分当前属于哪一种情况，按照题目要求，一共是三种情况：
      1. i+2k不超过数组长度，反转前k个字符
      2. i+2k超过数组长度，而且i+k超过数组长度，反转剩余全部字符
      3. i+2k超过数组长度，而且i+k不超过数组长度，反转前k个字符
   4. 其实第一点和第三点是可以合并的，都是要反转前k个字符

代码如下：

class Solution {
public:
    void reverseString(string& s, int left, int right) {
        // 左右指针，一个最左侧，一个最右侧
        // 两边向内靠拢，相遇则结束
        while(left < right) {
            // 交换左右指针的字符
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            // 指针向中间移动
            left++;
            right--;
        }
    }
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size();i = i + 2*k) {
            // 假如剩余字符超过2k，直接反转前k个字符
            if(i + 2*k < s.size()) {
                reverseString(s, i, i + k - 1);
            }
            // 假如剩余字符不超过k，直接反转全部字符
            else if(i + 2*k > s.size() && i + k > s.size()) {
                reverseString(s, i, s.size() - 1);
            }
            // 假如剩余字符超过k，但是不超过2k，直接反转前k个字符
            else {
                reverseString(s, i, i + k - 1);
            }
        }
        return s;
    }
};

总结：

1. 一刷的时候，采取的策略是：

   1. 将数组切割为两段，一段是满足i+2k，一段是不满足i+2k
   2. 针对第二段，再做判断，看是否满足i+k，针对性做处理
   3. 第一段可以用一个循环解决，第二段可以用一个if和else解决
   4. 缺点是，要找对循环的退出条件，以及判断的临界条件，在写代码的时候很容易出错，需要多次调试
   5. 我采用的切割方式是取余以及整除，确认循环次数以及判断的临界条件，调试了四次，才勉强通过

2. 代码随想录提供一个清晰的思路：

   1. 这是一道模拟的题目
   2. 对于累计的2k这个条件，可以放到for循环的表达式中，i+2k就可以
   3. 库函数的实现方式，可以自己实现，也可以调用库函数

54.替换数字

题目描述：

​ 给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

示例一:

输入：s = "a1b2c3"
输出："anumberbnumbercnumber"

提示：

数据范围：
1 <= s.length < 10000

解题思路：

1. **关键词提取：**字符不变、数字替换
2. 解法：
   1. 确认遍历的顺序：
      1. 从前往后遍历，会出现字符在数组中的频繁移动
      2. 从后往前遍历，未遍历到的字符在数组中的位置不需要做移动
      3. 因此，采用从后向前遍历的方式
   2. 在原来的数组中，每次替换数字的时候，做扩容
   3. 扩容，需要遍历原数组，统计数字的个数，计算需要增容的空间大小
   4. 往新数组中填充数据，需要同步遍历原数组，所以采用双指针的解法

代码如下：

#include<iostream>
using namespace std;
int main() {
    string s;
    while(cin>>s) {
        // 统计字符数组中数字的个数
        int count = 0;
        // 记录字符数组原数组的长度
        int strOldLen = s.size();
        for(int i = 0; i < strOldLen; i++) {
            if(s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        // 扩充原数组
        s.resize(s.size() + count * 5);
        // 记录新数组的长度
        int strNewLen = s.size();
        // 遍历原数组，从后往前遍历，并且往新数组中填入字符
        // 需要两个指针来完成这个动作
        // 并且，新旧数组是同一个数组，新数组是在原数组的基础上新增了多个空格
        // 两个指针分别指向各自数组的最后一个元素位置
        // int oldIndex = strOldLen - 1;
        int newIndex = strNewLen - 1;
        for(int oldIndex = strOldLen - 1; oldIndex >= 0; oldIndex--) {
            // 是字符
            if(s[oldIndex] >= 'a' && s[oldIndex] <= 'z') {
                // 赋值以后，下标要做移动
                s[newIndex--] = s[oldIndex];
            }
            // 是数字
            else {
                // 赋值以后，下标要做移动
                s[newIndex--] = 'r';
                s[newIndex--] = 'e';
                s[newIndex--] = 'b';
                s[newIndex--] = 'm';
                s[newIndex--] = 'u';
                s[newIndex--] = 'n';
            }
            // oldIndex--;
        }
        cout << s << endl;
    }
}

总结：

1. 比较直接的，是考虑新建一个空间符合要求的数组，然后在新的数组中，去填充替换后的字符串，并且是从前往后去遍历，逐个放置字符串。
2. 代码随想录的思路中，借鉴的地方如下：

   1. 假如是在原数组中做操作，遍历顺序的影响：

      1. 增加时间复杂度，没替换一个数字，要将后续的元素统一往后移动四位。
      2. 会让代码变得复杂，多加一个循环，移动后续数组元素，并且指向下一个需要检索的原数组元素。

   2. 双指针法：

      1. 无论是新建一个数组，或者是在原数组中做扩容，都会需要用到两个指针。
      2. 采用双指针法，会让这两个方法的代码逻辑一样。
         1. 新建一个数组，从前往后遍历。
         2. 在原数组做扩容，从后往前遍历。

151.反转字符串中的单词

题目描述：

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

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

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

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

示例一:

输入：s = "the sky is blue"
输出："blue is sky the"

示例二:

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

提示：

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

解题思路：

1. **关键词提取：**反转单词顺序、间隔一个空格
2. 解法：
   1. 解决掉多个空格，按照题目描述共三种情况：
      1. 前导
      2. 尾随
      3. 中间
   2. 反转单词的顺序，单词内部的顺序不需要反转，两种方式：
      1. 负负得正，整体反转后，再反转单词内部的顺序
      2. 识别单词，统计单词个数，再按照个数来调整单词的顺序，需要采用二维数组存储单个单词

代码如下：

class Solution {
public:
    void reverseString(string& s, int left, int right) {
        // 左右指针，一个最左侧，一个最右侧
        // 两边向内靠拢，相遇则结束
        while(left < right) {
            // 交换左右指针的字符
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            // 指针向中间移动
            left++;
            right--;
        }
    }
    string reverseWords(string s) {
        // 清除前导空格
        int start = 0;
        while(s[start] == ' ') {
            start++;
        }
        // 清除尾随空格
        int end = s.size() - 1;
        while(s[end] == ' ') {
            end--;
        }
        // 实际的清除动作，是在下述操作中执行的，双指针，做数组元素的移动
        // 清除字符数组中的多余空格
        int newIndex = 0;
        for(int oldIndex = start; oldIndex <= end; oldIndex++) {
            if(s[oldIndex] == ' ' && s[oldIndex + 1] == ' ') {
                continue;
            }
            // 在原数组中，从前往后，填充字符
            s[newIndex++] = s[oldIndex];
        }
        // 手动添加截止符
        s[newIndex] = '\0';
        // 将字符全部反转
        reverseString(s, 0, newIndex - 1);
        // 重新定义数组大小
        s.resize(newIndex);
        // 反转单词
        // 从前往后，检测到空格以及截止符号，就划分出前面完整的一个单词，将该单词反转
        newIndex = 0;
        for(int i = 0; i <= s.size(); i++) {
            if(s[i] == ' ' || s[i] == '\0') {
                reverseString(s, newIndex, i - 1);
                newIndex = i + 1;
            }
        }
        return s;
    }
};

总结：

1. 一旦遇到数组元素移动的方式，还是下意识的采用暴力解法，就是逐个移动当前元素后面的元素，在这点上还没有明显改进。

2. 代码随想录的思路借鉴：

   1. 双指针法，去做数组元素的移动。不申请额外的数组空间。

   2. 数组的两次反转，负负得正。这点一开始都很难想得到。

      1. 按照题目的要求，能想到的还是顺序遍历，统计单词个数以及记录单词。再按照个数来做反转。
      2. 但是，基于上述点，可以采用栈的思路来做反转。将单词拆分出来，入栈。然后，再挨个出栈，从前往后遍历，放入到数组中。

   3. 从思路上来说，删除空格的顺序，应该是先删前缀，再删中间，最后删后缀。

      1. 代码的组合逻辑上，这个脉络会清晰一些。
      2. 这个写法，在采用双指针法做元素移动时，更明确。

   4. 删除空格还有另一种思路，可以先删除掉全部空格，再手动添加单词之间的空格。

55.右旋转字符串

题目描述：

​ 字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

示例一:

输入：s = "abcdefg" k = 2
输出："fgabcde"

提示：

数据范围：
1 <= k < 10000,
1 <= s.length < 10000;

解题思路：

1. **关键词提取：**后方字符、移动到前方、数量k
2. 解法：
   1. 明确字符串大小size和数量k之间的关系：
      1. 若k>size，就会出现循环移动的情况，k-size和k的结果是一致的，只需要移动一次就可以
      2. 若k==size，就不需要移动
      3. 若k<size，就需要移动
   2. 移动的方式：
      1. 新建一个数组。定位至size-k所在的位置，将后k个字符放置到新数组的前边，再将0-size-k这个区间的字符依次放置到新数组中。最后返回新的数组
      2. 在原数组上做移动。负负得正的思路，将字符串整个反转，再将前k个字符做一次反转，再将后size-k个字符做一次反转

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    // 接收字符串和整数
    cin >> n;
    cin >> s;
    
    // int len = s.size();
    // 反转整个字符串
    reverse(s.begin(), s.end());  
    // 反转前n个字符
    reverse(s.begin(), s.begin() + n);
    // 反转剩余字符，size - n
    reverse(s.begin() + n, s.end());
    
    cout << s << endl;
}

总结：

1. 移动元素，可以新建一个数组，采用双指针的方式，将后k个字符先放到数组前面，再将前size-k个字符放到数组后面。
2. 代码随想录的思路借鉴：
   1. 不申请额外空间的思考。刚好是上一道反转字符串的思路的延伸，负负得正。
   2. 对于细节的思考。反转字符串，负负得正，也有两种方式：
      1. 左反转。
      2. 右反转。
      3. 反转也分两种方式：
         1. 先整体后局部。
         2. 先局部后整体。
   3. 虽然只需要调整一下反转的代码的顺序，但是这种再深入一些的思考，是一种向上攀登的态度。相比于做出来结束，这种再反复斟酌一些细节，并且搞清楚区别点，会增进思维逻辑的严谨性以及系统性，也是我最应该做的调整。