算法训练营第八天：字符串反转与替换实战

算法训练营第八天

• 昨日回顾
• 344.反转字符串
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
• 541.反转字符串Ⅱ
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
• 54.替换数字
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
• 坚持就是胜利

昨日回顾

• 四数相加和两数相加本质一样，使用哈希分组可以降低时间复杂度
• 赎金信和之前的字母异位词原理相同，区别在于前者有一个包含关系，够用就行，后一个要求内容完全相等。
• 三数之和以及四数之和重点在于去重。结果去重，开销很大，会超时，所以就要在过程中去重。哈希和双指针两种方法

344.反转字符串

卡哥文字以及视频讲解链接

重点

• 典型的双指针例题，左右指针相向运动。
• 和STL 中 std::reverse比较，库函数支持不同迭代器类型优化，底层实现会更复杂。但实现逻辑基本相同。
• swap函数，交换是高效的，通常是常数时间复杂度 O(1)，因为它只交换内部指针，而不是逐个复制元素。实现过程有临时变量法（以下代码中的实现就是），异或法（位运算）以及加减法。

c++实现

class Solution {
public:
void reverseString(vector<char>& s) {
for(int i = 0 , j = s.size() – 1 ; i < s.size() / 2 ; i++ ,j—){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
//以上三行可以换成swap(s[i],s[j]);
}
return;
}
};

541.反转字符串Ⅱ

卡哥文字以及视频讲解链接

重点

• 看起来题目很复杂，但实际都是无用信息。
• 关注的点只有是否还够k个字符，以及向后移动2k个字符是否越界。

c++实现

class Solution {
public:
string reverseStr(string s, int k) {
for(int i = 0 ; i < s.size() ; i += 2 * k){
if(i + k <= s.size()){
//i + k <= s.size()中的 <= 很关键
//题干要求，从i开始的k个元素，其实判断条件 i + k – 1 < s.size()更好理解
reverse(s.begin() + i , s.begin() + i + k);
//左闭右开
}else{
reverse(s.begin() + i , s.end());
}
}
return s;
}
};

54.替换数字

卡哥文字以及视频讲解链接

重点

• 从后往前，在原字符串上修改，空间复杂度O(1)。
• 从前往后就得一个新字符串了，浪费。
• 熟悉一下std库函数的使用，命名空间不一定必须写using namespace std;

c++实现

#include <iostream>
#include <string>

int main(){
std::string s;
// std::cout << "请输入一个带有字母和数字的字符串：" << std::endl;
std::cin >> s;
int count = 0;
for(char i : s){
if(i <= '9' && i >= '0'){
count++;
}
}
int i = s.size() – 1;
s.resize(s.size() + 5 * count);
//要清楚resize和reserve的区别
//resize才是改变字符串实际大小的函数
//reserve只是改变容量，访问后面的内容会越界
int j = s.size() – 1;
for( ; i >= 0 ; i—){
if(s[i] <= '9' && s[i] >= '0'){
s[j—] = 'r';
s[j—] = 'e';
s[j—] = 'b';
s[j—] = 'm';
s[j—] = 'u';
s[j—] = 'n';
}else{
s[j—] = s[i];
}
}
std::cout << s << std::endl;
}

坚持就是胜利

• 第一天，搞定！
• 第二天，搞定！
• 第三天，搞定！
• 第四天，搞定！
• 第五天，搞定！
• 第六天，搞定！
• 第七天，搞定！
• 第八天，搞定！

author