当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.009.Palindrome Number

LeetCode.009.Palindrome Number


题目描述

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.


解题过程

判断整数是否回文数,算法很简单,但要考虑溢出就比较麻烦。
题目要求不得使用额外空间(申请临时变量不算),所以不能转为字符串再判断。
首先要知道的常识是:所有负整数都不是回文数

求输入值的逆置和原值比较

如果先求输入整数的逆置,再和原数比较,会有逆置后溢出的风险,我写了个求逆置后判断的版本,是可以AC的,为什么呢?

  • 首先,Integer.MAX_VALUE=2147483647范围内最大的回文数是2147447412,其逆置不会溢出。
  • 其次,如果输入值x的逆置reverse溢出,reverse会变成负的,肯定和x不相等。

所以即使不考虑溢出此方法也能AC

//Integer.MAX_VALUE范围内最大的回文数是2147447412,其逆置不会溢出
//如果x的逆置溢出,reverse会变成负的,肯定和x不相等,所以即使不考虑溢出此方法也能AC
public boolean isPalindrome1(int x) {
    if(x<0)
        return false;
    int a=x;
    int reverse=0;
    while(a!=0){
        reverse = reverse*10 + a%10;
        a = a/10;
    }
    return reverse==x ? true : false;
}

求输入值后半段的逆置和前半段比较

题目中提示了求逆置有溢出风险,那有没有更好的方法呢?
我也想了比较前后段,但那得知道x的位数,求x的位数就得把x遍历一遍,感觉太麻烦,其他更巧妙的求x的逆置过程中就知道已经处理了一半的方法没想到。
然后看Solution,人家给出了方法,说在求x的逆置reverse过程中如何知道已经处理了x位数的一半呢?答案是当x小于reverse时就表明已经处理了x位数的一半,很简单的数学逻辑,竟然没想到。
但是用这种方法需要注意的是10的倍数得单独处理,因为逆置后末尾的0会被忽略,遇到x除去末尾0是回文时,比如122100,会出现reverse和x相等的情况,但这时候x并不是回文数。

下面是我根据Solution中的思想写的,在x除以10前后都和reverse比较一下是为了能同时应对偶数位回文(1221)和奇数位回文(121),第一版我写的忘了单独处理10的倍数,错了一次,目前版本已经AC:

//只逆置x的后半段,和前半段比较
public boolean isPalindrome(int x) {
    //10的倍数(除了0)肯定不是回文数,因为逆置后第一位的0会被舍去
    //必须单独处理10的倍数,否则遇到122100这种除0外是回文的会出错
    if(x<0 || (x%10==0 && x!=0))
        return false;
    int reverse=0;
    while(reverse <= x){ //当x<reverse时,表明已处理了x的后半段
        reverse = reverse*10 + x%10;
        if(reverse==x)
            return true;
        x = x/10;
        if(reverse==x)
            return true;
    }
    return false;
}

Solution中的写法和我不太一样,是在循环结束后再判断:

public boolean isPalindrome(int x) {    
    if(x < 0 || (x > 0 && x % 10 == 0)) return false;
    int num = 0;
    while(x > num){
        num = num * 10 + x % 10;
        x = x / 10;
    }

    // To distiguish the length of the integer is even or odd.
    if(x == num || x == num / 10) return true;
    else return false;
}

GitHub代码


上一篇 LeetCode.004.Median of Two Sorted Arrays

下一篇 LeetCode.206.Reverse Linked List

阅读
915
阅读预计4分钟
创建日期 2018-02-06
修改日期 2018-02-07
类别
百度推荐