LeetCode No.9 [Palindrome Number]

Description

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Leet Code Link


基于字符串的实现

基于字符串的实现很简单: 转换成字符串数组后进行前后比对, 如果不相同则返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isPalindrome(x int) bool {
if x < 0 {
return false
}
bytes := []byte(strconv.Itoa(x))
for i, j := 0, len(bytes)-1; i < j; i, j = i+1, j-1 {
if bytes[i] != bytes[j] {
return false
}
}
return true
}

基于数学算法的实现

基于数字算法的实现是通过反转算法,从低位开始取出数字并进行反转的叠加,并去除原数字中低位部分,当原数字小于等于反转的数字后开始进行判断。(其中还包括负数、小于10、个位为0时的判断逻辑)

1
2
3
12321 => {x:12321, y:0} => {x:1232, y:1} => {x:123, y:12} => {x:12, y:123} => x=y/10 => true
1221 => {x:1221, y:0} => {x:122, y:1} => {x:12, y:12} => x=y => true
1222 => {x:1222, y:0} => {x:122, y:2} => {x:12, y:22} => x!=y => false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isPalindrome(x int) bool {
if x < 0 || (x != 0 && x%10 == 0) {
return false
}
if x < 10 {
return true
}
y := 0
for y < x {
y = y*10 + x%10
x = x / 10
}
return x == y || x == y/10
}