Day 8 | Leetcode 344, 541, k54, 151, k55

链接

344.反转字符串
541. 反转字符串II
卡码网：54.替换数字
151.翻转字符串里的单词
卡码网：55.右旋转字符串

知识

541. 反转字符串II

一般来说，编程语言自己实现的库函数都是左闭右开的，因此reverse(s, i, i + k)表示的是反转字符串s的第i位到第i + k位，不包含第i + k位。

卡码网：54.替换数字

1. 注意，cpp中比较大小不能写作48 <= s[i] <= 57，而是要写作s[i] >= 48 && s[i] <= 57。表达式48 <= s[i] <= 57实际上会先计算48 <= s[i]，这个表达式的结果是一个布尔值true或false，在C++中，这个布尔值会被隐式转换为整数，true转换为1，false转换为0。然后，该整数（0或1）会与57进行比较，所以条件几乎总是为真（除非s[i]是字符'0'）。
2. 扩容字符串的函数为resize函数。
3. cpp中是可以不遍历字符串中的每个字符，就直接cout输出整个字符串的。
4. 字符串和数组的区别（摘自代码随想录）：
   字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。
   在C语言中，把一个字符串存入一个数组时，也把结束符 ‘\0’存入数组，并以此作为该字符串是否结束的标志。
   在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。
   那么vector< char > 和 string 又有什么区别呢？
   其实在基本操作上没有区别，但是string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。所以想处理字符串，我们还是会定义一个string类型。
5. 若要求某个字符在0-9之间，既可以写s[i] >= 48 && s[i] <= 57（’0’的ascii码是48，’1’的ascii码是57），也可以写s[i] >= '0' && s[i] <= '9'。

151.翻转字符串里的单词

1. erase函数的时间复杂度是O(n)
2. 本题可以用split函数来从字符串中分割出单词，但那样就失去了意义
3. 若给一个函数传入的参数加上引用&，那么在函数中对这个参数进行了修改，调用该函数后该参数也会被修改。

卡码网：55.右旋转字符串

1. 注意：若在ACM模式中调用reverse函数，必须#include <algorithm>，否则会报错。但若调用swap函数，不需要引用任何头文件，直接使用即可。

初次尝试

344.反转字符串

先尝试用reverse函数秒杀，顺便复习reverse函数的用法：

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

reverse函数相当于把字符串反转以后，将新的字符串存入了旧的字符串中。

我曾经做过反转链表的题，猜测用双指针可以解决这道题。写下了以下的代码：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )
        {
            // swap(s[l], s[r]);
            int tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
        }
    }
};

直接用swap函数或者手写swap函数都是可以的。l < r或者l <= r都可以。因为字符串中字符的个数为奇数时，中间那个字符交换不交换都一样；字符个数为偶数时，交换最后两个成对的字符即可。

541. 反转字符串II

拿到这道题，我的第一想法是分类讨论。设字符串的长度是len。若len < k，则全部反转；若k <= len < 2k，则反转前k个字母；若len >= 2k，则按照题意反转。本题在反转的逻辑上没有困难，但问题在于如何分割出需要反转的子字符串。我没想出来什么好办法，写的逻辑太复杂又容易出错。

卡码网：54.替换数字

我先输入字符串s，然后定义每个元素由char类型变量组成的vector。遍历字符串s，若其中的某个字符的ascii码在48-57之间，说明该字符是数字0-9，那么向vector中依次插入number这6个字符。其他情况下，向vector中插入原始字符即可。据此思路写下以下的代码，可以通过评测。

# include <iostream>
# include <vector>

using namespace std;

int main()
{
    string s;
    cin >> s;

    vector<char> out;

    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] >= 48 && s[i] <= 57)
        {
            out.push_back('n');
            out.push_back('u');
            out.push_back('m');
            out.push_back('b');
            out.push_back('e');
            out.push_back('r');
        }
        else
            out.push_back(s[i]);
    }

    for (int i = 0; i < out.size(); i ++ )
        cout << out[i];
    cout << endl;
    return 0;
}

151.翻转字符串里的单词

这道题yxc应该讲过,要么通过流的方式读入为一个个单词，样例代码如下所示：

#include <iostream>
#include <string>
#include <sstream> // 引入 stringstream

using namespace std;

