仅仅反转字母
双指针
我们使用 left 指针从左边开始扫描字符串s, right指针从右边开始扫描字符串 s。如果两个指针都扫描到字母，且 left<right，那么交换 s[left] 和 s[right]，然后继续进行扫描；否则表明反转过程结束，返回处理后的字符串。
class Solution { public: bool letter(char ch) { if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) { return true; } else{ return false; } } string reverseOnlyLetters(string s) { int begin=0; int end=s.size()-1; while(begin<end) { while(begin<end&&!letter(s[begin])) { ++begin; } while(begin<end&&!letter(s[end])) { --end; } swap(s[begin],s[end]); ++begin; --end; } return s; } };
哈希表
class Solution { public: string reverseOnlyLetters(string s) { map<int,char> no; int len=s.size()-1; string m; for(int i=len;i>=0;i--) { if(isalpha(s[i])) { m+=s[i]; } else{ no[i]=s[i]; } } for(auto it=no.begin();it!=no.end();it++) { m.insert(it->first,1,it->second); } return m; } };
用栈处理
class Solution { public: //栈 string reverseOnlyLetters(string s) { stack<char> a; int len=s.size()-1; string m; for(int i=0;i<=len;i++) { if(isalpha(s[i])) { a.push(s[i]); } } for(int i=0;i<=len;i++) { char ch; if(isalpha(s[i])) { ch=a.top(); a.pop(); } else{ ch=s[i]; } m+=ch; } return m; } };
字符串中的第一个唯一字符
数组下标
class Solution { public: int firstUniqChar(string s) { int count[26]={0}; int len=s.size()-1; for(int i=0;i<=len;i++) { count[s[i]-'a']++; } for(int i=0;i<=len;i++) { if(count[s[i]-'a']==1) { return i; } } return -1; } };
哈希表
class Solution { public: int firstUniqChar(string s) { unordered_map<char,int> a; int len=s.size()-1; for(int i=0;i<=len;i++) { a[s[i]]++; } for(int i=0;i<=len;i++) { if(a[s[i]]==1) { return i; } } return -1; } };
字符串最后一个单词的长度
#include<iostream> using namespace std; int main() { string s; while(getline(cin,s)) { int pos=s.rfind(' '); cout<<s.size()-1-pos<<endl; } return 0; }
验证回文串
class Solution { public: bool isletter(char ch) { //判断是否是字母或者是数字 if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) { return true; } else{ return false; } } bool isPalindrome(string s) { //先把大写字母转换成小写字母 for(auto& ch:s) { if(ch>='a'&&ch<='z') { ch-=32; } } int begin=0,end=s.size()-1; while(begin<end) { //判断是否是字母或者是数字，不是就一直走 while(begin<end&&!isletter(s[begin])) { ++begin; } while(begin<end&&!isletter(s[end])) { --end; } //当到这里，说明这两个数是字母或者数字,判断是否相等 if(s[begin]!=s[end]) { return false; } //如果相等继续移动指针比较后面的，如果不相等，上一步直接返回false else{ ++begin; --end; } } return true; } };
字符串相加
class Solution { public: //大数相加 //从后往前加+=，以后再用reverse反转过来 // 123 // + 48 string addStrings(string num1, string num2) { int end1=num1.size()-1; int end2=num2.size()-1; int value1=0,value2=0,next=0; int addret=0; string sum; while(end1>=0||end2>=0) { if(end1>=0) { value1=num1[end1--]-'0'; } else{ value1=0; } if(end2>=0) { value2=num2[end2--]-'0'; } else{ value2=0; } addret=value1+value2+next; if(addret>9) { next=1; addret-=10; } else{ next=0; } sum+=(addret+'0'); } if(next==1) { sum+='1'; } reverse(sum.begin(),sum.end()); return sum; } };
反转字符串||
我们直接按题意进行模拟：反转每个下标从 2k2k 的倍数开始的，长度为 kk 的子串。若该子串长度不足 kk，则反转整个子串。
class Solution { public: string reverseStr(string s, int k) { int n = s.length(); for (int i = 0; i < n; i += 2 * k) { reverse(s.begin() + i, s.begin() + min(i + k, n)); } return s; } };
反转字符串中的单词|||
class Solution { public: string reverseWords(string s) { if(s.size()==1||s.size()==0) return s; //如果s的长度为0或者1就没必要有后续了； int i = 0, j = 0; //定义“双指针”吧，i后面用来指向单词end()，j用来指向单词第一个； for(auto ch:s){ if(ch==' '){ reverse(&s[j],&s[i]); //翻转单词 j=i+1; //反复指向单词首个字符 } ++i; } if(s[s.size()-1]!=' ') //如果最后一个单词最后字符不是空格，那还得翻转一次 reverse(&s[j],&s[i]); return s; } };
字符串相乘
在相乘或者相加计算过程的每一位，我们可以考虑先不去满10进位，等到计算完所有的相乘结果以后，最终将其加到一块，再去满10进位 ，最后的结果和普通竖式 一样，但却可以大大简化我们的模拟过程。(如下图所示)
1、长度是n和长度是m的数字相乘，最多只有n + m位，为了方便计算，将num1和num2反向存储到A[]和B[]中，即位数低的在数组前面，且开一个大小是n + m的C[]存储计算后的答案。
2、两个数相乘时，将A[i] * B[j]的结果累加到C[i + j]中，最后C[i + j]表示i + j这个位数的值是C[i + j](如上图所示)
3、由于C[]数组中的某些位数字可能是大于等于10的，我们从0枚举到n + m - 1，进行满10进位， 将所有位的值全部变成个位数。
4、最后将C[]数组反转输出。
class Solution { public: string multiply(string num1, string num2) { vector<int> A, B; int n = num1.size(), m = num2.size(); for (int i = n - 1; i >= 0; i -- ) A.push_back(num1[i] - '0'); //反向存贮 for (int i = m - 1; i >= 0; i -- ) B.push_back(num2[i] - '0'); vector<int> C(n + m); for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) C[i + j] += A[i] * B[j]; int t = 0; //存贮进位 for (int i = 0; i < C.size(); i ++ ) { t += C[i]; C[i] = t % 10; t /= 10; } int k = C.size() - 1; while (k > 0 && !C[k]) k -- ; //去除前导0 string res; while (k >= 0) res += C[k -- ] + '0'; //反转 return res; } };
找出字符串中第一个只出现一次的字符
这一题和上面一题极为相似,那题我用了数组下标做的，这题当然也是可以,不过换个思路做，拓展下知识面.
#include<iostream> using namespace std; int main() { string s; while(getline(cin,s)) { for(int i=0;i<s.size();i++) { if(s.find_first_of(s[i])==s.find_last_of(s[i]))//从前往后找,从后往前找，如果是同 一个数那说明这个是第一个只出现了一次,返回该字母 { cout<<s[i]<<endl; break; } //如果走到最后还没有找到，说明没有，返回-1 if(i==s.size()-1) { cout<<-1<<endl; } } } return 0; }
