一、最长公共前缀
思路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];//可能只有一个字符串
}
};二、最长回文子串
解法：中心扩展算法
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);
}
};三、二进制求和（字符串相加）
解法：模拟进位相加，但是区别就是得逢2进1 ，再将最后的结果逆序。
class Solution {
public:
string addBinary(string a, string b) {
//模拟进位相加，但是区别就是逢2进1
size_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） 最后会接受到最后一个字符串
五、仅仅翻转字母
非英文字符保存在原地，而英文字母翻转，所以我们可以用双指针分别指向字符串的首尾位置，如果遇到非字母的就往中间靠，当两个指针指向的都是字母的时候，交换两个指针指向的字母即可
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;
}
};六、验证回文串
验证回文串，只需要用双指针指向首尾的位置，对非字母数字的直接跳过，当两个指针停下来的时候判断对应位置的字母是不是相同的。
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
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;
}
};九、字符串相乘（重点）
class Solution {
public: //从后往前不需要处理前导0
string 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) //为了高位的补0
cur.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进1
size_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、然后处理前导0
size_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 处理前导0
while(ret.size()>1&&ret.back()=='0') ret.pop_back();
reverse(ret.begin(),ret.end());
return ret;
}
};十、字符串中常用的一些接口
C语言相关：
C++相关：
