leetcode之回文系列

1 回文識别基礎

回文通俗地将就是把一個句子或者字元串正過來反過來讀都是一樣的.

比如123321就是一個回文.

識别一個回文字元串思路也很簡單:定義兩個指針分别指向字元串的頭尾,若果兩個指針指向的字元相等,那麼繼續逐漸向中間收縮,否則退出循環.

知道指針相遇.如果指針相遇之前就已經停止那麼就不是回文

2 回文串的加強版

原題

3 回文數字

原題

解：

時間O（n）空間O（1）其中x/t%10表示每次循環數字的首位，比如1234的首位計算為：1234除以1000等等于1，在對10 取餘，結果為1。下一次循環首位為1234/100%10結果為2，一次類推，而最末尾則為直接對10 取餘，末尾向左以為則為1234/10再對10 取餘，基本原理是這樣。

4 最長回文字串

• 暴力求解法

窮舉思路：取出所有的子串，判斷它是否回文，并傳回最長的子串

• 中心擴充法

  思路從字元串中的某個元素開始（逐個判斷），向兩邊擴充，判斷是否回文并記錄，将取得最長子回文傳回即可。


• 動态規劃法簡介

• Manacher算法簡介

5. leetCode 234：Palindrome Linked List（回文連結清單）

按照以往的經驗，關于回文問題不外乎兩種：中心擴充法，兩端收縮法

然而單連結清單無法倒序周遊，兩種方法都沒有什麼卵用。

仔細觀察一個回文比如：1 2 3 4 5 5 4 3 2 1發現有什麼規律？假象把這個連結清單對折，那麼相應的每個對稱的數字都對的上（這不廢話~），其實這個對折過程就是先把連結清單的一半（前一半後一半都行）反轉然後在比對的過程，如果是回文當然能一一對應上啦

實作代碼：

**有時候面試官會要求不要破壞連結清單結構

那麼可以把連結清單的一半用棧儲存起來，然後再比較。

或者還是用之前的方法，翻轉之後再給翻轉回去~~**