【C++】string的经典算法题

文章目录仅仅反转字母找字符串中第一个只出现一次的字符字符串里面最后一个单词的长度验证一个字符串是否是回文字符串相加翻转字符串II区间部分翻转翻转字符串III翻转字符串中的单词字符串相乘找出字符串中第一个只出现一次的字符仅仅反转字母classSolution{public:boolisLetter(charch){if(chachz)returntrue;if(chAchZ)returntrue;returnfalse;}stringreverseOnlyLetters(string S){if(S.empty())returnS;size_t begin0,endS.size()-1;while(beginend){while(beginend!isLetter(S[begin]))begin;while(beginend!isLetter(S[end]))--end;swap(S[begin],S[end]);begin;--end;}returnS;}};找字符串中第一个只出现一次的字符classSolution{public:intfirstUniqChar(string s){// 统计每个字符出现的次数intcount[256]{0};intsizes.size();for(inti0;isize;i)count[s[i]]1;// 按照字符次序从前往后找只出现一次的字符for(inti0;isize;i)if(1count[s[i]])returni;return-1;}};classSolution{public:intfirstUniqChar(string s){intcount[26]{0};for(autoch:s){count[ch-a];}//遍历第一个字符的countfor(size_t i0;is.size();i){if(count[s[i]-a]1)returni;}return-1;}};字符串里面最后一个单词的长度rfind是倒着找operator从流中提取字符串operator将字符串插入流左闭右开的区间数据个数左减右例如[0,10)个数10左闭右闭的区间数据个数左减右加一例如[0,9]个数10getline只识别换行不识别空格还可以自定义字符结束#includeiostream#includestringusingnamespacestd;intmain(){string str;getline(cin,str);size_t posstr.rfind( );//有可能没有空格if(pos!string::npos)coutstr.size()-(pos1)endl;elsecoutstr.size()endl;return0;}验证一个字符串是否是回文classSolution{public:boolisLetterOrNumber(charch){return(ch0ch9)||(chachz)||(chAchZ);}boolisPalindrome(string s){// 先小写字母转换成大写再进行判断for(autoch:s){if(chachz)ch-32;}intbegin0,ends.size()-1;while(beginend){while(beginend!isLetterOrNumber(s[begin]))begin;while(beginend!isLetterOrNumber(s[end]))--end;if(s[begin]!s[end]){returnfalse;}else{begin;--end;}}returntrue;}};字符串相加classSolution{public:stringaddStrings(string num1,string num2){string s3;intcarry0;intend1num1.size()-1,end2num2.size()-1;while(end10||end20){intval1end10?num1[end1--]-0:0;intval2end20?num2[end2--]-0:0;intretval1val2carry;carryret/10;retret%10;s3(ret0);}if(carry)s31;reverse(s3.begin(),s3.end());returns3;}};翻转字符串II区间部分翻转classSolution{public:stringreverseStr(string s,intk){intns.length();//当剩余字符在 k 到 2k 之间时会跳过for(inti0;in;i2*k){reverse(s.begin()i,s.begin()min(ik,n));}returns;}};分析如果 i k n那么 last i k反转从 i 到 ik-1 的字符即前 k 个。如果 i k n那么 last n反转从 i 到 n-1 的字符即剩余的全部字符。这正好处理了剩余字符少于 k 的情况。当剩余字符在 k 到 2k 之间时i k 可能小于 n所以反转前 k 个后面的保持不变。注意因为 i 每次增加 2k所以下一个块从 i2k 开始而当前块的后 k 个字符如果有不会被反转符合要求。翻转字符串III翻转字符串中的单词classSolution{public:stringreverseWords(string s){string ret;intlengths.length();inti0;while(ilength){//记录单词开始位置startintstarti;while(ilengths[i]! ){i;}//单词区间[start,i)//反向索引for(intpstart;pi;p){ret.push_back(s[starti-1-p]);}//插入了单词后插入空格长度while(ilengths[i] ){ret.push_back( );i;}}returnret;}};字符串相乘classSolution{public:if(num10||num20)return0;//ans初始化为0string ans0;intmnum1.size(),nnum2.size();//先乘数字2的最低位for(intin-1;i0;i--){string curr;//carry是进位intcarry0;//除了第一次其余要给curr也加上n-1-i个0for(intjn-1;ji;j--){curr0;}//现在处理当前位i//将num2[i]转换为数字处理intynum2[i]-0;//数字1从后往前的每一位和数字2的其中一位相乘for(intjm-1;j0;j--){intxnum1[j]-0;intretx*ycarry;carryret/10;retret%10;curr(ret0);}//继续处理进位while(carry){curr(carry%100);carry/10;}reverse(curr.begin(),curr.end());ansaddStrings(ans,curr);}returnans;}//字符串相加的代码stringaddStrings(string num1,string num2){string s3;intcarry0;intend1num1.size()-1,end2num2.size()-1;while(end10||end20){intval1end10?num1[end1--]-0:0;intval2end20?num2[end2--]-0:0;intretval1val2carry;carryret/10;retret%10;s3(ret0);}if(carry)s31;reverse(s3.begin(),s3.end());returns3;}};找出字符串中第一个只出现一次的字符#includeiostreamusingnamespacestd;//找出第一个只出现一次的字符的代码classSolution{public:intfirstUniqChar(string s){intcount[26]{0};for(autoch:s){count[ch-a];}for(size_t i0;is.size();i){if(count[s[i]-a]1)returni;}return-1;}};intmain(){Solution s;string str;cinstr;intress.firstUniqChar(str);if(res!-1)coutstr[res];elsecoutres;return0;}