優質博文：IT-BLOG-CN

一、題目

給你一個整數x，如果x是一個回文整數，返回true；否則返回false。回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。例如，121是回文，而123不是。

示例 1：
輸入：x = 121
輸出：true

示例 2：
輸入：x = -121
輸出：false
解釋：從左向右讀, 為-121。 從右向左讀, 為121-。因此它不是一個回文數。

示例 3：
輸入：x = 10
輸出：false
解釋：從右向左讀, 為01。因此它不是一個回文數。

-2^31 <= x <= 2^31 - 1

進階： 你能不將整數轉為字符串來解決這個問題嗎？

二、代碼

思路： 第一個想法是將數字轉換為字符串，并檢查字符串是否為回文。但是，這需要額外的非常量空間來創建問題描述中所不允許的字符串。第二個想法是將數字本身反轉，然后將反轉后的數字與原始數字進行比較，如果它們是相同的，那么這個數字就是回文。 但是，如果反轉后的數字大于int.MAX，我們將遇到整數溢出問題。

按照第二個想法，為了避免數字反轉可能導致的溢出問題，為什么不考慮只反轉int數字的一半？畢竟，如果該數字是回文，其后半部分反轉后應該與原始數字的前半部分相同。例如，輸入1221，我們可以將數字1221的后半部分從21反轉為12，并將其與前半部分12進行比較，因為二者相同，我們得知數字1221是回文。

首先，我們應該處理一些臨界情況。所有負數都不可能是回文，例如：-123不是回文，因為-不等于3。所以我們可以對所有負數返回false。除了0以外，所有個位是0的數字不可能是回文，因為最高位不等于0。所以我們可以對所有大于0且個位是0的數字返回false。

現在，讓我們來考慮如何反轉后半部分的數字。對于數字1221，如果執行1221 % 10，我們將得到最后一位數字1，要得到倒數第二位數字，我們可以先通過除以10把最后一位數字從1221中移除，1221 / 10 = 122，再求出上一步結果除以10的余數，122 % 10 = 2，就可以得到倒數第二位數字。如果我們把最后一位數字乘以10，再加上倒數第二位數字，1 * 10 + 2 = 12，就得到了我們想要的反轉后的數字。如果繼續這個過程，我們將得到更多位數的反轉數字。

現在的問題是，我們如何知道反轉數字的位數已經達到原始數字位數的一半？由于整個過程我們不斷將原始數字除以10，然后給反轉后的數字乘上10，所以，當原始數字小于或等于反轉后的數字時，就意味著我們已經處理了

class Solution {public boolean isPalindrome(int x) {// 思路：因為不能使用字符串和反轉整個整數，因為反轉后數int溢出，所以只能創建一個變量保存一般的數據，利于/和%// 第一步：先排除特殊的場景，但是0是符合的if (x < 0 ||  (x > 0 && x % 10 == 0)) {return false;}// 第二步：創建一個變量保存 % 后的數據，并對當前x進行/操作int temp = 0;while (x > temp) {// 退出條件：x不斷減小， temp不斷變大，最終就會退出，先讓原有的數進一為給尾數留個坑位temp = temp * 10 + x % 10;x = x / 10;}// 第三步，判斷x與temp是否相同，特殊場景判斷：當x為奇數時 temp 會比 x多以為，比如 12321 進行上面的拆分后 x = 12 temp = 123，所以需要對 temp進行 /return temp == x || temp /10  == x;}
}

時間復雜度： O(log?n)對于每次迭代，我們會將輸入除以10，因此時間復雜度為O(log?n)。
空間復雜度： O(1)我們只需要常數空間存放若干變量。

思路
標簽：數學
如果是負數則一定不是回文數，直接返回false
如果是正數，則將其倒序數值計算出來，然后比較和原數值是否相等
如果是回文數則相等返回true，如果不是則不相等false
比如123的倒序321，不相等；121的倒序121，相等

class Solution {public boolean isPalindrome(int x) {if(x < 0)return false;int cur = 0;int num = x;while(num != 0) {cur = cur * 10 + num % 10;num /= 10;}return cur == x;}
}

普通解法： 最好理解的一種解法就是先將 整數轉為字符串 ，然后將字符串分割為數組，只需要循環數組的一半長度進行判斷對應元素是否相等即可。

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

進階解法—數學解法
通過取整和取余操作獲取整數中對應的數字進行比較。

舉個例子：1221 這個數字。

通過計算 1221 / 1000， 得首位1
通過計算 1221 % 10， 可得末位 1
進行比較
再將 22 取出來繼續比較

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

進階解法—巧妙解法
直觀上來看待回文數的話，就感覺像是將數字進行對折后看能否一一對應。

所以這個解法的操作就是 取出后半段數字進行翻轉。

這里需要注意的一個點就是由于回文數的位數可奇可偶，所以當它的長度是偶數時，它對折過來應該是相等的；當它的長度是奇數時，那么它對折過來后，有一個的長度需要去掉一位數（除以 10 并取整）。

具體做法如下：

每次進行取余操作 （ %10），取出最低的數字：y = x % 10
將最低的數字加到取出數的末尾：revertNum = revertNum * 10 + y
每取一個最低位數字，x 都要自除以 10
判斷 x 是不是小于 revertNum ，當它小于的時候，說明數字已經對半或者過半了
最后，判斷奇偶數情況：如果是偶數的話，revertNum 和 x 相等；如果是奇數的話，最中間的數字就在revertNum 的最低位上，將它除以 10 以后應該和 x 相等。

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