[[313923]]

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

但是我們今天不聊這日子的寓意，我們來聊聊技術(shù)相關(guān)的話題。

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

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

一. 驗證回文字符串

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

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

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

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

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

邏輯很簡單，一個循環(huán)兩個指針，就搞定了。

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

例如 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() 可以直接判斷當前字符是不是只屬于字母和數(shù)字。

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

二. 驗證回文數(shù)

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

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

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

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 的非零數(shù)，個位為 0 ，那么它注定不是一個回文數(shù)。因為對應的回文位置是這個數(shù)字的最高位，而最高位不會為 0。

2. 通過循環(huán)，每次循環(huán)中，按位生成翻轉(zhuǎn)后的數(shù)字，并將原數(shù)字最低位打掉。

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

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

三. 驗證回文鏈表

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

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

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

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

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

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，說明是奇數(shù)，需要再進一位 
  if(fast != null) { 
    slow = slow.next; 
  } 
  // 此時 pre 為反轉(zhuǎn)原鏈表前半部分的子鏈表 
  // slow 為原鏈表的中間節(jié)點 
  while(pre != null && slow != null) { 
    if(pre.val != slow.val) { 
      return false; 
    } 
    pre = pre.next; 
    slow = slow.next; 
  } 
  return true; 
} 

 第一遍循環(huán)之后，slow 節(jié)點指向了鏈表的中間位置，而 pre 則是翻轉(zhuǎn)了原鏈表的前半部分的子鏈表。

再通過一個 while 循環(huán)，將它們逐個比對，就可以得到我們要的結(jié)果。

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

四. 小結(jié)時刻

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

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