当前位置：首页 > news >正文

代码随想录(day8)——字符串

news 2025/8/5 10:29:35

Leetcode.344 反转字符串：

344. 反转字符串 - 力扣（LeetCode）

原理过于简单，没什么好说的，直接给出代码：

class Solution {
public:void reverseString(vector<char>& s) {int end = s.size()-1;int start = 0;while( start <= end){swap(s[start],s[end]);start++;end--;}}
};

Leetcode.541 反转字符串：

541. 反转字符串 II - 力扣（LeetCode）

对于本题，题干中的条件看起来十分复杂，其实可以归结于一种分支情况，即每次都读取给定字符串 $s$ 中的前 $2k$ 个字符，反转前 $k$ 个。即：

而下面的两行则只是针对字符串中的剩余字符。如果剩余字符的数量少于 $k$ 则全部反转，否则反转前 $k$ 个。

由于对于字符串的反转，每次都是以 $2k$ 来进行的，所以，在遍历整体的字符串时，每次都遍历 $2k$ 个字符，再对这些字符进行操作。由于每当读取 $2k$ 字符和剩余字符的数量 $n$ , $k<n<2k$ 时，都是反转 $k$ 个字符，所以这两种情况可以归为一类。即：判断已被操作的区间＋ $k$ 是否满足 $<=s.size()$ ，满足的话，则反转这段区间的前 $k$ 字符，否则说明剩余字符的数量 $<k$ ，因此，直接对剩余的字符全部进行反转即可。

class Solution {
public:string reverseStr(string s, int k) {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.begin()+s.size());}} return s;   }
};

卡码网.54 替换数字:

54. 替换数字（第八期模拟笔试） (kamacoder.com)

对于本题，可以直接利用 $string$ 中的运算符重载 $"+="$ 以及开辟一个新的 $string$ 类对象来完成，但是这种方法需要开辟新的空间，且过于简单，意义不大，因此对于这种方法本处只给出代码，重点在于下面的第二种方法：

#include<string>
#include<iostream>
using namespace std;int main()
{string s1,s2;cin >> s1;for(int i = 0; i < s1.size(); i++){if(s1[i] >= '0' && s1[i] <= '9'){s2+="number";}else{s2+=s1[i];}}cout << s2;return 0;
}

运行结果如下：

对于第二种方法，可以首先遍历一遍给定的字符串，并且创建一个变量 $count$ 用于统计给定字符串中出现数字的次数。在遍历完成后，直接利用 $resize$ 函数对给定字符串进行扩容，扩容大小为 $s1.size()-count+count*6$ ，即 $s.size()+5*count$ 。此时的字符串的大小就等于将所有的数字都改为 $number$ 后的字符串的大小。

然后利用双指针对字符串进行遍历，一个指针 $fast$ 指向现字符串的末尾，另一个指针 $slow$ 指向原字符串最后一个字符所在的位置。例如对于字符串 $a1b2c3$ ，由于字符串中存在三个数字，因此 $count==3$ ,在扩容时，大小为 $3+5*3 = 18$ 。双指针指向的位置如下图所示：

如果 $slow$ 位置所对应的字符是数字，则从 $fast$ 位置开始，依次向前填写 $number$ 的每个字母，即：

在完成对于 $number$ 的倒序填写后，令 $fast--,slow--$ ，即：

再对 $slow$ 位置的字符进行判断，由于不为数字，因此 $s[fast]=s[slow];$ 对 $fast$ 位置进行赋值。即：

随后再 $fast--,slow--$ 。依次循环即可。

对应代码如下：

