https://leetcode.com/problems/palindrome-number/description/
又水了一道很简单的题，求回文数，只要记着负数肯定不是回文数就可以了。
简单从左右分别开始比较：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x>=0:
xStr=str(x)
left=0
right=len(xStr)-1
while right-left>=1:
if xStr[left] != xStr[right]:
return False
left=left+1
right=right-1
return True
else:
return False
|
用时 192ms 用 Python 字符串反转的方式最简洁，一行搞定：
1
2
3
4
5
6
7
| class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
return str(x) == str(x)[::-1]
|
用时 205ms，和上一种方法几乎一样
使用 Java 语言，继续将数字转换成字符串的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isPalindrome(int x) {
Boolean is_palin=true;
String x_s=Integer.toString(x);
for(int i=0;i<x_s.length()/2;i++){
if(x_s.charAt(i)!=x_s.charAt(x_s.length()-i-1)){
is_palin=false;
break;
}
}
return is_palin;
}
}
|
用时 100ms，刚好在平均水平上。
Leetcode 提示可以不用转换为字符串，这个可能就会麻烦一些，而且速度会慢很多：
大概思路是使用一个栈来解决问题，先通过 10 的对数决定数字的位数，然后根据位数进行循环，在前半段（也就是数字中后 1/2 的位）将数字推入栈内，在后半段（也就是数字中前 1/2 的位）不断将之前推入栈内的数字出栈，并和当前数位上的数字比较，如果不相同，则判断不是回文数。
处理的时候需要注意小于 0 的情况，也要注意奇数和偶数在前后两段分段上的不一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public boolean isPalindrome(int x) {
Boolean is_palin=true;
if(x<0)
is_palin=false;
Stack<Integer> st= new Stack<Integer>();
int x_len=(int)(Math.log(x)/Math.log(10))+1;
int even_or_odd=x_len%2;
for(int i=1;i<=x_len;i++){
int res=x%10;
x=x/10;
if(i<=x_len/2){
st.push(res);
}else if(i>x_len/2+even_or_odd){
int res_pop=(Integer)st.pop();
if(res_pop!=res){
is_palin=false;
break;
}
}
}
return is_palin;
}
}
|
标准答案的思路是直接将数字逆转，判断和原数字是否相等，思路和 Python 逆转字符串几乎如出一辙。但这种解法会非常慢，以至于只超过了 27.26%的人（还是在处理了小于 0 的情况以后）。当然，官方例子排除了更多的情况，运行速度更快一些。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isPalindrome(int x) {
if(x<0)
return false;
int num=x;
int reverted_x=0;
while(num>0){
reverted_x=reverted_x*10+num%10;
num/=10;
}
return reverted_x==x;
}
}
|