LeetCode-Palindrome Number

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