每日一道 LeetCode (3):回文數(shù)

題目：回文數(shù)

題目來源：https://leetcode-cn.com/problems/palindrome-number/

判斷一個整數(shù)是否是回文數(shù)。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。

示例 1:

輸入: 121
輸出: true

示例?2:

輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。從右向左讀, 為 121- 。因此它不是一個回文數(shù)。

示例 3:

輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個回文數(shù)。

進階:

你能不將整數(shù)轉(zhuǎn)為字符串來解決這個問題嗎？

解題思路

在題目給出的示例中可以直觀的看到，負(fù)數(shù)由于負(fù)號的關(guān)系，肯定不是回文數(shù)的，那么我們第一件事情就是判斷輸入的數(shù)字不是負(fù)數(shù)。

然后根據(jù)數(shù)字的特性，還可以知道個位數(shù)字是 0 的整數(shù)，肯定也不會是回文數(shù)，個位是 0 的數(shù)字如果是回文數(shù)的話，那么首位一定也要是 0 ，這種數(shù)字除了 0 以外其余的顯然都不會是一個回文數(shù)。

這樣，我們的第一個極限值判斷就有了，所有的負(fù)數(shù)返回 false ，所有個位是 0 且不為 0 的整數(shù)也要返回 false 。

接下來，不知道你們會不會想到上一篇文章中的整數(shù)反轉(zhuǎn)，將整個輸入的數(shù)字反轉(zhuǎn)后，得到的結(jié)果如果和輸入數(shù)字一樣，那么這個肯定是回文數(shù)，不過這么搞的話，我們還需要判斷反轉(zhuǎn)后的數(shù)字是否溢出，有點麻煩。

那么比較好的方案是啥，當(dāng)然是直接反轉(zhuǎn)后面一半的數(shù)字，與前面一半的數(shù)字做比較，如果一樣的話，返回 true ，不一樣的返回 false 。

數(shù)字反轉(zhuǎn)的操作很簡單，輸入的數(shù)字 x 直接循環(huán)的取模就好，然后我們再對輸入的數(shù)字在循環(huán)的過程中除以 10 。

問題是我們?nèi)绾闻袛喾崔D(zhuǎn)的位數(shù)已經(jīng)達到了一半？

這個問題可以這么考慮，如果是偶數(shù)回文數(shù)的情況，X 和 Y 相等的時候，反轉(zhuǎn)的位數(shù)就已經(jīng)到一半了，如果是奇數(shù)回文數(shù)的情況，那么 X < Y 的時候，反轉(zhuǎn)的位數(shù)也到一半了，然后我們對去除 Y 的最后一位，和 X 進行比較，如果相等，那么這個數(shù)字就是奇數(shù)位的回文數(shù)。

寫代碼

經(jīng)過上面的分析，代碼已經(jīng)簡單到顯而易見了：

public boolean isPalindrome(int x) {
// 先做極限情況判斷
if (x < 0 || (x % 10 == 0 && x != 0)) return false;

int revertedNumber = 0;

// 一直循環(huán)到 revertedNumber 大于或者等于 x
while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }

return revertedNumber == x || x == revertedNumber / 10;
}

到這里，不知道有沒有同學(xué)會想問，題目上如果沒有加那句「不將整數(shù)轉(zhuǎn)為字符串」題干，可以怎么解答。

在 Java 中，如果沒有這個限制，那這個代碼不要簡單太多， Java 中的 StringBuilder 和 StringBuffer 都直接提供了 reverse() 方法：

public boolean isPalindrome_1(int x) {
// 先做極限情況判斷
if (x < 0 || (x % 10 == 0 && x != 0)) return false;

    StringBuilder stringBuilder = new StringBuilder(String.valueOf(x));
return stringBuilder.toString().equals(stringBuilder.reverse().toString());
}

?

小結(jié)一下吧：如果以后遇到「整數(shù)反轉(zhuǎn)」的問題，基本思路就是循環(huán)取模，然后再乘以 10 加起來，需要注意的就是 int 類型有長度限制，注意超限和極限值判斷。今天的回文數(shù)可以看做一種稍微特殊的「整數(shù)反轉(zhuǎn)」問題。

?