今天刷LeetCode匈仗，遇到一道簡單算法題，Palindrome Number逢慌，但解題過程比較有意思悠轩，借此文記錄下。
解析題目
問題描述： Determine whether an integer is a palindrome. Do this without extra space. 判斷一個int類型的數(shù)是否為回文數(shù)攻泼？ 不使用額外空間火架。
關(guān)于什么是回文數(shù)？給個定義：正反方向輸出的值相等的數(shù)稱為回文數(shù)忙菠。 沒理解到的何鸡，可以去網(wǎng)上搜下。
舉例：1牛欢、1221骡男、11211等是回文數(shù)；-1傍睹、0隔盛、12、123323等就不是回文數(shù)拾稳。
那什么是回文字符串呢吮炕？可以參考這篇文章【算法】Longest Palindromic Substring。
分析思路
理解題目后熊赖，總共想到三個思路：
- 按位比較： 1. 計算整數(shù)的位數(shù)（長度）来屠， 2. 從第一位和最后一位開始依次遞增和增減循環(huán)比較。
- 反轉(zhuǎn)輸入int震鹉，與原數(shù)比較看是否相等俱笛。 之前有道題是：反轉(zhuǎn)一個int數(shù)，其中需要考慮溢出問題传趾。
- 轉(zhuǎn)成字符串迎膜，按位比較。 但題目限制不能占用額外內(nèi)存浆兰。
考慮使用第一種思路磕仅，這道題比較簡單珊豹，有了思路后，按說就可以編碼了榕订，但為了養(yǎng)成好習(xí)慣店茶，別著急編碼還是想下case情況先。我只想到兩個：1.負數(shù)不是回文數(shù)劫恒。 2. 考慮位數(shù)奇偶數(shù)情況贩幻。雖然少，過程不能省两嘴。
開始編碼丛楚，貼下我第一版代碼。
public boolean isPalindrome(int x) {
if (x < 0) { // 負數(shù)情況
return false;
}
final int originX = x;
int bitCount = 1;
// 算出有多少位（長度）
while (x >= 10) {
x /= 10;
bitCount++;
}
int l = 0;
int r = bitCount - 1;
// 依次比較
while (getBitNum(originX, bitCount, l) == getBitNum(originX, bitCount, r)) {
l++;
r--;
if (l >= r) {
return true;
}
}
return false;
}
// 去取原數(shù)對應(yīng)位下標(biāo)的數(shù)值
int getBitNum(int num, final int len, int index) {
int temp = 1;
while (len - index > 1) {
temp *= 10;
index++;
}
return (num / temp) % 10;
}
LeetCode上類似白板編程憔辫，代碼比較齪趣些，請見諒。編寫完了自測case贰您，好都沒問題坏平，這么簡單那就提交吧，提交是通過了锦亦，但提示該算法擊敗了1.7%的其它用戶提交功茴，也就是說效率很差，墊底了孽亲。這樣怎么行呢，畢竟咋還是有追求的程序猿對吧展父。于是分析代碼返劲，其中三處循環(huán)，還有嵌套栖茉；估算時間復(fù)雜度為：O(nlog10n)篮绿。* （ps:時間復(fù)雜度計算，不是很清楚吕漂，有知道的大神請留言指教亲配，謝謝。）
懷著焦慮的心情惶凝，點開了官方推薦解法頁面吼虎。看到一半苍鲜，哎呀思灰，這不是上文中我想到的第二條思路嗎，反轉(zhuǎn)int整數(shù)混滔。但官方建議只反轉(zhuǎn)int的一半洒疚，然后與剩下一半比較歹颓，如果相等則是回文數(shù)。這就完美避開了Integer.MAX_VALUE溢出問題油湖，不得不服巍扛。
想著先不看其代碼實現(xiàn)，自己寫一下再說乏德，于是在之前基礎(chǔ)上改出了下面的代碼撤奸。
boolean isPalindromeNum(int x) {
if (x < 0) {
return false;
}
final int originX = x;
int bitCount = 1;
while (x >= 10) {
x /= 10;
bitCount++;
}
int index = 0;
int halfNum = 0;
final int halfLen = bitCount / 2;
int tempX = originX;
while (index < halfLen) {
halfNum = halfNum * 10 + tempX % 10;
tempX /= 10;
index++;
}
// 判斷奇偶情況
return halfNum == (bitCount % 2 == 0 ? tempX : tempX / 10);
提交跑起來，嗯快了不少鹅经，擊敗了48%寂呛，感覺不錯對吧。這會去看官方給出的C#代碼實現(xiàn)瘾晃，看完感覺受到一萬點傷害贷痪，吐血了。不說了蹦误，貼代碼劫拢。
boolean isPalindromeNumOfficial(int x) {
// Special cases:
// As discussed above, when x < 0, x is not a palindrome.
// Also if the last digit of the number is 0, in order to be a palindrome,
// the first digit of the number also needs to be 0.
// Only 0 satisfy this property.
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber / 10;
}
注釋寫的很清楚了，主要有三點：1. 判斷尾數(shù)為0的情況 2. 取消判斷位數(shù)的邏輯 3. 聰明處理奇偶位數(shù)情況强胰。
小結(jié)
小小一道簡單的算法題舱沧，都能頻繁帶給你刺激，是不是很過癮偶洋。想想平時我們寫的代碼熟吏，是不是應(yīng)該翻出來再斟酌斟酌，哈哈哈玄窝。
最后貼下轉(zhuǎn)字符串思路實現(xiàn)的代碼牵寺。
// 轉(zhuǎn)字符串在比較 ，速度是很快的
public boolean isPalindromeForString(int x) {
String num = String.valueOf(x);
if (num == null || num.length() == 0) return true;
int start = 0, end = num.length() - 1;
while (start < end) {
if ((char) num.charAt(start) != (char) num.charAt(end)) return false;
start++;
end--;
}
return true;
}
以上代碼均由Java實現(xiàn)恩脂，項目地址https://github.com/yangjiantao/DSAA帽氓。
