[[313923]]

  今天是 2020 年 02 月 02 日，被稱為「千年一遇的對稱日」，20200202 正反都一樣，反正都是「愛你愛你」的意思。不少新人都選擇今天作為領證的日子，不過因為肺炎的緣故，有些地方已經取消了今日的預約。 

但是我們今天不聊這日子的寓意，我們來聊聊技術相關的話題。

20200202 這種正反都一樣的串，在算法上稱為「回文」，又因為不同的結構，被分為回文數、回文字符串、回文鏈表等。

這分別又延伸出好幾個 Leetcode 算法題，今天我們在這個別人領證的日子，復習一下「回文」相關的算法題。

一. 驗證回文字符串

今天的日期，用字符串表示是 "20200202"，這就是一個回文字符串。

那么想要寫個方法，驗證其是否是一個回文字符串，拍腦袋想最簡單的方法就是將字符串翻轉后比對。 

1. boolean isPalindrome(String s) { 
2.   return new StringBuilder(s).reverse().equals(s) 
3. } 

但是多數情況下是不允許我們直接使用 Api，那除此之外，比較常用的方法就是用 2 個指針，從字符串的前后兩個方向，向內夾。

boolean isPalindrome(String s) { 
    int i = 0; 
  int j = s.length() - 1; 
  while (i < j ) { 
    if (Character.toLowerCase(s.charAt(i) != Character.toLowerCase(s.charAt(j))) { 
        return false; 
    } 
    i++; 
    j--; 
  } 
  return true; 
} 

邏輯很簡單，一個循環兩個指針，就搞定了。

但是因為這是一個字符串，很輕易的可以拿到字符串的長度，所以一般算法題會加上一些額外的條件，增加難度。

例如 Leetcode 上的「125. 驗證回文串」，給定的字符串是包含空格的。 

 這種情況呢，只需要把之前的解法改改就好了，兩個指針在移動的時候，如果遇上 1 個空格就多走 1 步即可。 

public boolean isPalindrome(String s) { 
  int i = 0, j = s.length() - 1; 
  while(i < j){ 
    while(i < j && !Character.isLetterOrDigit(s.charAt(i))) 
      i++; 
    while(i < j && !Character.isLetterOrDigit(s.charAt(j))) 
      j--; 
    if(Character.toLowerCase(s.charAt(i)) != 
       Character.toLowerCase(s.charAt(j))) 
      return false; 
    i++; j--; 
  } 
  return true; 
} 

通過 isLetterOrDigit() 可以直接判斷當前字符是不是只屬于字母和數字。

關于字符串的回文算法，除了 125 之外，leetcode 第 680 題也屬于回文字符串，有興趣可以去看看。

二. 驗證回文數

如果回文字符串中只包含數字，那么它也可以是一個回文數，例如 20200202。

想要驗證回文數，比較簡單的方法就是將其轉換字符串，然后用驗證字符回文串的算法模式去套用。但是這并沒有用到數字的特性。

既然是數字，我們可以通過除法 / 和取余 % 的方式，將這個數字取出后半段進行翻轉，然后比對兩個數字的是否相等。

public boolean 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; 
} 

 簡單解釋一下：

1. 首先做一些簡單的驗證。如果一個大于 0 的非零數，個位為 0 ，那么它注定不是一個回文數。因為對應的回文位置是這個數字的最高位，而最高位不會為 0。

2. 通過循環，每次循環中，按位生成翻轉后的數字，并將原數字最低位打掉。

3. 如果跳出循環，說明后半部分已經翻轉完畢，那么分兩個情況考慮，數字長度是奇數還是偶數。然后判斷原數字 x 和后半部分翻轉的數字 reversedNumber 是否相同。

另外提一句，這道題是 Leetcode 上的「9. 回文數」題。

三. 驗證回文鏈表

回文串和回文數都說了，接下來看看回文鏈表。

單鏈表這種特殊的結構，想要確定個長度也需要 O(n) 的復雜度，而且沒有前驅指針，雙指針前后夾的辦法是沒法用了。

當然我們可以將它轉換為我們熟悉的回文數或者回文串進行計算，但是這同樣沒有用到鏈表的特性。

在驗證回文鏈表的場景下，我們可以通過快慢指針的方式找到鏈表的中間節點，然后再將原鏈表的一半反轉，之后開始比對。

為了效率，可以把這兩個步驟糅合在 1 個循環中。

public boolean isPalindrome(ListNode head) { 
  if(head == null || head.next == null) { 
    return true; 
  } 
  ListNode slow = head, fast = head; 
  ListNode pre = head, prepre = null; 
  while(fast != null && fast.next != null) { 
    pre = slow; 
    slow = slow.next; 
    fast = fast.next.next; 
    pre.next = prepre; 
    prepre = pre; 
  } 
  // 如果 fast 不為 null，說明是奇數，需要再進一位 
  if(fast != null) { 
    slow = slow.next; 
  } 
  // 此時 pre 為反轉原鏈表前半部分的子鏈表 
  // slow 為原鏈表的中間節點 
  while(pre != null && slow != null) { 
    if(pre.val != slow.val) { 
      return false; 
    } 
    pre = pre.next; 
    slow = slow.next; 
  } 
  return true; 
} 

 第一遍循環之后，slow 節點指向了鏈表的中間位置，而 pre 則是翻轉了原鏈表的前半部分的子鏈表。

再通過一個 while 循環，將它們逐個比對，就可以得到我們要的結果。

另外提一句，這道題是 Leetcode 上的「234. 回文鏈表」題。

四. 小結時刻

那今天就到這里，20200202 這個日子里，我們復習了一下回文相關的算法題，不知道分別從字符串、數字、鏈表三個方向橫向的看回文類的題之后，你能總結出什么規律?歡迎在留言區討論。

因為疫情的緣故，不少朋友明日起，就要切換到在家遠程辦公狀態了，祝各位順利。