20200202 這個(gè)千年一遇的對(duì)稱(chēng)日，是時(shí)候?qū)ⅰ富匚乃惴ā挂痪W(wǎng)打盡！
今天是 2020 年 02 月 02 日，被稱(chēng)為「千年一遇的對(duì)稱(chēng)日」，20200202 正反都一樣，反正都是「愛(ài)你愛(ài)你」的意思。不少新人都選擇今天作為領(lǐng)證的日子，不過(guò)因?yàn)榉窝椎木壒剩行┑胤揭呀?jīng)取消了今日的預(yù)約。
但是我們今天不聊這日子的寓意，我們來(lái)聊聊技術(shù)相關(guān)的話(huà)題。
20200202 這種正反都一樣的串，在算法上稱(chēng)為「回文」，又因?yàn)椴煌慕Y(jié)構(gòu)，被分為回文數(shù)、回文字符串、回文鏈表等。
這分別又延伸出好幾個(gè) Leetcode 算法題，今天我們?cè)谶@個(gè)別人領(lǐng)證的日子，復(fù)習(xí)一下「回文」相關(guān)的算法題。
一. 驗(yàn)證回文字符串
今天的日期，用字符串表示是 "20200202"，這就是一個(gè)回文字符串。
那么想要寫(xiě)個(gè)方法，驗(yàn)證其是否是一個(gè)回文字符串，拍腦袋想最簡(jiǎn)單的方法就是將字符串翻轉(zhuǎn)后比對(duì)。
- boolean isPalindrome(String s) {
- return new StringBuilder(s).reverse().equals(s)
- }
但是多數(shù)情況下是不允許我們直接使用 Api，那除此之外，比較常用的方法就是用 2 個(gè)指針，從字符串的前后兩個(gè)方向，向內(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;
- }
邏輯很簡(jiǎn)單，一個(gè)循環(huán)兩個(gè)指針，就搞定了。
但是因?yàn)檫@是一個(gè)字符串，很輕易的可以拿到字符串的長(zhǎng)度，所以一般算法題會(huì)加上一些額外的條件，增加難度。
例如 Leetcode 上的「125. 驗(yàn)證回文串」，給定的字符串是包含空格的。
這種情況呢，只需要把之前的解法改改就好了，兩個(gè)指針在移動(dòng)的時(shí)候，如果遇上 1 個(gè)空格就多走 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;
- }
通過(guò) isLetterOrDigit() 可以直接判斷當(dāng)前字符是不是只屬于字母和數(shù)字。
關(guān)于字符串的回文算法，除了 125 之外，leetcode 第 680 題也屬于回文字符串，有興趣可以去看看。
二. 驗(yàn)證回文數(shù)
如果回文字符串中只包含數(shù)字，那么它也可以是一個(gè)回文數(shù)，例如 20200202。
想要驗(yàn)證回文數(shù)，比較簡(jiǎn)單的方法就是將其轉(zhuǎn)換字符串，然后用驗(yàn)證字符回文串的算法模式去套用。但是這并沒(méi)有用到數(shù)字的特性。
既然是數(shù)字，我們可以通過(guò)除法 / 和取余 % 的方式，將這個(gè)數(shù)字取出后半段進(jìn)行翻轉(zhuǎn)，然后比對(duì)兩個(gè)數(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;
- }
簡(jiǎn)單解釋一下：
1. 首先做一些簡(jiǎn)單的驗(yàn)證。如果一個(gè)大于 0 的非零數(shù)，個(gè)位為 0 ，那么它注定不是一個(gè)回文數(shù)。因?yàn)閷?duì)應(yīng)的回文位置是這個(gè)數(shù)字的最高位，而最高位不會(huì)為 0。
2. 通過(guò)循環(huán)，每次循環(huán)中，按位生成翻轉(zhuǎn)后的數(shù)字，并將原數(shù)字最低位打掉。
3. 如果跳出循環(huán)，說(shuō)明后半部分已經(jīng)翻轉(zhuǎn)完畢，那么分兩個(gè)情況考慮，數(shù)字長(zhǎng)度是奇數(shù)還是偶數(shù)。然后判斷原數(shù)字 x 和后半部分翻轉(zhuǎn)的數(shù)字 reversedNumber 是否相同。
另外提一句，這道題是 Leetcode 上的「9. 回文數(shù)」題。
三. 驗(yàn)證回文鏈表
回文串和回文數(shù)都說(shuō)了，接下來(lái)看看回文鏈表。
單鏈表這種特殊的結(jié)構(gòu)，想要確定個(gè)長(zhǎng)度也需要 O(n) 的復(fù)雜度，而且沒(méi)有前驅(qū)指針，雙指針前后夾的辦法是沒(méi)法用了。
當(dāng)然我們可以將它轉(zhuǎn)換為我們熟悉的回文數(shù)或者回文串進(jìn)行計(jì)算，但是這同樣沒(méi)有用到鏈表的特性。
在驗(yàn)證回文鏈表的場(chǎng)景下，我們可以通過(guò)快慢指針的方式找到鏈表的中間節(jié)點(diǎn)，然后再將原鏈表的一半反轉(zhuǎn)，之后開(kāi)始比對(duì)。
為了效率，可以把這兩個(gè)步驟糅合在 1 個(gè)循環(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，說(shuō)明是奇數(shù)，需要再進(jìn)一位
- if(fast != null) {
- slow = slow.next;
- }
- // 此時(shí) pre 為反轉(zhuǎn)原鏈表前半部分的子鏈表
- // slow 為原鏈表的中間節(jié)點(diǎn)
- while(pre != null && slow != null) {
- if(pre.val != slow.val) {
- return false;
- }
- pre = pre.next;
- slow = slow.next;
- }
- return true;
- }
第一遍循環(huán)之后，slow 節(jié)點(diǎn)指向了鏈表的中間位置，而 pre 則是翻轉(zhuǎn)了原鏈表的前半部分的子鏈表。
再通過(guò)一個(gè) while 循環(huán)，將它們逐個(gè)比對(duì)，就可以得到我們要的結(jié)果。
另外提一句，這道題是 Leetcode 上的「234. 回文鏈表」題。
四. 小結(jié)時(shí)刻
那今天就到這里，20200202 這個(gè)日子里，我們復(fù)習(xí)了一下回文相關(guān)的算法題，不知道分別從字符串、數(shù)字、鏈表三個(gè)方向橫向的看回文類(lèi)的題之后，你能總結(jié)出什么規(guī)律?歡迎在留言區(qū)討論。
因?yàn)橐咔榈木壒剩簧倥笥衙魅掌穑鸵袚Q到在家遠(yuǎn)程辦公狀態(tài)了，祝各位順利。
