首页 > 基础算法 > 模拟法 > LeetCode-Palindrome Number[模拟]
2014
11-19

LeetCode-Palindrome Number[模拟]

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

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.

标签: Math
分析

首先想到,可以利用上一题,将整数反转,然后与原来的整数比较,是否相等,相等则为 Palindrome 的。可是 reverse()会溢出。

正确的解法是,不断地取第一位和最后一位(10进制下)进行比较,相等则取第二位和倒数第二位,直到完成比较或者中途找到了不一致的位。

代码1

//LeetCode, Palindrome Number
// 时间复杂度O(1),空间复杂度O(1)
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int d = 1; // divisor
        while (x / d >= 10) d *= 10;

        while (x > 0) {
            int q = x / d;  // quotient
            int r = x % 10;   // remainder
            if (q != r) return false;
            x = x % d / 10;
            d /= 100;
        }
        return true;
    }
};

Java代码:

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

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?