本文首發(fā)于公眾號(hào)「五分鐘學(xué)算法」，是圖解 LeetCode 系列文章之一。

個(gè)人網(wǎng)站：https://www.cxyxiaowu.com

題目來源于 LeetCode 第 9 號(hào)問題：回文數(shù)。題目難度為 Easy，目前通過率為 56.0%。

題目描述

判斷一個(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)為字符串來解決這個(gè)問題嗎？

題目解析

解法一：普通解法

最好理解的一種解法就是先將 整數(shù)轉(zhuǎn)為字符串 ，然后將字符串分割為數(shù)組，只需要循環(huán)數(shù)組的一半長(zhǎng)度進(jìn)行判斷對(duì)應(yīng)元素是否相等即可。

動(dòng)畫描述

代碼實(shí)現(xiàn)

///簡(jiǎn)單粗暴，看看就行
class?Solution?{
????public?boolean?isPalindrome(int?x)?{
????????String?reversedStr?=?(new?StringBuilder(x?+?"")).reverse().toString();
????????return?(x?+?"").equals(reversedStr);
????}
}


解法二：進(jìn)階解法---數(shù)學(xué)解法

通過取整和取余操作獲取整數(shù)中對(duì)應(yīng)的數(shù)字進(jìn)行比較。

舉個(gè)例子：1221 這個(gè)數(shù)字。

• 通過計(jì)算 1221 / 1000， 得首位1

• 通過計(jì)算 1221 % 10， 可得末位 1

• 進(jìn)行比較

• 再將 22 取出來繼續(xù)比較

動(dòng)畫描述

代碼實(shí)現(xiàn)

class?Solution?{
????public?boolean?isPalindrome(int?x)?{
????????//邊界判斷
????????if?(x?<?0)?return?false;
????????int?div?=?1;
????????//
????????while?(x?/?div?>=?10)?div?*=?10;
????????while?(x?>?0)?{
????????????int?left?=?x?/?div;
????????????int?right?=?x?%?10;
????????????if?(left?!=?right)?return?false;
????????????x?=?(x?%?div)?/?10;
????????????div?/=?100;
????????}
????????return?true;
????}
}


解法三：進(jìn)階解法---巧妙解法

直觀上來看待回文數(shù)的話，就感覺像是將數(shù)字進(jìn)行對(duì)折后看能否一一對(duì)應(yīng)。

所以這個(gè)解法的操作就是 取出后半段數(shù)字進(jìn)行翻轉(zhuǎn)。

這里需要注意的一個(gè)點(diǎn)就是由于回文數(shù)的位數(shù)可奇可偶，所以當(dāng)它的長(zhǎng)度是偶數(shù)時(shí)，它對(duì)折過來應(yīng)該是相等的；當(dāng)它的長(zhǎng)度是奇數(shù)時(shí)，那么它對(duì)折過來后，有一個(gè)的長(zhǎng)度需要去掉一位數(shù)（除以 10 并取整）。

具體做法如下：

• 每次進(jìn)行取余操作 （ %10），取出最低的數(shù)字：y = x % 10

• 將最低的數(shù)字加到取出數(shù)的末尾：revertNum = revertNum * 10 + y

• 每取一個(gè)最低位數(shù)字，x 都要自除以 10

• 判斷 x 是不是小于 revertNum ，當(dāng)它小于的時(shí)候，說明數(shù)字已經(jīng)對(duì)半或者過半了

• 最后，判斷奇偶數(shù)情況：如果是偶數(shù)的話，revertNum 和 x 相等；如果是奇數(shù)的話，最中間的數(shù)字就在revertNum 的最低位上，將它除以 10 以后應(yīng)該和 x 相等。

動(dòng)畫描述

代碼實(shí)現(xiàn)

class?Solution?{
????public?boolean?isPalindrome(int?x)?{
????????//思考：這里大家可以思考一下，為什么末尾為?0?就可以直接返回?false
????????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;
????}
}