今天是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转到回文数再到回文序列判断，已然不能再深入下去了，否则或许会迎来女朋友的公开审问。
今年开年实在是有太多让人感慨无奈又忧心忡忡的事情了，好在至少还有今天这么个日子。虽然说不上多重要，但是能够听到最爱的人看似随意而又深情满满的告白，不也是件乐事嘛。
当然了，单身的朋友坐等国家分配就好。然后等下一个千年一遇的日子哈。
最后希望疫情早日结束！
