題目描述
判斷一個整數是否是回文數，回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數，
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 ， 從右向左讀, 為 121- ，因此它不是一個回文數，
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 ，因此它不是一個回文數，
進階:
你能不將整數轉為字串來解決這個問題嗎？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-number
難度:簡單
題解
我的題解
我的思路:不將數字轉字串,所以判斷是否回文需要將數字進行反轉,判斷反轉后的數字與原數字是否相等.可以先將負數排除,因為負數反轉后負號在后導致必定不是回文(這里有個問題,正數其實也可以帶符號的比如:+121,但是此題默認的應該是正數都不帶符號).
public boolean isPalindrome(int x) {
if (x<0){
return false;
}
int y = x;
// 定義為long型是為了防止反轉后溢位
long z = 0;
do {
z = z*10 +y%10;
y=y/10;
} while (y>0);
return x == z;
}
官方題解
思路:為了避免數字反轉可能導致的溢位問題，為什么不考慮只反轉 int 數字的一半？畢竟，如果該數字是回文，其后半部分反轉后應該與原始數字的前半部分相同，
例如，輸入 1221，我們可以將數字 “1221” 的后半部分從 “21” 反轉為 “12”，并將其與前半部分 “12” 進行比較，因為二者相同，我們得知數字 1221 是回文，
演算法
首先，我們應該處理一些臨界情況，所有負數都不可能是回文，例如：-123 不是回文，因為 - 不等于 3，所以我們可以對所有負數回傳 false，
現在，讓我們來考慮如何反轉后半部分的數字，
對于數字 1221，如果執行 1221 % 10，我們將得到最后一位數字 1，要得到倒數第二位數字，我們可以先通過除以 10 把最后一位數字從 1221 中移除，1221 / 10 = 122，再求出上一步結果除以 10 的余數，122 % 10 = 2，就可以得到倒數第二位數字，如果我們把最后一位數字乘以 10，再加上倒數第二位數字，1 * 10 + 2 = 12，就得到了我們想要的反轉后的數字，如果繼續這個程序，我們將得到更多位數的反轉數字，
現在的問題是，我們如何知道反轉數字的位數已經達到原始數字位數的一半？
我們將原始數字除以 10，然后給反轉后的數字乘上 10，所以，當原始數字小于反轉后的數字時，就意味著我們已經處理了一半位數的數字，
public boolean isPalindrome(int x) {
// 特殊情況：
// 如上所述，當 x < 0 時，x 不是回文數，
// 同樣地，如果數字的最后一位是 0，為了使該數字為回文，
// 則其第一位數字也應該是 0
// 只有 0 滿足這一屬性
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// 當數字長度為奇數時，我們可以通過 revertedNumber/10 去除處于中位的數字，
// 例如，當輸入為 12321 時，在 while 回圈的末尾我們可以得到 x = 12，revertedNumber = 123，
// 由于處于中位的數字不影響回文（它總是與自己相等），所以我們可以簡單地將其去除，
return x == revertedNumber || x == revertedNumber/10;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139451.html
標籤：其他