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

344.反转字符串

题目链接：344.反转字符串
文档讲解：344.反转字符串
视频讲解：344.反转字符串
目标：学习reverse函数的使用，明确使用库函数的条件
状态：比较简单🤗

学习前的想法

需要编写一个函数，其作用是将输入的字符串反转过来，要求空间复杂度为O(1)，即不使用额外的空间，原地修改数组。

考虑到字符串像数组一样，可以使用两个指针分别从字符串的起始位置和终止位置遍历，交换两个指针的值即可。

需要考虑到的问题是字符串中字符是奇数个还是偶数个，假设我的两个指针分别为left和right，字符串为s，则left = 0, right = s.size() - 1。

每次交换后，left++, right--，显然需要使用一个循环来实现，那么我们的循环结束条件是什么呢？

当字符数为奇数时，中间的字符不需要交换，当left = right时，循环终止，
当字符数为偶数时，中间的两个数交换后，left++，right--，当left = right时，循环终止。

尝试实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;

        while(left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

2024-3-6
这道题应该是可以使用swap()的吧🤪

学习后的想法

字符串的处理操作在思想上和数组一致，只是在不同的语言中表现方式不同。

双指针法的经典应用，思路和我上面写的基本一样。

2024-3-6
后面会做一个双指针经典移动过程的总结

卡哥使用的是for循环实现的，这一点和我不太一样。

再次明确平常练习以及面试中库函数的使用场景：

不要使用库函数去实现算法的关键部分

实现

1
2
3
4
5
len = s.size() - 1;

for(int i = 0, j = len; i < j; i++, j--) {
	swap(s[i], s[j]);
}

541. 反转字符串II

题目链接：541. 反转字符串II
文档讲解：541. 反转字符串II
视频讲解：LeetCode：541. 反转字符串II
目标：
状态：虽然是简单题，但是哥们还是不hui🤗

学习前的想法

每次计数至2k后需要重新计数。

尝试实现，每2k个字符翻转前k个字符，进行一个循环，判断剩余字符数的长度，

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string reverseStr(string s, int k) {
        int over = s.size();
        int left = 0;

        while(true) {
            if(over >= 2 * k) {
                reverse(left, left + k);
                left = left + 2k;
                over -= 2 * k;
            }

            if(over >= k && over < 2k) {
                reverse(left, left + k);
                break;
            }

            if(over > 0 && over <k) {
                reverse(left, s.size());
                breaak;
            }
        }

        return s;
    }
};

编译报错。。。。

2024-3-6
在所有的博客中，我都将我自己写过的错误代码放入了其中，多年以后，当我面向我的这些记录时，我是否回忆起当年第一次敲出这些代码来的焦灼与兴奋感呢？
这也时我为什么采用了这种时间戳的形式来记录自己的一些想法。

学习后的想法

上面应该是reverse()函数的使用出现了错误，本题并不涉及具体算法的一些只是，难点只在于将字符串进行反转的一些规则。

在处理字符串时，可以每隔2k个字符处理一次

实现

1
2
3
4
5
6
for(int i = 0; i < s.size(); i += (2 * k)) {
	if(i + k <= s.size()) reverse(s.begin() + i, s.begin() + i + k);
	else reverse(s.begin() + i, s.end());
}

return s;

卡码网：54.替换数字

题目链接： 卡码网：54.替换数字
文档讲解： 卡码网：54.替换数字
视频讲解：
目标：
状态：感觉这一题很黏人

学习前的想法

给定一个字符串，其中包含数字和小写字母，需要将数字字符替换为number。

这一题需要直接将这个字符串输出出来，我的想法是遍历这个字符串遇到数字，就打印number，字母就按原样输出。

尝试实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

int main() {
    string s;
    
    cin >> s;
    
    for(int i = 0; i < s.size(); i++) {
        if(s[i] >= '0' && s[i] <= '9') {
            cout << "number";
        }else {
            cout << s[i];
        }
    }
    
    cout << endl;
    
    return 0;
}

这种做法是可以通过卡玛网的测试的，但是似乎和下面卡哥的方法不一样。

2024-3-6
但是这种方式时空性能似乎都要比卡哥的做法好

学习后的想法

我们进行的是一个数组填充的任务，在文档里，卡哥指出很多数组填充类的题目，其做法都是预先给数组扩容带填充后的大小，然后从后向前进行操作。

关于为什么是从后开始遍历，这是因为，如果从前遍历，在数组中每填充一个新元素，就需要把这个元素后面的元素都向后移动一位。

