1 回文識(shí)別基礎(chǔ)
回文通俗地將就是把一個(gè)句子或者字符串正過(guò)來(lái)反過(guò)來(lái)讀都是一樣的.
比如123321就是一個(gè)回文.
識(shí)別一個(gè)回文字符串思路也很簡(jiǎn)單:定義兩個(gè)指針?lè)謩e指向字符串的頭尾,若果兩個(gè)指針指向的字符相等,那么繼續(xù)逐漸向中間收縮,否則退出循環(huán).
知道指針相遇.如果指針相遇之前就已經(jīng)停止那么就不是回文
2 回文串的加強(qiáng)版
原題
3 回文數(shù)字
原題
解：
時(shí)間O（n）空間O（1）其中x/t%10表示每次循環(huán)數(shù)字的首位，比如1234的首位計(jì)算為：1234除以1000等等于1，在對(duì)10 取余，結(jié)果為1。下一次循環(huán)首位為1234/100%10結(jié)果為2，一次類推，而最末尾則為直接對(duì)10 取余，末尾向左以為則為1234/10再對(duì)10 取余，基本原理是這樣。
4 最長(zhǎng)回文字串
- 暴力求解法
窮舉思路：取出所有的子串，判斷它是否回文，并返回最長(zhǎng)的子串
- 中心擴(kuò)展法
思路從字符串中的某個(gè)元素開(kāi)始（逐個(gè)判斷），向兩邊擴(kuò)展，判斷是否回文并記錄，將取得最長(zhǎng)子回文返回即可。
- 動(dòng)態(tài)規(guī)劃法簡(jiǎn)介
- Manacher算法簡(jiǎn)介
5. leetCode 234：Palindrome Linked List（回文鏈表）
按照以往的經(jīng)驗(yàn)，關(guān)于回文問(wèn)題不外乎兩種：中心擴(kuò)展法，兩端收縮法
然而單鏈表無(wú)法倒序遍歷，兩種方法都沒(méi)有什么卵用。
仔細(xì)觀察一個(gè)回文比如：1 2 3 4 5 5 4 3 2 1發(fā)現(xiàn)有什么規(guī)律？假象把這個(gè)鏈表對(duì)折，那么相應(yīng)的每個(gè)對(duì)稱的數(shù)字都對(duì)的上（這不廢話~），其實(shí)這個(gè)對(duì)折過(guò)程就是先把鏈表的一半（前一半后一半都行）反轉(zhuǎn)然后在匹配的過(guò)程，如果是回文當(dāng)然能一一對(duì)應(yīng)上啦
實(shí)現(xiàn)代碼：
有時(shí)候面試官會(huì)要求不要破壞鏈表結(jié)構(gòu)
那么可以把鏈表的一半用棧保存起來(lái)，然后再比較。
或者還是用之前的方法，翻轉(zhuǎn)之后再給翻轉(zhuǎn)回去~~