#include<string>
#include<iostream>
using namespace std;int main()
{string s1;cin >> s1;int count = 0;for(int i = 0; i < s1.size(); i++){if(s1[i] >= '0' && s1[i] <= '9'){count++;}}int oldlen = s1.size()-1;int slow = oldlen;s1.resize(s1.size()+5*count);int fast = s1.size()-1;for(; fast >=0; fast--){if(s1[slow] >= 'a' && s1[slow] <= 'z'){s1[fast] = s1[slow];}else {s1[fast] = 'r';s1[fast-1] = 'e';s1[fast-2] = 'b';s1[fast-3] = 'm';s1[fast-4] = 'u';s1[fast-5] = 'n';fast-=5;}slow--;}cout <<s1;return 0;
}

Leetcode.151 反转字符串中的单词：

151. 反转字符串中的单词 - 力扣（LeetCode）

对于本题，与文章C及C++每日练习(2)-CSDN博客中倒置字符串一题极为相似，但是对于本题，单词之间的空格并不是只有一个，而是若干个。因此，解决本题的方法可以分为两步：

1.将给定字符串中的多余的空格进行删除。

2.按照C及C++每日练习(2)-CSDN博客中的方法倒置字符串中的单词

对于如何删除字符中多余的空格，例如对于下面给定的字符串：

对于多余的字符，分别为第一个字符前面的空格和最后一个字符后面的空格，以及两个单词之前非第一个空格。对于消除多余的字符，可使用的方法如下：

利用 $for$ 循环对字符串进行遍历，同时创建两个指针 $slow,fast$ .在循环中，只对 $s[fast] !=" "$ 的情况进行处理，如果 $s[fast] ==" \, \, ";$ 则令 $fast$ 继续向后遍历。例如对于上面图中的字符串， $slow,fast$ 的起始位置如下所示：

当 $s[fast]!="\, \, \, ";$ 时，即：

令 $s[slow] = s[fast]$ ，并且两个指针向后移动一位，即：

按照上述方法，利用 $while$ 循环完成对于单个字符或者字符串的覆盖，即：

  while(fast < s.size() && s[fast] != ' '){s[slow++] = s[fast++];}

而对于多余空格的处理，可以再循环开头单独进行判定：判定条件如下：
$s[fast] !=' \, \, \, ' , slow !=0;$ ，例如对于上面图中 $slow$ 所处的位置是待处理的多余空格。由于处理多个空格的条件为 $s[fast] !=' \, \, \, ' , slow !=0;$ ，因此按照前面对于 $fast$ 运动逻辑的规定， $fast$ 会继续向下遍历，直到找到非空字符，即：

此时，改变 $slow$ 位置的字符，即： $s[slow] = '\, \, ';$ ，然后让 $slow$ 指向下一个位置，即：

随后，再利用前面的逻辑使得 $s[slow]=s[fast]$ 来复写非空字符串，即：

再按照前面的规则，首先让 $fast$ 移动至非空字符，即：

令 $s[slow++]='\, \, ';$ ，即：

再复写非空字符串，即：

完成了对于字符串的去重操作。随后，利用 $resize$ 函数，将字符串的长度改为 $slow$ 。

对于旋转字符串的方法，可以在C及C++每日练习(2) 进行查看，本处只给出相应代码：

class Solution {
public:void removeExtraSpace(string&s){int slow = 0, fast = 0;for(fast= 0;fast < s.size(); fast++){if(s[fast] != ' '){if(slow != 0){s[slow] = ' ';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());   int slow = 0;for(int fast = 0; fast <= s.size(); fast++){if(fast == s.size() || s[fast] == ' '){reverse(s.begin()+slow,s.begin()+fast);slow = fast+1;}}return s;}
};

运行结果如下：

卡码网.55 右旋字符串：

55. 右旋字符串（第八期模拟笔试） (kamacoder.com)

没什么好说的，先整体逆置，在前 $k$ 个逆置，最后剩余的逆置，代码如下：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;int main()
{int k = 0;string s;cin>>k;cin>>s;reverse(s.begin(),s.end());reverse(s.begin(),s.begin()+k);reverse(s.begin()+k,s.end());cout << s;return 0;
}

运行结果如下：