而且，在刚开始一次性申请够所有的空间，就不需要每次添加都去申请一次。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string s;
cin >> s;
int oldSize = s.size();
int count = 0;
for(int i = 0; i < s.size(); i++) {
	if(s[i] >= '0' && s[i] <= '9') count++;
}

s.resize(s.size() + count * 5);
int newSize = s.size();
for(int i = newSize - 1, j = oldSize - 1; j < i; i--, j--) {
	if(s[j] > '9' || s[j] < '0') s[i] = s[j];
	else {
		s[i] = 'r';
		s[i - 1] = 'e';
		s[i - 2] = 'b';
		s[i - 3] = 'm';
		s[i - 4] = 'u';
		s[i - 5] = 'n';
		i -= 5;
	}
}

cout << s << endl;

151.翻转字符串里的单词

题目链接：151.翻转字符串里的单词
文档讲解：151.翻转字符串里的单词
视频讲解：字符串复杂操作拿捏了！ | LeetCode:151.翻转字符串里的单词
目标：
状态：学过之后思路知道了，但是代码逻辑还是有点迷糊，得多加练习

学习前的想法

2024-3-6
从开始学c语言开始，就对这种带有不定数目空格的字符串的处理头疼，实在是没有思路。想来应该是此类题目做的比较少，遂直接查看题解，努力学习，天天向上。

学习后的想法

整体的思路是先把整个字符串进行反转，反转后再对每个单词分别做一次反转，因为反转字符串的实现前面已多次实现，在这里我们可以直接使用reverse()函数来实现。

所以本题的难点实际上在于怎么把多余的空格删去。

在字符串的前面，单词之间，字符串的后面，都可能会存在一个或者多个空格，在去除空格是需要同时考虑到这三种情况。

我们本质上是使用快慢指针来实现的，快指针向后遍历，不断的将非空的值赋给慢指针所在的位置，随后慢指针位置向后移动一位。

关于如何去除前端空格？

只需要将快指针向后遍历，直到所指位置不为空格，或者超出字符串长度；

关于如何去除单词之间空格？

由于每个单词之间需要存在一个空格，我们在快指针遍历时需要保留一个空格存入慢指针所指向位置，如果快指针指向空格，但是快指针前面的一个位置不为空格，说明这个空格是紧挨着单词的，我们将其保留，当快指针指向空格，并且其前面一个位置也为空格时，说明这个空格是多出来的，我们将其删除。

关于如何去除后端空格？

快指针已经将字符串遍历完成，此时有两种情况：

（注意：慢指针始终指向需要填充的位置，即已填充元素的后一位）

慢指针指向最后一个单词的最后一个字母的后一位，此时只需重塑字符串大小为慢指针位置，即slowIndex。

慢指针指向最后一个单词的最后一个字母的后一位的后一位，此时说明我们最后一个单词之后跟了一个多余的空格，我们需要将其删除，因此重塑字符串大小位慢指针位置减1，即slowIndex - 1。

实现

2024-3-7
由于我对这一题的理解还不够到位，自己没能写出伪代码来表示我的思路，后续会补上

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

题目链接：55. 右旋字符串
文档讲解：右旋字符串
视频讲解：
目标：
状态：

学习前的想法

我的第一个想法是将后面的k个字符保存下来，然后重塑原来字符串的大小为s.size() - k，将前面保存的字符串与重塑的s拼接一下，就实现了题目要求的效果。

这样需要使用额外空间，并不是一个很好的方法。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

int main() {
    int k;
    string s;
    
    cin >> k >> s;
    
    string tail;
    
    for(int i = s.size() - k; i < s.size(); i++) {
        tail += s[i];
    }
    
    s.resize(s.size() - k);
    
    cout << tail + s << endl;
    
    return 0;
}

学习后的想法

提升一下本题的难度，要求空间复杂度为O(1)。

思路和上一题一样，先整体反转，再分段反转。

这个思路确实很牛逼，因为反转的函数已经有了，也很简洁，只需控制好反转的长度就行。

实现

1
2
3
4
5
int k, string s;

reverse(s.begin, s.end);
reverse(s.begin, s.begin + k);
reverse(s.begin + k, s.end);

收获与学习时长

学习时长： 2 Day
因为学校在搞生产实习，学习不了考研的东西，因此课上断断续续写点博客，效率属实低下，效果也不是很好，细水长流，慢慢磨了两天，才写完完整的一些内容，不过内容应该还算充实，有很多我个人的想法与理解。

收获

2024-3-7
痛苦无法避免，磨难可以选择，共勉。