一、最长公共前缀
. - 力扣(LeetCode)
思路1:两两比较 时间复杂度mn 实现findcomon返回两两比较后的公共前缀
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {//两两比较 string ret=strs[0];size_t n=strs.size();for(size_t i=0;i<n;++i)ret=findcommon(ret,strs[i]);return ret;}string findcommon(string&s1,string&s2){size_t n=min(s1.size(),s2.size());size_t i=0;for(;i<n;++i)if(s1[i]!=s2[i]) break;return s1.substr(0,i);}
};
思路2:统一比较 时间复杂度mn
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {//统一比较size_t m=strs.size(),n=strs[0].size();for(int i=0;i<n;++i){char temp=strs[0][i];for(int j=0;j<m;++j)if(i==strs[j].size()||strs[j][i]!=temp)return strs[0].substr(0,i); }return strs[0];//可能只有一个字符串}
};
二、最长回文子串
. - 力扣(LeetCode)
解法:中心扩展算法
1、固定一个中心点,从中心点开始往两边扩展
2、要考虑奇数长度,也要考虑偶数长度
class Solution {
public:string longestPalindrome(string s) {size_t begin=0; size_t len=0;//帮助我们记录符合要求的回文子串//中心扩展算法size_t n=s.size();for(size_t i=0;i<n;++i){int left=i,right=i;//考虑奇数回文串while(left>=0&&right<n&&s[left]==s[right]) {--left;++right;}if(right-left-1>len) {begin=left+1;len=right-left-1;}//考虑偶数回文串left=i;right=i+1;//考虑奇数回文串while(left>=0&&right<n&&s[left]==s[right]) {--left;++right;}if(right-left-1>len) {begin=left+1;len=right-left-1;}}return s.substr(begin,len);}
};
三、二进制求和(字符串相加)
. - 力扣(LeetCode)
解法:模拟进位相加,但是区别就是得逢2进1 ,再将最后的结果逆序。
class Solution {
public:string addBinary(string a, string b) {//模拟进位相加,但是区别就是逢2进1size_t n1=a.size(),n2=b.size();string ret;//返回 从后往前模拟进位相加ret.reserve(n1>n2?n1+1:n2+1);//提前开空间 减少时间消耗int cur1=n1-1; int cur2=n2-1;int t=0;while(cur1>=0||cur2>=0||t) //可能会有进位的遗失{if(cur1>=0) t+=a[cur1--]-'0';if(cur2>=0) t+=b[cur2--]-'0';ret+=t%2+'0';t/=2;}reverse(ret.begin(),ret.end());//结果要反转一下return ret;}
};
四、字符串最后一个单词的长度
字符串最后一个单词的长度_牛客题霸_牛客网
该题不能用cin>>s 因为遇到空格就会停止,所以要解决这个问题就必须用getline
而string中的rfind可以帮助我们从后往前找。
#include <iostream>
using namespace std;int main()
{string s;getline(cin,s);//接受一个带空格的字符串cout<<s.size()-1-s.rfind(" ")<<endl;//while(cin>>s);//cout<<s.size();return 0;
}
因为该题凑巧找的是最后一个,所以也可以直接用while(cin>>s) 最后会接受到最后一个字符串
五、仅仅翻转字母
. - 力扣(LeetCode)
非英文字符保存在原地,而英文字母翻转,所以我们可以用双指针分别指向字符串的首尾位置,如果遇到非字母的就往中间靠,当两个指针指向的都是字母的时候,交换两个指针指向的字母即可
class Solution {
public:string reverseOnlyLetters(string s){//双指针法size_t begin=0;size_t end=s.size()-1;while(begin<end){while(begin<end&&!isalpha(s[begin])) ++begin;while(begin<end&&!isalpha(s[end])) --end;swap(s[begin],s[end]);++begin;--end;}return s;}
};
六、验证回文串
. - 力扣(LeetCode)
验证回文串,只需要用双指针指向首尾的位置,对非字母数字的直接跳过,当两个指针停下来的时候判断对应位置的字母是不是相同的。
class Solution {
public:bool isPalindrome(string s){//双指针往中间靠,直到相遇则回文 int length=s.size();int left=0,right=length-1;while(left<right){while(left<right&&!isalnum(s[left])) ++left;while(left<right&&!isalnum(s[right])) --right;if(left<right)if(tolower(s[left])!=tolower(s[right]))return false;++left;--right;}return true;}
};
七、反转字符串II
. - 力扣(LeetCode)
class Solution {
public:string reverseStr(string s, int k){int n=s.size();for(int i=0;i<n;i+=2*k)reverse(s.begin()+i,s.begin()+min(i+k,n));return s;}
};
需要注意的是如果i+k超过了n,就要将他修正为n。
八、反转字符串III
双指针,始终让两个指针指向字符串中某个单词的头和尾,然后进行反转。
class Solution {
public:string reverseWords(string s){int head=0,tail=0;//双指针法int length=s.size();while(head<length){if(s[head]!=' '){while(tail<length&&s[tail]!=' ')++tail;reverse(s.begin()+head,s.begin()+tail);}++tail;head=tail;}return s;}
};
九、字符串相乘(重点)
. - 力扣(LeetCode)
class Solution {
public: //从后往前不需要处理前导0string multiply(string num1, string num2){ //高位相乘补0 处理前导0 最后处理进位if(num1=="0"||num2=="0") return "0";string ret="0";//处理返回值 方便进行相加int m = num1.size(), n = num2.size();for(int i=n-1;i>=0;--i){string cur;int add=0;//处理进位for(int j=n-1;j>i;--j) //为了高位的补0cur.push_back('0');int y=num2[i]-'0';//取出这一位for(int j=m-1;j>=0;--j){int x=num1[j]-'0';int product=x*y+add;cur.push_back(product%10+'0');add=product/10;//保留进位}while(add!=0){cur.push_back(add%10+'0');add/=10;}reverse(cur.begin(),cur.end());ret= addBinary(ret, cur);}return ret;}string addBinary(string a, string b) {//模拟进位相加,但是区别就是逢2进1size_t n1=a.size(),n2=b.size();string ret;//返回 从后往前模拟进位相加ret.reserve(n1>n2?n1+1:n2+1);//提前开空间 减少时间消耗int cur1=n1-1; int cur2=n2-1;int t=0;while(cur1>=0||cur2>=0||t) //可能会有进位的遗失{if(cur1>=0) t+=a[cur1--]-'0';if(cur2>=0) t+=b[cur2--]-'0';ret+=t%10+'0';t/=10;}reverse(ret.begin(),ret.end());//结果要反转一下return ret;}
};
class Solution {
public:string multiply(string num1, string num2) {//处理相乘问题->1、先无进位相乘 2、然后相加 3、然后处理进位 4、然后处理前导0size_t m=num1.size(),n=num2.size();//准备工作,模拟进位前将两个字符串先进行逆序reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());vector<size_t> temp(m+n-1);for(size_t i=0;i<m;++i) //无进位相乘for(size_t j=0;j<n;++j) temp[i+j]+=(num1[i]-'0')*(num2[j]-'0');//无进位相乘后累加//处理进位size_t cur=0,t=0;//t是进位信息string ret;ret.reserve(m+n);//优化一下,提前开空间while(cur<m+n-1||t) {if(cur<m+n-1) t+=temp[cur++];ret+=t%10+'0';t/=10;}//3 处理前导0while(ret.size()>1&&ret.back()=='0') ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};
十、字符串中常用的一些接口
C语言相关:
C语言:字符函数和字符串函数-CSDN博客
C++相关:
C++:String类的使用-CSDN博客