c++：string相关的oj题（415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III）

1. 415. 字符串相加

传送门

题目详情

代码1

class Solution {
public:string addStrings(string num1, string num2) {int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位int next=0;//进位string retStr;while(index1>=0||index2>=0)//还有一个没完就要进来：有可能一直进位{int val1=0,val2=0; if(index1>=0){val1=num1[index1--]-'0';}if(index2>=0){val2=num2[index2--]-'0';}int ret=next+val1+val2;//两者相加后加上进位数next=ret/10;//需要进位就是1了，不需要就是0ret%=10;retStr.insert(0,1,'0'+ret);//头插到新string}//最后有可能有1+9的情况,现在只会有0if(next==1){retStr.insert(0,1,'1');}return retStr;}
};

思路1

1. 首先，定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位，用来从后往前遍历字符串。
2. 然后定义一个变量 next 用来表示进位，初始化为 0。
3. 接下来使用一个循环来遍历两个字符串，直到 index1 和 index2 都小于 0。在循环中，每次取出 index1 和 index2 对应位置的数字，并将它们与进位相加，得到一个临时的结果 ret。
4. 然后更新进位 next 为 ret/10，并将 ret%10 插入到需要返回的字符串 retStr 的开头。
5. 循环结束后，还需要检查最后是否有进位，如果有，需要将进位插入到结果字符串的开头。

但此时还是有一个问题的，那就是效率低（因为头插时间复杂度O（N^2））;

代码2

class Solution {
public:string addStrings(string num1, string num2) {int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位int next=0;//进位string retStr;while(index1>=0||index2>=0)//还有一个没完就要进来：有可能一直进位{int val1=0,val2=0; if(index1>=0){val1=num1[index1--]-'0';}if(index2>=0){val2=num2[index2--]-'0';}int ret=next+val1+val2;//两者相加后加上进位数next=ret/10;//需要进位就是1了，不需要就是0ret%=10;//使用尾插效率更好,尾插有append，这里我们使用+=retStr+='0'+ret;}//最后有可能有1+9的情况,现在只会有0if(next==1){retStr+='1';}reverse(retStr.begin(),retStr.end());//尾插后，最后翻转一下return retStr;}
};

思路2

整体思路都是一样的，只不过有头插换成了尾插+翻转

2. 125. 验证回文串

传送门

题目详情

代码1（按照要求修改后放到新string里）

class Solution {
public:bool isPalindrome(string s) {string re;for(auto e:s)//按照要求修改好{if((e>='A'&&e<='Z')||(e>='a'&&e<='z')||(e>='0'&&e<='9')){if(e>='A'&&e<='Z'){re+=(e+32);}else{re+=e;}}}string modified(re);reverse(re.begin(),re.end());       //看看是否相同for(int i=0;i<modified.size();i++){if(re[i]!=modified[i]){return false;}}return true;}

思路1

1. 遍历输入字符串 s 中的每个字符 e。
   如果字符 e 是字母或数字，则根据题目要求将大写字母转换为小写字母，并将其添加到新的字符串 re 中。

2. 创建一个新的字符串 modified，它是字符串 re 的一个副本。

3. 反转字符串 re。

4. 比较反转后的字符串 re 和副本字符串 modified，如果它们不相等，则返回 false，表示不是回文字符串；如果它们相等，则返回 true，表示是回文字符串

代码2(利用双指针/索引)

bool isLetterOrNumber(char ch)
{return (ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9');
}class Solution {
public:bool isPalindrome(string s) {for(auto& e:s)//大的变小的{if(e>='A'&&e<='Z'){e+=32;}}int begin=0;int end=s.size()-1;while(begin<end){while(begin<end&&!isLetterOrNumber(s[begin])){begin++;}while(begin<end&&!isLetterOrNumber(s[end])){--end;}if(s[begin]!=s[end]){return false;}else{++begin;--end;}}return true;}
};

思路2

1. 创建一个辅助函数 isLetterOrNumber，用于判断一个字符是否是字母或数字。
2. 遍历输入字符串 s 中的每个字符 e，将大写字母转换为小写字母。
3. 初始化两个指针 begin 和 end，分别指向字符串的开头和结尾。
4. 在一个 while 循环中，不断移动指针 begin 和 end，直到两个指针相遇。
   在移动指针的过程中，跳过非字母和数字的字符。
5. 在二者都是数字或者字母后，比较指针指向的字符，如果不相等，则返回 false，表示不是回文字符串；如果相等，则继续移动指针。
6. 如果循环结束后都没有返回 false，则说明是回文字符串，返回 true。

3. 541. 反转字符串 II

传送门

题目详情

代码1

class Solution {
public:string reverseStr(string s, int k) {int len=s.size();for(int i=0;i<len;i+=2*k){if(i+k<=len)//剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符//同时前面的2k区域不用管，直接满足，只有最后那个不够2k的区间才讨论{reverse(s.begin()+i,s.begin()+i+k);}else{reverse(s.begin()+i,s.begin()+len);}}return s;}
};

思路1

利用每次要跳2k来处理：就直接i+=2k，这样每次直接跳到下一个区间，前面够2k的不用管，直接满足i+k<=len，只有那最后一个不够2k的需要讨论（毕竟s.begin()+len是最后元素的下个位置）

4. 557. 反转字符串中的单词 III

传送门

题目详情

代码1（利用find）

class Solution {
public:string reverseWords(string s) {size_t pos=0;int i=0;while(i<s.size()){pos=s.find(' ',i);if(pos==string::npos)//只有一个单词了{reverse(s.begin()+i,s.end());break;}reverse(s.begin()+i,s.begin()+pos);i=(pos+1);}return s;}
};

思路1

总体思路是找到单词的左和右索引，在这个区间内进行翻转

1. 利用一个i 对字符串进行遍历，pos来储存找到的' '的下标
2. 那么从i到pos就是一个单词加上’ '，正好满足reserve()函数左闭右开的性质
3. 然后i=pos+1（跳到空格后）
4. 如果没找到空格，就说明只剩下一个，或者只有一个单词。 就直接i到end（）进行翻转了

代码2（利用双指针）

class Solution {
public:string reverseWords(string s) {int i=0;while(i<s.size())//直接进循环{int left=i;//存一下起始位置while(i<s.size()&&s[i]!=' ')//找空格{i++;}//现在要么找到了，要么到size处了int right=i-1;while(left<right)//开始换{swap(s[left],s[right]);left++;right--;}if(s[i]==' '){i++;}}return s;}
};

思路2

总体思路是一样的，不过自己找，没有利用find

---

今天就到这里啦！