算法题: 回文数 内附多种解法 LeetCode 第9题

题目

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

示例 1:

输入: 121

输出: true

示例 2:

输入: -121

输出: false

解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10

输出: false

解释: 从右向左读, 为 01 。因此它不是一个回文数。

我的思路

• 转换成字符串后, 对称对比
• 取出每一位后对称对比
• 取出每一位形成新数与原数对比(看了大神的代码后才发现的)

我的代码

class Solution {
    public boolean isPalindrome(int x) {
        if (x == 0) {
            return true;
        }
        if (x % 10 <= 0) {
            return false;
        }
        int [] arr = new int[20];
        int i = 0;
        while(x > 0) {
            arr[i] = x % 10;
            x = x / 10;
            i++;
        }
        for (int j = 0; j < i/2 || j== i-1 ; j++) {
            if (arr[j] != arr[i-j-1]) {
                return false;
            }
        }
        return true;
    }
}

• 改进后的代码 反转后与原数对比

class Solution {
    public boolean isPalindrome(int x) {
        int z = x, i = 0;
        while(x > 0) {
            i = i * 10 + x % 10;
            x = x / 10;
        }
        return i == z;
    }
}

有点疑惑的是两者用时相当, 有没有人来告诉我为什么?

另一种思路 转字符串后对称比较

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0)return false;
        String str=x+"";
        int i=0;
        int j=str.length();
        while(i<j){
            if(str.charAt(i++)!=str.charAt(--j)){
                return false;
            }
        }
        return true;
    }
}

c语言代码

int reverse(int x){
    int ret=0,max=0x7fffffff,min=0;
    long rs=0;
    for(;x;rs=rs*10+x%10,x/=10);
    return ret=rs>max||rs<min?0:rs;
}
bool isPalindrome(int x){
    return x==reverse(x);
}

python 代码

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if str(x)[::] == str(x)[::-1]:
            return True
        else:
            return False

LeetCode 第9题