int main()
{
    string line;
    getline(cin, line); // 使用 getline 读取一整行

    stringstream ss(line); // 使用 stringstream 来分割字符串
    string word;
    while (ss >> word) { // 从 stringstream 中读取单词，直到结束
        cout << word << endl; // 输出单个单词
    }

    return 0;
}

要么通过双指针算法找出一个个单词并存储之。然后再将一个个单词逆序拼接为字符串并输出。我先尝试后一种方法。但没有做出来。

卡码网：55.右旋转字符串

本题我下意识地使用substr来写，得到如下的代码：

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    string s1 = s.substr(s.size() - k, s.size()); // 后面k个字符
    string s2 = s.substr(0, s.size() - k); // 字符串在后面k个字符前的字符
    cout << s1 + s2 << endl;
}

向substr中传入的区间是左闭右开的。

若不借助库函数，我还有一个想法。先拿一个字符串保存输入字符串的后面k个字符。然后在输入字符串的基础上，从尾部倒着插入前面的那些字符，最后再将另一个字符串保存的原字符串的后面k个字符插到新字符串的前面去。其实倒着插入和顺着插入也没什么区别。

我还想到一种做法。受到151. 翻转字符串里的单词启发，首先反转整个字符串，然后反转字符串的前k位，最后反转字符串的后(n - k)位。由此写出了两个版本的代码，第一版是直接调用reverse函数，第二版是手动实现reverse函数。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());
    cout << s << endl;
}

#include <iostream>
#include <string>

using namespace std;

// 手动实现reverse函数
void reverseString(string &s, int i, int j)
{
    for (int a = i, b = j; a < b; a ++ , b -- )
    {
        int tmp = s[a];
        s[a] = s[b];
        s[b] = tmp;
    }
}

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    reverseString(s, 0, s.size() - 1);
    reverseString(s, 0, k - 1);
    reverseString(s, k, s.size() - 1);
    cout << s << endl;
}

实现

344.反转字符串

在算法的思路上，字符串和数组非常类似。本题应用双指针法即可：首尾交换，再次一级交换，以此类推。因此首尾各有一个指针，两指针交换，然后两指针同时向中间移动。若库函数直接把题目解决了，就不要用库函数。若库函数是题目的一部分，且我们知道库函数的大体实现逻辑和时间复杂度，那就可以用。代码如下所示：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )
            swap(s[i], s[j]);
    }
};

swap函数有两种方法，一种是常见的交换数值，另一种是位运算，可参见代码随想录。

541. 反转字符串II

模拟题，模拟复杂的规则下，如何反转字符串。题意：每2k段的前k个字符进行反转，尾部如果剩下的字符超过长度超过k，则反转k个字符，剩下的不动。尾部如果剩下的字符长度小于k，则全部反转。本题的代码可以很简洁。

本题每次取2k段，因此按照2k来遍历：for (int i = 0; i < s.size(); i += 2k)。然后在for循环中操作前k个字符即可。边界条件想不明白可以带一个具体的例子来试。代码和注释如下所示：

