一、最长回文子串

最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。

讲解：

我们这里使用的是中心扩展方法，其实类似于暴力枚举，但是时间复杂度O（n*n）。算法的思路时固定一个位置，从中心开始，向两边扩展，如果最左边的值等于最右边时（满足回文串）。再左边向左走，右边向右走（前提不要越界）。
在求出长度即可和原来比较，返回值从begin到len。我们上面所说的是奇数扩展，偶数扩展让right等于left下一个位置

begin用来记录起始位置，len记录每次变化的长度。如果比原来大，就更新给len。

草图如下：

class Solution {
public:string longestPalindrome(string s) {//中心扩展int begin=0,len=0,n=s.size();for(int 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进0，如果俩数相加等于2，直接变零，不等于2，那就直接模2即可（结果是多少就多少），t%2表示运算最终结果，t/2表示进到下一位。

我们这里直接使用俩个指针遍历俩字符串数组的末尾，不过最终返回结果要逆序。

class Solution {
public:string addBinary(string a, string b) {string ret;//存放新的数组int cur1=a.size()-1,cur2=b.size()-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;}
};

附录：

开始做这道题没懂t是怎么运用的，原来让t是遍历俩字符串数组。贯穿进去的。

---

三、字符串相乘

字符串相乘原题

---

讲解：

这里讲解下思路;类似于模拟列竖式运算的方法，只不过这里模拟的时候，中间过程没有进位，最终结果统一进位。但是你会发现，这个方法结果算下来是对的。
然后在讲解下代码：首先反准下。分四部进行。我们给俩字符串都弄个下标（如下图绿色部分）。数组大体思路是 我们来定义个tmp数组来存放无进位相乘再相加的结果，存放进位结果的时候我们要注意：存放的位置应该放哪里？存放的位置应该是俩数相乘的下标（例如：3和5相乘时，放在数组下标1的位置.3对应下标0，5下标是1。再和3和4相乘的结果相加）。

处理完进位后，注意前导零。比如说。一个数和0相乘，结果只要一个0，但是会出现多个0，我们只需要保存一个0即可。当最终结果大于1且都是0时，保留一个字符0即可。最后还要反转回来。reverse下。

class Solution {
public:string multiply(string n1, string n2) {//先无进位相乘//先反转int m=n1.size(),n=n2.size();reverse(n1.begin(),n1.end());reverse(n2.begin(),n2.end());vector<int>tmp(m+n-1);//第二步，无进位相乘再相加for(int i=0;i<m;i++){for(int j=0;j<n;j++){tmp[i+j]+=(n1[i]-'0')*(n2[j]-'0');}}//处理进位int cur=0,t=0;string res;while(cur<m+n-1||t!=0){if(cur<m+n-1)   t+=tmp[cur++];res+=t%10+'0';t/=10;}//处理前导0while(res.size()>1&&res.back()=='0')    res.pop_back();reverse(res.begin(),res.end());return res;}
};

---

今日分享这里