【代码随想录37期】Day08 反转字符串、反转字符串Ⅱ、替换数字、反转字符串里面的单词、右旋转字符串

本文主要是介绍【代码随想录37期】Day08 反转字符串、反转字符串Ⅱ、替换数字、反转字符串里面的单词、右旋转字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

反转字符串

解题思路：
数组双指针法：使用两个数组索引子来交换元素，调用自定义的swapElement函数或库函数swap都可以
注意：
1. 数组元素交换时，不能直接使用“=”号，因为这样只是将指针指向了同一个地址，而没有交换元素
2. 库函数swap只能用于基本数据类型，不能用于自定义数据类型
3. 库函数swap的参数类型必须一致，否则会报错
4. 库函数swap的参数类型不能是常量、引用、数组、指针，否则会报错
5. 双指针for循环的边界条件要注意，不能写成i < stringLen - 1，因为这样会漏掉最后一个元素，最好是带入检查一下

代码随想录

C++ swap函数（effective C++ 条款25）-CSDN博客


v1.0:
class Solution {
public:void swapElement(auto *x, auto *y){auto temp = *x;*x = *y;*y = temp;}void reverseString(vector<char>& s) {int stringLen = s.size();for(int i = 0, j = stringLen - 1; i < stringLen/2; i++, j--){swapElement(&s[i], &s[j]);}}
};v2.0:
1. 参考了swap库函数的实现来实现swapElement函数
2. 避免申请stringLen大小的临时变量，直接在原数组上交换元素,减少空间复杂度
3. 发现自己搞混了一些东西，引用不是不可以赋值，而是不能更改引用的对象，所以对swapElement的参数列表进行了修改
class Solution {
public:void swapElement(auto &x, auto &y){auto temp = x;x = y;y = temp;}void reverseString(vector<char>& s) {for(int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--){swapElement(s[i], s[j]);//swap(s[i], s[j]);}}
};

反转字符串Ⅱ

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码随想录

解题思路：
因为for循环的循环出现了规律，所以一定要在for循环中体现出来。
将题目的规则模拟出来即可。v1.0:
class Solution {
public:string reverseStr(string s, int k) {for(int i = 0; i < s.size(); i += 2 * k){if(i + k > s.size() - 1){reverse(s.begin() + i, s.end());}else{reverse(s.begin() + i, s.begin() + i + k);}}return s;}
};v2.0:
1. 参考reverse的实现定义了自己的reverseSubStr函数，在reverseStr函数中调用
2. 关于reverseSubStr的--last和first++，因为s.end()返回的是最后一个字符的下一个位置，所以要先--
3. 关于s.begin()和s.end()查看网址：https://img-blog.csdn.net/20180518122234389?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lzcTk2/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
class Solution {
public:template <class BidirectionalIterator>void reverseSubStr(BidirectionalIterator first, BidirectionalIterator last){while(first != last && first != --last){//确定两者的值是否相邻或相等iter_swap(first++, last);}}string reverseStr(string s, int k) {for(int i = 0; i < s.size(); i += 2 * k){if(i + k > s.size() - 1){reverseSubStr(s.begin() + i, s.end());}else{reverseSubStr(s.begin() + i, s.begin() + i + k);}}return s;}
};v3.0:
使用反转字符串.cpp的方法
class Solution {
public:void reverseString(vector<char>& s, int first, int last) {while(first < last){swap(s[first++], s[last--]);}}string reverseStr(string s, int k) {for (int i = 0; i < s.size(); i += 2 * k){if (i + k <= s.size() - 1) reverseString(s, i, i + k - 1);else reverseString(s, i, s.size() - 1);}return s;}
};

替换数字

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码随想录

数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

字符串string和字符数组char[] vector的区别

string拥有size()
char是用≠’/0’

字符串实际上是使用 null 字符 ‘\0’ 终止的一维字符数组。因此，一个以 null 结尾的字符串，包含了组成字符串的字符。

下面的声明和初始化创建了一个 “Hello” 字符串。由于在数组的末尾存储了空字符，所以字符数组的大小比单词 “Hello” 的字符数多一个。

v1.0

class Solution {
public:string pathEncryption(string path) {// int numsOfPoint = 0;// for(inti = 0; i < path.size(); i++){//     if(path[i]=='.')numsOfPoint++;// }//本题大小不变 不需要path.resize(path.size() + numsOfPoint)for(int i = 0; i < path.size(); i++ ){if(path[i]=='.'){path[i] = ' ';}}return path;}
};

v2.0

class Solution {
public:string pathEncryption(string path) {size_t pos = path.find(".");while(pos != string::npos){path.replace(pos, 1, " ");pos = path.find(".");}return path;}
};

反转字符串里面的单词

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码随想录

v1.0

class Solution {
public:string reverseWords(string s) {for(int i = 0; i <s.size() - 1; i++){if(s[i] == ' '&& s[i+1] == ' '){s.erase(s.begin() + i);}if(s.size()>0 && s[s.size() - 1]==' '){s.erase(s.end());}if(s.size()>0 && s[0]==' '){s.erase(s.begin());}}reverse(s.begin(), s.end());int j = 0;for(int i = 0; i < s.size(); i++){if(s[i]==' '){reverse(s.begin() + j, s.begin() + i - 1);j = i + 1;}}return s;}
};

问题：1. erase与for循环嵌套时间复杂度高

这个代码实际上非常容易错，因为随着erase，迭代器指代的不是我们希望的位置

v2.0：

class Solution {
public:string reverseWords(string s) {int fastIndex = 0, slowIndex = 0;//先去掉首部的空格while(s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' '){fastIndex++;}//去除中间多余的空格for(;fastIndex < s.size(); fastIndex++){if(fastIndex > 1 && s[fastIndex - 1] == ' '&&s[fastIndex]==' '){continue;}else{s[slowIndex] = s[fastIndex];slowIndex++;}}//去掉最后的空格，最后有三种情况：//1.没空格，此时慢指针就在最后一个元素上//2.有两个空格以上，此时慢指针不随快指针移动，停在最后一个元素上//3.有一个空格，此时慢指针会随快指针移动，停在最后一个空格上if(slowIndex > 1 && s[slowIndex - 1]==' '){s.resize(slowIndex-1);}else{s.resize(slowIndex);}//反转整个字符串reverse(s.begin(), s.end());//反转单词int j = 0;for(int i = 0; i <= s.size(); i++){if(s[i]==' ' || i == s.size()){reverse(s.begin() + j, s.begin() + i);j = i + 1;}}return s;}
};

v3.0

class Solution {
public:void removeExtraSpaces(string &s){int slowIndex = 0, fastIndex = 0;for(; fastIndex < s.size();fastIndex++){if(s[fastIndex] != ' '){//只处理不包含空格的部分if(slowIndex != 0){s[slowIndex++] = ' ';//首先加一个空格}while(s[fastIndex] != ' ' && fastIndex<s.size()){s[slowIndex++] = s[fastIndex++];//剩下不是空格的部分都加进来}}}s.resize(slowIndex);}string reverseWords(string s) {removeExtraSpaces(s);reverse(s.begin(), s.end());int j = 0;for(int i = 0;i<=s.size();i++){if(s[i]== ' '|| i ==s.size()){reverse(s.begin()+j, s.begin()+i);j = i + 1;}}return s;}
};

右旋转字符串

代码随想录

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

v1.0：

使用整体反转+局部反转就可以实现反转单词顺序的目的。

而使用局部反转+整体反转就可以实现反转字母顺序的目的

class Solution {
public:string dynamicPassword(string password, int target) {reverse(password.begin(), password.begin() + target);reverse(password.begin() + target, password.end());reverse(password.begin(), password.end());return password;}
};