class Solution {
public:
    string reverseStr(string s, int k) {
        // 每隔2k个字符跳转一次，即每次取出2k个字符
        for (int i = 0; i < s.size(); i += 2 * k)
        {
            // 对2k个字符的前k个字符进行反转
            // 由于每次取2k，取若干次后。字符串的尾部剩下的字符长度l可能l < k 或 k <= l < 2k
            // 对前一种情况，需要将尾部全部反转，对后一种情况，需要反转尾部剩下字符的前k个字符
            // 先处理后一种情况，注意加上条件i + k <= s.size()，这可以避免对索引超出范围的元素进行反转
            // 至于i + k是否能取到s.size()，可以举例子：k = 3, s = {a, b, c}，由此可见可以取等于
            // 也可以从理论上分析，由于reverse的区间是左闭右开的，因此s.begin() + i + k实际上取不到，因此可以让i + k = s.size() 
            // 处理完后continue即可，除去反转2k个字符中的前k个字符的一般情况，尾部剩下的字符的长度的第一种情况和第二种情况只可能有一种发生
            if (i + k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k); // 左闭右开
                continue;
            }
            // 再处理前一种情况，当剩余的字符长度l < k时，反转剩余的全部字符
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

也可以不用continue，直接采用if-else写法，参见代码随想录的写法（代码随线录的注释也更加简洁明了）：

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

卡码网：54.替换数字

本题的最佳解法不需要额外的辅助空间。首先扩充原字符串到每个数字字符替换成 “number” 之后的大小。然后用双指针算法，指针i指向旧字符串的末尾，指针j指向新字符串的末尾。用指针i遍历旧字符串，若遇到字母，则原样填入指针j指向的位置；若遇到数字，则从后往前将number填入到指针j指向的位置。直到i和j都指向新旧字符串的开头为止。这里的新旧字符串其实是扩容之后和扩容之前的同一字符串，只是为了方便区分称它们为新旧字符串。根据这个思路，我写出了如下的代码：

# include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    
    // count为字符串中数字的数量
    int count = 0;
    for (int i = 0; i < s.size(); i ++ )
        if (s[i] >= 48 && s[i] <= 57)
            count ++ ;
    
    int oldSize = s.size();
    s.resize(oldSize + count * 5); // 字符串扩容
    
    // 双指针算法，i指向旧字符串，j指向新字符串
    for (int i = oldSize - 1, j = s.size() - 1; i >= 0; )
    {
        if (s[i] < 48 || s[i] > 57) 
        {
            s[j] = s[i];
            i -- ;
            j -- ;
        }
        else
        {
            s[j] = 'r';
            s[j - 1] = 'e';
            s[j - 2] = 'b';
            s[j - 3] = 'm';
            s[j - 4] = 'u';
            s[j - 5] = 'n';
            i -- ;
            j -= 6;
        }
    }
    
    // 可以直接写作cout << s << endl;
    for (int i = 0; i < s.size(); i ++ )
        cout << s[i];
    return 0;
}

代码随想录的代码本质上和我写的是一样的，但他写的更见简洁一些，我写的更易于理解一些。

我的写法中，必须让i >= 0，不能写成i > 0，否则答案错误。例子，输入1，输出本来应该为number，若for循环的条件为i > 0，则不会进入for循环，直接输出1，这显然是不对的。但对于代码随想录的写法：for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--)，则j < i是正确的，若首字符为字母，则j = i时两指针均以指向首字符，首字符保留即可，不需要处理；若首字符为数字，则逻辑也可以正确执行。若j <= i，则反而会出现越界的问题，因为当j和i都指向首字符后，for循环的条件依然满足，此时完成当前循环后，i和j继续-1，再次判断时，i依然等于j，再次进入循环，此时s[i]和s[j]就不存在了（s[-1]不存在）。

151.翻转字符串里的单词

是字符串中操作比较复杂的题目，给的字符串中在开头、中间、结尾都可能有空格。反转字符串里的单词后，要将多余的空格都删掉。

整体思路：先让单词的顺序和目标相同，即将整个字符串都反转。再对每个单词做反转，就得到了目标字符串。将原字符串整体反转，再将每一个单词反转。

难点：如何删去多余的空格。要求空间复杂度O(1)，即不能申请新的字符串来放置删去多余空格后的字符串。且不能使用库函数。使用快慢双指针算法，删除多余空格的时间复杂度为O(n)。快指针用于遍历旧字符串，慢指针用于依次指向新字符串中的各个元素。（新字符串在旧字符串的基础上修改，并不需要另外创建字符串来存储新字符串）。双指针的用法同数组章节的移除元素。

根据上述思路，我写出了如下的代码：

class Solution
{
public:
    void removeExtraSpace(string &s)
    {
        int slow = 0;
        for (int fast = 0; fast < s.size(); fast ++ )
        {
            if (s[fast] != ' ') // 去除字符串开头的空格
            {
                // 每复制完一个单词后，加一个空格
                // 这句话不可以放在while循环后，否则会在最后一个单词后面增加一个多余的空格
                if (slow != 0) s[slow ++ ] = ' ';

                // 将旧字符串的非空部分复制到新字符串中
                while (fast < s.size() && s[fast] != ' ') s[slow ++ ] = s[fast ++ ];
            }
        }
        s.resize(slow);
    }

    string reverseWords(string s) 
    {
        removeExtraSpace(s); // 删去所有多余的空格

        reverse(s.begin(), s.end()); // 反转整个字符串，注意reverse函数是左开右闭的

        // 反转每个单词
        int start = 0, i = 0;
        while (i < s.size())
        {
            while (i < s.size() && s[i] != ' ') i ++ ; // 找到空格
            reverse(s.begin() + start, s.begin() + i); // 反转start到空格之间的单词
            start = i + 1; // 更新start
            i = start; // 更新i
        }
        return s;
    }
};

