LeetCode NO. 9 Palindrome Number
LeetCode 第9題 回文數(shù)
DIFFICULTY(難度)
EASY
容易
DESCRIPTION(題面)
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
判斷一個整數(shù)是否是回文數(shù),回文數(shù)就是正讀反讀都相同的數(shù)字
EXAMPLE(樣例)
ONE
Input: 121(輸入:121)
Output: true(輸出:true)
輸入:121
輸出:true
TWO
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
輸入:-121
輸出:false
解釋:從左向右讀是-121,從右向左讀是121-避乏,因此不是回文數(shù)
THREE
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
輸入:10
輸出:false
解釋:從右向左讀為01憾儒,因此10不是回文數(shù)友扰。
FOLLOW UP
Could you solve it without converting the integer to a string?
你能否在不將整數(shù)轉(zhuǎn)化為字符串的情況下蔬芥,判斷出該整數(shù)是不是回文數(shù)?
SOLUTION(解題)
class Solution {
public:
bool isPalindrome(int x) {
if(0 > x || (x % 10 == 0 && x != 0)) {
return false;
}
int reversed = 0;
while(x > reversed) {
reversed = reversed * 10 + x % 10;
x = x / 10;
}
return x == reversed || x == reversed/10;
}
};
NOTE(注)
思路1:轉(zhuǎn)字符串
將整形轉(zhuǎn)換成字符串漆改,從兩側(cè)向內(nèi)依次比較即可沾瓦。既然題目提示了不轉(zhuǎn)換字符串的方式判斷满着,何不試一下?
思路2:反轉(zhuǎn)整個數(shù)字
將整個整數(shù)反過來贯莺,如果反轉(zhuǎn)數(shù)字和原數(shù)字相同那就說明這個整數(shù)是回文數(shù)风喇,第一次提交就是這種方案,結(jié)果遇到了reversed越界缕探,因為使用了乘法嘛魂莫,越界沒有考慮到,改成long類型通過爹耗。提交后查看最佳提交的解題思路耙考,如思路3
思路3:反轉(zhuǎn)數(shù)字的一半
既然會有越界問題,那不計算那么多位就好了潭兽,也就是不要把整個數(shù)字都反轉(zhuǎn)過來倦始。從思路2的計算過程,原數(shù)字x在不斷被除10山卦,而余數(shù)則是不斷的被累加到反轉(zhuǎn)數(shù)的低位鞋邑,那是不是說如果這個數(shù)字是回文數(shù),那么當(dāng)計算到一半的時候怒坯,原數(shù)字x會與反轉(zhuǎn)數(shù)reverse是相等的炫狱,所以只要反轉(zhuǎn)一半就好了,那如何判斷反轉(zhuǎn)到一半的位置了呢剔猿,因為x在不斷被除10,reverse不斷在低位累加嬉荆,那么當(dāng)x小于reverse的時候归敬,就說明已經(jīng)轉(zhuǎn)換了一半的數(shù)字了。
例1:101
計算過程變量值
x | reversed |
---|---|
101 | 0 |
10 | 1 |
1 | 10 |
發(fā)現(xiàn)reverse的值其實是比x的最終值要大的,發(fā)現(xiàn)reverse的最后一位汪茧,就是原x中間的那一位椅亚,而這一位并不影響判斷這個數(shù)是不是回文數(shù),所有的奇數(shù)位數(shù)的整數(shù)都符合這個規(guī)律舱污,所以只要判斷去掉個位的其余數(shù)字相同即可呀舔,因此判斷條件是 x == reversed/10
,如例2
例2: 10101
計算過程變量值
x | reversed |
---|---|
10101 | 0 |
1010 | 1 |
101 | 10 |
10 | 101 |
例3:1001
計算過程變量值
x | reversed |
---|---|
1001 | 0 |
100 | 1 |
10 | 10 |