每日一道 LeetCode (3)：回文數(shù)
題目：回文數(shù)
題目來(lái)源：https://leetcode-cn.com/problems/palindrome-number/
判斷一個(gè)整數(shù)是否是回文數(shù)。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。
示例 1:
輸入: 121
輸出: true
示例?2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。從右向左讀, 為 121- 。因此它不是一個(gè)回文數(shù)。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個(gè)回文數(shù)。
進(jìn)階:
你能不將整數(shù)轉(zhuǎn)為字符串來(lái)解決這個(gè)問(wèn)題嗎？
解題思路
在題目給出的示例中可以直觀的看到，負(fù)數(shù)由于負(fù)號(hào)的關(guān)系，肯定不是回文數(shù)的，那么我們第一件事情就是判斷輸入的數(shù)字不是負(fù)數(shù)。
然后根據(jù)數(shù)字的特性，還可以知道個(gè)位數(shù)字是 0 的整數(shù)，肯定也不會(huì)是回文數(shù)，個(gè)位是 0 的數(shù)字如果是回文數(shù)的話，那么首位一定也要是 0 ，這種數(shù)字除了 0 以外其余的顯然都不會(huì)是一個(gè)回文數(shù)。
這樣，我們的第一個(gè)極限值判斷就有了，所有的負(fù)數(shù)返回 false ，所有個(gè)位是 0 且不為 0 的整數(shù)也要返回 false 。
接下來(lái)，不知道你們會(huì)不會(huì)想到上一篇文章中的整數(shù)反轉(zhuǎn)，將整個(gè)輸入的數(shù)字反轉(zhuǎn)后，得到的結(jié)果如果和輸入數(shù)字一樣，那么這個(gè)肯定是回文數(shù)，不過(guò)這么搞的話，我們還需要判斷反轉(zhuǎn)后的數(shù)字是否溢出，有點(diǎn)麻煩。
那么比較好的方案是啥，當(dāng)然是直接反轉(zhuǎn)后面一半的數(shù)字，與前面一半的數(shù)字做比較，如果一樣的話，返回 true ，不一樣的返回 false 。
數(shù)字反轉(zhuǎn)的操作很簡(jiǎn)單，輸入的數(shù)字 x 直接循環(huán)的取模就好，然后我們?cè)賹?duì)輸入的數(shù)字在循環(huán)的過(guò)程中除以 10 。
問(wèn)題是我們?nèi)绾闻袛喾崔D(zhuǎn)的位數(shù)已經(jīng)達(dá)到了一半？
這個(gè)問(wèn)題可以這么考慮，如果是偶數(shù)回文數(shù)的情況，X 和 Y 相等的時(shí)候，反轉(zhuǎn)的位數(shù)就已經(jīng)到一半了，如果是奇數(shù)回文數(shù)的情況，那么 X < Y 的時(shí)候，反轉(zhuǎn)的位數(shù)也到一半了，然后我們對(duì)去除 Y 的最后一位，和 X 進(jìn)行比較，如果相等，那么這個(gè)數(shù)字就是奇數(shù)位的回文數(shù)。
寫(xiě)代碼
經(jīng)過(guò)上面的分析，代碼已經(jīng)簡(jiǎn)單到顯而易見(jiàn)了：
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;
}
到這里，不知道有沒(méi)有同學(xué)會(huì)想問(wèn)，題目上如果沒(méi)有加那句「不將整數(shù)轉(zhuǎn)為字符串」題干，可以怎么解答。
在 Java 中，如果沒(méi)有這個(gè)限制，那這個(gè)代碼不要簡(jiǎn)單太多， 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)」的問(wèn)題，基本思路就是循環(huán)取模，然后再乘以 10 加起來(lái)，需要注意的就是 int 類(lèi)型有長(zhǎng)度限制，注意超限和極限值判斷。今天的回文數(shù)可以看做一種稍微特殊的「整數(shù)反轉(zhuǎn)」問(wèn)題。
?
