leetcode9.Palindrome Number

发表于 更新于 分类于 ，

题目要求

1
判断一个数字是否是回数，不能同使用自然数生成string或数组那样的方式实现

回数的定义：一个自然数，如果该自然数从左向右读和从右向左读都是一样的数，则这个数为回数（隐藏条件，回数不可以为负数）

思路一：双指针

将数字看成是一个数组，使用两个指针分别指向这个数字的首尾，并且判断当前左右指针上的数字是否相等，相等则继续推进直至左右指针相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//双指针，将左右指针分别指向数字的首位
public boolean isPalindrome(int x) {
    if(x<0 || (x%10==0&&x!=0)){
        return false;
    }
    int rightPointer = 0;
    //获得右指针的初始值，即数组的长度
    while(Math.pow(10, rightPointer)<=x){
        rightPointer++;
    }
    rightPointer--;
    int leftPointer = 0;
    while(rightPointer>leftPointer){
        int left = (int) (x/Math.pow(10, leftPointer)%10);
        int right = (int) (x/(Math.pow(10, rightPointer))%10);
        leftPointer++;
        rightPointer--;
        if(left!=right){
            return false;
        }
    }
    return true;
}

思路二：判断生成的数字是否相等

上面用数组的思维解决数字的遍历是一种方法，但是要先通过一圈遍历获得右指针，增加了时间。所以可以采用从右至左遍历数字并按照添加顺序有小到大生成新的数字，判断最终生成的数字是否和遍历结束的数字相等。
这里需要考虑一种特殊情况，即当末尾为0的情况。若不优先考虑该情况，就会生成错误的结果

1
2
3
4
5
6
7
8
9
10
11
public boolean isPalindrome2(int x) {
    if(x<0 || (x%10==0&&x!=0)){
        return false;
    }
    int res = 0;
    while(x>res){
        res = res*10 + (x%10);
        x /= 10;
    }
    return (x==res || x==(res/10));
}