9. Palindrome Number

本文给出了Leetcode第9题的代码.

Palindrome Number

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

click to show spoilers.

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        
        int num = x;
        int count = 0;
        while(num != 0){
        	count++;
        	num /= 10;
        }
        
        int fistHalf;
        int lastHalf;
        int medium = count/2;
        int weight = (int) Math.pow(10,medium);
        if(count%2 == 0){
	        fistHalf = x/weight;
	        lastHalf = x%weight;
        }else{
        	fistHalf = x/(weight*10);
        	lastHalf = x%weight;
        }
        
        //int weight = (int) Math.pow(10,medium-1);
        weight /= 10;
        for(int i=0;i<medium;i++,weight /= 10){
        	int tail = fistHalf%10;
        	int head = lastHalf/weight;
        	fistHalf /= 10;
        	lastHalf %= weight;
        	if(tail != head)
        		return false;
        }
        return true;
    }
}

还有比我简单多了的方法，清晰名了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isPalindrome(int x) {
    // 因为算法已经cover了10,20,30,...有尾巴一串0的corner case，所以这里不用判断
    if (x < 0) {
        return false;
    }
    int tempX = x;
    int reverse = 0;
    // 当tempX剩下一位数的时候停下来
    while (tempX >= 10) {
        reverse = reverse * 10 + tempX % 10;
        tempX /= 10;
    }
    //对比整个x的头尾两位，以及中间所有位reverse以后是否与不reverser时一致
    return tempX == x % 10 && reverse == x / 10;
}
本文总阅读量次.

留言

▲