題目匯總：

9. 回文數(shù)（整型轉字符串）

266. 回文排列

5. 最長回文子串（動態(tài)規(guī)劃）

680. 驗證回文字符串 Ⅱ（左右指針）

一 數(shù)字類型回文串

1、9. 回文數(shù)

1）問題描述

整型回文串判斷

2）思路：

借助帶余除法從個位提取整型數(shù)據(jù)各位數(shù)字，再反轉數(shù)字整合在一起，最后和輸入數(shù)據(jù)進行比對。

具體代碼

（類似技巧題目：leetcode 7 整數(shù)反轉，需要考慮反轉后溢出情況）

二、字符串回文排列題

1、266. 回文排列

1）問題描述

字符串回文排列

2）思路：

建立哈希映射map_array[26]，把字符串的各個字符映射到數(shù)組特定下標，數(shù)組中各下標對應的值為該下標（字符）出現(xiàn)的次數(shù)。根據(jù)回文串的特點，只要滿足數(shù)組中各元素的值最多只有一個奇數(shù)即可。

2、5. 最長回文子串

1）問題描述

求字符串最長回文子串

約束

2）思路：

（1）動態(tài)規(guī)劃

動態(tài)規(guī)劃分析

核心代碼

該算法時間復雜度為，狀態(tài)總數(shù)為，每一狀態(tài)需要轉移的時間為.

空間復雜度。

（2）中新擴展法

遍歷字符串，假定遍歷的元素是回文中心，并向兩端進行擴展。

核心代碼（C編寫）

中心擴展法

該算法時間復雜度為，每個回文中心最多向外擴展次。

空間復雜度為

（3）Manacher算法（馬拉車算法）

核心思想：

在中心擴散法基礎上進行優(yōu)化，充分利用每次遍歷的結果，預測未遍歷元素若作為回文中心，可能達到的長度。這樣的好處是充分利用已經(jīng)遍歷過的信息，把時間復雜度降為線性級別。（像類似的還有KMP算法）

假設字符串s構成回文串，s[center]為串s的回文中心，利用字符串元素關于回文中心對稱性特點，來判斷s[i]右側元素若作為回文中心，可能達到的長度。

理解：https://www.cxyxiaowu.com/2665.html

馬拉車算法大致思路

部分代碼

字符串預處理

馬拉車算法核心

返回結果

3、680. 驗證回文字符串 Ⅱ

1）問題描述

驗證回文串字符問題描述

2）思路

從兩側往中間收縮判斷，遇到不符合情況，枚舉可能性。

3）代碼實現(xiàn)

回文串字符代碼實現(xiàn)