女朋友跟我说“爱你爱你”，我首先想到的竟是“回文数”！

今天是2020年02月02日，传说中千年一遇的完全对称日。同时，2020又谐音“爱你爱你”。在如此特殊的日子里，你难道不想干点什么吗？当然，专家建议疫情期间少出门。

当女朋友早上兴冲冲地跟我说 “今天是20200202” 的时候，我的第一反映竟然是！

这不是个回文数吗？然后脑子里开始快速闪过一段又一段讳莫如深的代码...

emmmm......别问我为什么能有女朋友！

01

回文数

Leetcode 09 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。比如20200202就是一个回文数。

判断回文数有三种解法：

1 一般解法

将整数转为字符串，然后将字符串分割为数组，通过循环数组的一半长度进行判

断对应的元素是否相等。

（代码略）

2 除法操作

通过取整和取余操作获得整数中对应的数字进行比较。

举个例子：20200202 这个数字。

通过计算 20200202 / 1000000， 得首位2

通过计算 20200202 % 10000000， 可得末位 2

将首位和末位进行比较，再将第2位0和倒数第2位0取出来继续比较。

代码：

class Solution {
public:
    bool isPalindrome(int x) {
        //边界判断
        if (x < 0) return false;
        int div = 1;
        //
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
};

3 对折解法

取出后半段数字进行翻转，看与前半段数字是否相同。

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

02

最长回文子串

Leetcode 5 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。比如"babad"中最长的回文字串是bab或者aba；比如“cbbd”中最长的回文字串是bb。

求最长回文字串的解法有很多，这里主要介绍四种。

1 暴力解法

列举所有的子串，判断是否为回文串，保存最长的回文串。

时间复杂度：两层 for 循环 O(n²）O(n²），for 循环里边判断是否为回文 O(n）O(n），所以时间复杂度为O(n³）O(n³）。这个复杂度太吓人了，写出来面试官可能就会溜了。

空间复杂度：O(1）O(1），常数个变量。

（代码略）

2 动态规划

重点是能够列举初始状态：

dp[i][i]=1; //单个字符是回文串

dp[i][i+1]=1 如果 s[i]=s[i+1]; //连续两个相同字符是回文串

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;//回文串起始位置
        int max=1;//回文串最大长度
        vector<vector<int>>  dp(len,vector<int>(len));//定义二维动态数组
        for(int i=0;i<len;i++)//初始化状态
        {
            dp[i][i]=1;
            if(i<len-1&&s[i]==s[i+1])
            {
                dp[i][i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
        {
            for(int i=0;i+l-1<len;i++)
            {
                int j=l+i-1;//终止字符位置
                if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移
                {
                    dp[i][j]=1;
                    start=i;
                    max=l;
                }
            }
        }
        return s.substr(start,max);//获取最长回文子串
    }
};

3 中心扩展法

回文中心的两侧互为镜像。因此，回文可以从他的中心展开，并且只有 2n-1 个这样的中心（一个元素为中心的情况有 n 个，两个元素为中心的情况有 n-1 个）

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;//记录回文子串起始位置
        int end=0;//记录回文子串终止位置
        int mlen=0;//记录最大回文子串的长度
        for(int i=0;i<len;i++)
        {
            int len1=expendaroundcenter(s,i,i);//一个元素为中心
            int len2=expendaroundcenter(s,i,i+1);//两个元素为中心
            mlen=max(max(len1,len2),mlen);
            if(mlen>end-start+1)
            {
                start=i-(mlen-1)/2;
                end=i+mlen/2;
            }
        }
        return s.substr(start,mlen);
        //该函数的意思是获取从start开始长度为mlen长度的字符串
    }
private:
    int expendaroundcenter(string s,int left,int right)
    //计算以left和right为中心的回文串长度
    {
        int L=left;
        int R=right;
        while(L>=0 && R<s.length() && s[R]==s[L])
        {
            L--;
            R++;
        }
        return R-L-1;
    }
};

4 Manacher（马拉车） 算法

Manacher 算法本质上还是中心扩散法，只不过它使用了类似 KMP 算法的技巧，充分挖掘了已经进行回文判定的子串的特点，在遍历的过程中，记录了已经遍历过的子串的信息，也是典型的以空间换时间思想的体现。

该算法的推理过程比较复杂，下次可以再写一篇文章来详细介绍。这里只是甩出代码。

class Solution {
private:
    int centerSpread(string s, int center) {
        int len = s.size();
        int i = center - 1;
        int j = center + 1;
        int step = 0;
        while (i >= 0 && j < len && s[i] == s[j]) {
            i--;
            j++;
            step++;
        }
        return step;
    }
public:
    string longestPalindrome(string s) {
        // 特判
        int size = s.size();
        if (size < 2) {
            return s;
        }
        // 得到预处理字符串
        string str = "#";
        for (int i = 0; i < s.size(); ++i) {
            str += s[i];
            str += "#";
        }
        int sSize = 2 * size + 1;
        int maxLen = 1;

        int start = 0;
        for (int i = 0; i < sSize; i++) {
            int curLen = centerSpread(str, i);
            if (curLen > maxLen) {
                maxLen = curLen;
                start = (i - maxLen) / 2;
            }
        }
        return s.substr(start, maxLen);
    }
};

03

2020爱你爱你

思绪从20200202转到回文数再到回文序列判断，已然不能再深入下去了，否则或许会迎来女朋友的公开审问。

今年开年实在是有太多让人感慨无奈又忧心忡忡的事情了，好在至少还有今天这么个日子。虽然说不上多重要，但是能够听到最爱的人看似随意而又深情满满的告白，不也是件乐事嘛。

当然了，单身的朋友坐等国家分配就好。然后等下一个千年一遇的日子哈。

最后希望疫情早日结束！

扫个关注，有空来看看直男程序员的业余分享。

推荐阅读（点击下方链接即可阅读）