码疯窝

LeetCode 每日一题 — Palindrome Number

2014/12/26 10:10:22    分类: 日志连载    0人评论 次浏览

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.

算法分析: 判断数字是否回文, 题目很简单, 但是容易走入误区. 首先想到的是字符串首尾比较, 但是题目说不能使用额外的空间, 于是只能通过计算, 想以同一种的思路判断首尾数字是否不同. 于是写出算法(C++版本). 并且成功通过验证. 写完后感觉有些不对劲. 每次计算出最高位和最低位, 最高位, 然后去除最高位和最低位. 如此循环, 可以如果最高位后面跟上数字0呢? 比如 1000221, 此算法计算此数字就与计算1221无异了. 会返回true. 但是在leetcode 上面竟然可以通过. 估计是leetcode 上缺少此testcase. 所以正确的解法如题意所说将数字反转, 然后与原数字比较. 下面C++ 是错误算法, 但能通过leetcode, java 和python 是正确的算法.

Java:

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

C++:

class Solution {
public:
    bool isPalindrome(int x) {
        int len = 1, left =0, right = 0;
        if (x < 0)
            return false;
        while(x / len >= 10)
            len *= 10;
            
        while (x >0) {
            left = x / len;
            right = x % 10;
            if (left != right)
                return false;
            x = x % len / 10;
            len /= 100;
        }
        return true;
    }
};

Python:

class Solution:
    # @return a boolean
    def isPalindrome(self, x):
        o = x
        ret = 0
        flag = 1
        if x < 0:
            return False
        while(x != 0):
            ret = ret * 10 + x % 10
            x = x / 10
        return ret == o
继续查看有关 日志连载的文章

0个访客评论