ACM之判断回文数

题目如下

图片.png

这道题比较简单,先上Python代码感受一下,就一行搞定:

#判断回文数
def isPalindrom(x):
    return  str(x) == str(x)[::-1]

这种方法虽然简单,但是耗时比较长。再用Java解决一下看看

方法一

显然负数不可能是回文数,区间[0,9]的整数肯定是回文数,所以把这些确定的条件先进行判断

将整数的每一位放在链表中,然后将链表逆序,比较逆序链表与顺序链表元素是否一样,一样则是回文数,否则不是

代码如下:

public class PalindromNumber {
    public boolean isPalindrom(int x){
        if(x < 0) return false;
        List<Integer> num = new ArrayList();
        while(x != 0){
            num.add(x % 10);
            x = x / 10;
        }
        int len = num.size();
        List<Integer> numRev = new ArrayList();
        for(int i = len-1;i >= 0;i--){
            numRev.add(num.get(i));
        }
        for(int i = 0;i < len ;i++) {
            if(num.get(i) != numRev.get(i)){
                return false;
            }
                
        }     
        return true;
    }

方法二

    将上述代码优化,发现其实我们只需要比较一般就行了,也就是将数从左往右读的前一半与从右往左读的后一半比较就ok,比如一个数12133121,前一半为1213,后一半是1213,显然数回文数。当一个数不能平均分为两半时,将较大的数(即前一半)整除10得到的数再与小数比较就行,因为前一半各位的数字也可以作为后一半的最高位,是公用的,去掉不会有影响。如121343121,前一半为121234,后一半为1213,12134/10=1213与后一半相同,故判断为回文数

代码:

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

可以直观的对比他们所需的时间,用时最少的是方法二

相关文章
相关标签/搜索