网站建设合同2018,中国建设规划采购网站,深圳市建局官网,介绍企业的ppt文章目录 1. 415. 字符串相加题目详情代码1思路1代码2思路2 2. 125. 验证回文串题目详情代码1#xff08;按照要求修改后放到新string里#xff09;思路1代码2(利用双指针/索引)思路2 3. 541. 反转字符串 II题目详情代码1思路1 4. 557. 反转字符串中的单词 III题目详情代码1按照要求修改后放到新string里思路1代码2(利用双指针/索引)思路2 3. 541. 反转字符串 II题目详情代码1思路1 4. 557. 反转字符串中的单词 III题目详情代码1利用find思路1代码2利用双指针思路2 1. 415. 字符串相加
传送门
题目详情 代码1
class Solution {
public:string addStrings(string num1, string num2) {int index1num1.size()-1,index2num2.size()-1;//找到最后一位int next0;//进位string retStr;while(index10||index20)//还有一个没完就要进来有可能一直进位{int val10,val20; if(index10){val1num1[index1--]-0;}if(index20){val2num2[index2--]-0;}int retnextval1val2;//两者相加后加上进位数nextret/10;//需要进位就是1了不需要就是0ret%10;retStr.insert(0,1,0ret);//头插到新string}//最后有可能有19的情况,现在只会有0if(next1){retStr.insert(0,1,1);}return retStr;}
};思路1
首先定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位用来从后往前遍历字符串。然后定义一个变量 next 用来表示进位初始化为 0。接下来使用一个循环来遍历两个字符串直到 index1 和 index2 都小于 0。在循环中每次取出 index1 和 index2 对应位置的数字并将它们与进位相加得到一个临时的结果 ret。然后更新进位 next 为 ret/10并将 ret%10 插入到需要返回的字符串 retStr 的开头。循环结束后还需要检查最后是否有进位如果有需要将进位插入到结果字符串的开头。 但此时还是有一个问题的那就是效率低因为头插时间复杂度ON^2; 代码2
class Solution {
public:string addStrings(string num1, string num2) {int index1num1.size()-1,index2num2.size()-1;//找到最后一位int next0;//进位string retStr;while(index10||index20)//还有一个没完就要进来有可能一直进位{int val10,val20; if(index10){val1num1[index1--]-0;}if(index20){val2num2[index2--]-0;}int retnextval1val2;//两者相加后加上进位数nextret/10;//需要进位就是1了不需要就是0ret%10;//使用尾插效率更好,尾插有append这里我们使用retStr0ret;}//最后有可能有19的情况,现在只会有0if(next1){retStr1;}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((eAeZ)||(eaez)||(e0e9)){if(eAeZ){re(e32);}else{ree;}}}string modified(re);reverse(re.begin(),re.end()); //看看是否相同for(int i0;imodified.size();i){if(re[i]!modified[i]){return false;}}return true;}思路1 遍历输入字符串 s 中的每个字符 e。 如果字符 e 是字母或数字则根据题目要求将大写字母转换为小写字母并将其添加到新的字符串 re 中。 创建一个新的字符串 modified它是字符串 re 的一个副本。 反转字符串 re。 比较反转后的字符串 re 和副本字符串 modified如果它们不相等则返回 false表示不是回文字符串如果它们相等则返回 true表示是回文字符串
代码2(利用双指针/索引)
bool isLetterOrNumber(char ch)
{return (chAchZ)||(chachz)||(ch0ch9);
}class Solution {
public:bool isPalindrome(string s) {for(auto e:s)//大的变小的{if(eAeZ){e32;}}int begin0;int ends.size()-1;while(beginend){while(beginend!isLetterOrNumber(s[begin])){begin;}while(beginend!isLetterOrNumber(s[end])){--end;}if(s[begin]!s[end]){return false;}else{begin;--end;}}return true;}
};思路2
创建一个辅助函数 isLetterOrNumber用于判断一个字符是否是字母或数字。遍历输入字符串 s 中的每个字符 e将大写字母转换为小写字母。初始化两个指针 begin 和 end分别指向字符串的开头和结尾。在一个 while 循环中不断移动指针 begin 和 end直到两个指针相遇。 在移动指针的过程中跳过非字母和数字的字符。在二者都是数字或者字母后比较指针指向的字符如果不相等则返回 false表示不是回文字符串如果相等则继续移动指针。如果循环结束后都没有返回 false则说明是回文字符串返回 true。
3. 541. 反转字符串 II
传送门
题目详情 代码1
class Solution {
public:string reverseStr(string s, int k) {int lens.size();for(int i0;ilen;i2*k){if(iklen)//剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符//同时前面的2k区域不用管直接满足只有最后那个不够2k的区间才讨论{reverse(s.begin()i,s.begin()ik);}else{reverse(s.begin()i,s.begin()len);}}return s;}
};思路1
利用每次要跳2k来处理就直接i2k这样每次直接跳到下一个区间前面够2k的不用管直接满足iklen只有那最后一个不够2k的需要讨论毕竟s.begin()len是最后元素的下个位置
4. 557. 反转字符串中的单词 III
传送门
题目详情 代码1利用find
class Solution {
public:string reverseWords(string s) {size_t pos0;int i0;while(is.size()){poss.find( ,i);if(posstring::npos)//只有一个单词了{reverse(s.begin()i,s.end());break;}reverse(s.begin()i,s.begin()pos);i(pos1);}return s;}
};思路1
总体思路是找到单词的左和右索引在这个区间内进行翻转
利用一个i 对字符串进行遍历pos来储存找到的 的下标那么从i到pos就是一个单词加上’ 正好满足reserve()函数左闭右开的性质然后ipos1跳到空格后如果没找到空格就说明只剩下一个或者只有一个单词。 就直接i到end进行翻转了
代码2利用双指针
class Solution {
public:string reverseWords(string s) {int i0;while(is.size())//直接进循环{int lefti;//存一下起始位置while(is.size()s[i]! )//找空格{i;}//现在要么找到了要么到size处了int righti-1;while(leftright)//开始换{swap(s[left],s[right]);left;right--;}if(s[i] ){i;}}return s;}
};思路2
总体思路是一样的不过自己找没有利用find 今天就到这里啦
