PalindromeNumber [source code]

public class PalindromeNumber {
static
/******************************************************************************/
public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        //terminating condition: either rev == x or rev > x;
        return rev == x || rev / 10 == x;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PalindromeNumber.Solution tester = new PalindromeNumber.Solution();
        int[] inputs = {10, 100};
        for (int i : inputs) System.out.println(i + " -> " + tester.isPalindrome(i));
    }
}

这个代码是discussion 上面的最优解: 166(99.96); 这个代码的思路是直接只比较到一半的位置(一半是通过一个类似 Binary Search 的 header 那样的比较来找到的), 不过这样找到的一半可能受到 x 的长度是奇数还是偶数影响, 所以最后要分别都考虑一下;
这个算法有一个 bug, 就是这个 reverse 之后重新 assemble 的过程, 看起来很聪明, 做到了O(1)的 space, 但是有一个缺点, 就是这样做, 所有 x 的trailing zeros都被无视了. 所以最开始要对所有有trailing 0的情形做一个单独的判断;

no extra space means anything of the order greater than O(1) .
Extra space would mean if the space can be expressed as a function of the length of the input. For eg. space could be O(n) if we store the n numbers while comparing arrays.

No extra space means O(1) extra space

我这个问题没有想通的一个原因在于, 我对于这种 reverse 的问题, 只有一个固化的思路, 就是所有的 digit 全部都 collect 到一个 array 里面, 然后比较;
这里 discussion 里面的一个普遍的技巧是, 没摘下来一个 digit, 直接放到另外一个 int 里面; 这样最后我们需要维护的只有一个单独的 int;

另外, 这题最 naive 的做法其实是非常简单的: 先判负; 如果不是负, 就直接做一个 reverse, 然后return x == rev就行了. 不需要担心 overflow, 因为正数的 reverse 不可能overflow; 严格来说也不是因为是正数就不会 overflow: 如果 x 本身是一个正数, 然后你最后计算出来的 rev 其实是不可能超过 x 的;
//后来想通了, 这个理解是不对的, 就算是正数, 也有可能是 overflow 的:因为 MAX 是2开头的10位数. 如果 x 比如是1开头的10位, 但是个位大于2, 那么就 overflow 了;
这个是原作者的说法:

Hi guys. I just don't know why we need to concern the overflow. When the reversed number overflows, it will becomes negative number which will return false when compared with x.
Here is my AC code.

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

这个是我给出的解释:
@wen587sort This solution is correct, but overflow can still occur even if we ruled out "x being negative".

Consider x == 12345_56789, then in the last iteration of your algorithm, there will be a 98765_5432 * 10 + 1 going on. This operation will overflow. Given this x, the res before your algorithm ends will be 1286619729 (according to OJ).

But again, your solution is correct, because such a situation won't matter in that an overflowing x won't make the algorithm return true anyway.
We all know that Integer.MAX_VALUE is a 10-digit number starting with 2. Let di denote the i-th digit of x, with i = 0..9. Since x is a given input, it does not overflow in itself. We know that d9 ≤ 2. And the only way that an overflow occurs, during iterations, in such a situation, is d0 > 2, because then in the last iteration's res = res * 10 + y % 10; we will have a 10-digit number starting with d0, which is larger than 2. It is also easy to see that in such a situation, the algorithm would spit out false anyway. That is, aside from knowing that "negative number is not palindrome", we can also say that "overflowing positive number also can not be palindrome".

To sum up:

• for negative numbers, this algorithm returns false, which is the right output.
• for positive numbers that don't overflow, this algorithm returns the right output, either it being true or false.
• for positive numbers that does overflow, this algorithm returns false, which coincides with the expected answer: such positive numbers can't be palindrome anyway according to analysis above.

这个问题解决起来其实也不难:

public boolean isPalindrome(int x) {  

    if (x < 0) return false;  

    int p = x;   
    int q = 0;   

    while (p >= 10){  
        q *=10;   
        q += p%10;   
        p /=10;   
    }  

    return q == x / 10 && p == x % 10;  
}

提前结束就行了, 因为只有最后一个 iteration 可能会 overflow;

关于这个算法的复杂度:

For those that are confused with the argument whether this algorithm is O(N) or O(lgN):
This algorithm is O(N) where N is the number of digits. At the same time it is O(lnX), where X is the input value.
Now, stop arguing about the time complexity and concentrate on coding.

另外以后打卡的时候, 如果碰到这种类似的不会做的题目, 就只允许等到 discussion 看完了之后, 再自己写一个学来的解, submit. 用比较长的时间来标志第一次做这个题目的时候的难度;

discussion 上面还有一个有意思的解法:

class Solution {  
public:  
    bool isPalindrome(int x) {  
        if(x<0) return false;  
        int fast=x,slow=x,rhalf=0;  
        while(fast/10){  
            rhalf = rhalf*10 + slow%10;  
            slow /= 10;  
            fast /= 100;  
        }  
        return fast==0?rhalf==slow:slow/10==rhalf;  
    }  
};

这个是用一个类似2pointers 或者龟兔赛跑的思路, 来找到半长度的这个点; 一个稍微需要注意的地方就是odd or even length的分别处理;

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:35.09%
Contributor: LeetCode
Related Topics
math
Similar Questions
Palindrome Linked List