一、最长回文子串

最长回文子串
给你一个字符串 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;
        }

        //处理前导0
        while(res.size()>1&&res.back()=='0')    res.pop_back();

        reverse(res.begin(),res.end());
        return res;

    }
};

---

今日分享这里