代码随想录中的反转每个单词的写法和我的略有不同，他用的是for循环，但本质是一样的。

卡码网：55.右旋转字符串

我在初次尝试中已经给出了空间复杂度为O(1)的最优解法，下面两幅图（对应两种等效的方法）可以帮助理解：

1. 先反转整个字符串，再反转两个子串

   

2. 先反转子串，再反转整个字符串

   

心得与备忘录

344.反转字符串

两种for循环的写法：for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )和for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )都可以。

541. 反转字符串II

1. for循环每次以2k为长度去跳转

2. 本题反转字符的三种情况：

   • 每隔 2k 个字符的前 k 个字符进行反转
   • 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
   • 剩余字符少于 k 个，则将剩余字符全部反转

   三种情况每次只可能出现一种，即出现了一种情况，另外两种情况就不会出现了。据此，我写出了结构分明的三段式代码：

   class Solution {
   public:
       string reverseStr(string s, int k) {
           for (int i = 0; i < s.size(); i += 2 * k)
           {
               // 情况1
               if (i + 2 * k <= s.size())
               {
                   reverse(s.begin() + i, s.begin() + i + k);
                   continue; // 可以省略
               }
               // 情况2
               else if (i + k <= s.size())
               {
                   reverse(s.begin() + i, s.begin() + i + k);
                   continue; // 可以省略
               }
               // 情况3
               else
                   reverse(s.begin() + i, s.end());
           }
           return s;
       }
   };

   情况1和情况2可以合并（即剩余字符的长度l满足l >= k时，都是反转剩下字符的前k个；只有当l满足l < k时，才要反转剩下的所有字符），因此产生了实现部分中的第二版代码。每次思考时应该先想到三种情况，再写出结构分明的三段式代码，然后对其进行简化。能够写出三段式代码即可，虽然不简洁但思路清晰简单、不容易出错。

3. 如果要求一段段地操作字符串或数组，那么for循环中的i变量是可以一段段增加的，而没必要每次+1

卡码网：54.替换数字

1. 本题注意使用双指针做法。代码推荐参考我在实现中的写法，虽然和代码随想录的代码略有差别，但本质是完全一样的。
2. 本题注意考虑边界条件，在我的写法中，是i >= 0而非i > 0；在代码随想录的写法中，是j < i而非j <= i。如果边界条件写得不对会导致发生指针异常或者部分样例无法通过。考虑边界条件时，可以举特例，也可以让代码先运行，若发生错误则修改相应的边界条件。

3. 很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。对于线性数据结构，填充或者删除，后序处理会高效的多。

   这么做有两个好处：

   1. 不用申请新数组。算法的空间复杂度从O(N)降到了O(1)。
   2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。算法的时间复杂度从O(n^2)降到了O(n)。

151.翻转字符串里的单词

1. 本题的总体思路：移除多余的空格->反转整个字符串->反转字符串中的每个单词
2. 利用快慢双指针移除多余的空格有两种写法，一种较为复杂，需要分别移除字符串前面的空格和字符串中间和最后的连续的不止一个的空格，最后再移除字符串最后可能存在的一个空格。另一种较为简单，思路和27.移除元素是相同的。快指针用于遍历旧字符串，慢指针用于依次指向新字符串中的各个元素。时间复杂度O(n)
3. 推荐使用较为简单的双指针写法。除去从旧字符串中复制每个单词到新字符串中的代码，还需要加上用于在新字符串中添加每个单词尾部的空格的代码。注意这两行代码的顺序不能写反，必须是先有添加空格的代码，再有复制单词的代码，否则会导致在新字符串的末尾多添加一个空格。
4. 上面提到的新旧字符串只是有时间上的先后，没有空间上的拷贝。新字符串就是在旧字符串的基础上利用双指针算法通过删除和改动部分元素得到的。因此空间复杂度为O(1)。

卡码网：55.右旋转字符串

1. 本题加上限制条件：不能申请额外空间，只能在本串上操作（对cpp）。
2. 可以先反转总串，再反转子串；也可以先反转子串，再反转总串。
3. 右旋转字符串和左旋转字符串方法完全相同，就是反转的区间不同。