LEETCODE 9. 回文数

LEETCODE 9. 回文数

题目描述

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:
输入: 121
输出: true

示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:
你能不将整数转为字符串来解决这个问题吗?

利用字符串做反转

这种方式很简单,将整数x变成字符串,然后再拷贝一份字符串,将拷贝后的字符串反转一下。
再比较原字符串和拷贝后的字符串就可以了。

当然有些特殊情况需要预先处理一下,当x<0时候就没法拼接出一个回文数字,所以当x<0时就直接返回false

java代码:

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) {
            return false;
        }
        String oldStr = ""+x;
        String newStr = new StringBuilder(""+x).reverse().toString();
        return oldStr.equals(newStr);
    }
}
                                                                           

python代码:

class Solution(object):
    def isPalindrome(self, x):
        return str(x)==str(x)[::-1]	
                                      

取模运算

用字符串很好理解,但这样的操作纯属多余,实际上我们只需要拿到原数字的最后一位就可以了, 我们用取模运算,就能拿到数字的最后一位,然后用res*10 + x%10这种方式就可以反向的拼接出来了。

  1. 12321通过 %10 得到1,再将老数字12321/10
  2. 1232%10得到2,再将新数字1*10 + 2得到12,同时老数字1232/10
  3. 123%10得到3,新数字12*10 + 3得到123,同时老数字123/10
  4. 12%10得到2,新数字123*10 + 2得到1232,同时老数字12/10
  5. 1%10得到1,新数字1232*10 + 1得到12321,同时老数字1/10

最后比较原数字12321和新拼接出来的数字12321

这种方式有一个隐藏的细节问题,不知道你注意到了没。
如果我们输入的是最大32位整数2147483647,这个数字本身是没有问题,是一个合法的32位最大整数,用int存储也没问题,但是如果将这个数字反转的话,其大小超过了32位最大整数,也就是会溢出

那是否要把变量的类型改成long来存储呢,这样反转后的数字就不会溢出了。
其实不用,虽然我们反转的数字不对,但是返回的结果却是对的。
因为32位整数中最大的回文数2147447412,这个数字是比最大32位整数 小的。
所以超过2147447412大小的数字也就不是回文数字了,虽然我们经过反转后的数字溢出了,但它的返回结果却是对的,这也算是歪打正着。于是我们继续用int类型来保存数字,也没问题。

java代码:

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) {
            return false;
        }
        int ans = 0;
        int old = x;
        while(x>0) {
            ans = ans*10 + x%10;
            x /= 10;
        }
        return ans==old;
    }
}
                                                     

python代码:

class Solution(object):
    def isPalindrome(self, x):
        if x<0:
            return False
        ans = 0
        old = x
        while x>0:
            tmp = x%10
            ans = ans*10 + tmp
            x /= 10
        return ans==old
                                           

反转一半数字

反转整数可能会有益处的风险(虽然结果也是对的),那我们想想是否能优化一下。【回文】的特点是什么?
首尾是一样的

我们不用反转整数的所有数字,只需要反转一半数字就可以了,这是利用了【回文】的对称性。
反转一半数字的代码跟解法二类似,但是循环终止条件不一样,解法二中的循环终止条件是x>0,我们不断的做x/10操作,最终x就会等于0,于是退出循环。但反转一半数字的循环条件就不好写了。
根据数字的长度判来判断循环的次数,这是可以的,但是怎么确定数字的长度呢?
仔细看上面的图,对于奇数长度的回文数字12321,我们可以拆分成两个数12123
对于偶数长度的回文数字123321,我们可以拆分成两个数字123123

那现在就明朗了,我们可以用大于来判断,在循环内原数字不断迭代 处理后如果大于新数字循环就退出。

如果回文数长度为奇数,经常上面的循环处理后,新数字正好是原数字x的10倍,所以返回结果需要考虑奇偶两种情况,即这么判断(假设新数字保存在ans里)

x==ans || x==(ans/10)

对于1020100这样的数字,用上面的判断方式就有问题了,2000这个数字不断循环,退出后变成0,跟新数字一样,于是返回true。

所以我们要对这些数字特殊处理一下,如果某个数字%10等于0,并且它不是0开头,那么直接返回false就可以了。

java代码:

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

python代码:

class Solution(object):
    def isPalindrome(self, x):
        if x<0 or (x%10==0 and x!=0):
            return False
        ans = 0
        while x>ans:
            ans = ans*10 + x%10
            x //= 10
        return x==ans or x==(ans//10)
                                          

(全文完)

2 次阅读

发表评论

电子邮件地址不会被公开。