FXTi's blog
0%

palindrome-number

Posted on Edited on

Palindrome Number – LeetCode 9

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.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;  
        int div = 1;  
        while (x / div >= 10) 
            div *= 10;  
        
        while (x != 0) {  
            int l = x / div;    
            int r = x % 10;  
            if (l != r) 
                return false;  
            x = (x % div) / 10;  
            div /= 100;  
        }  
        return true; 
    }
};

思路

判断是否为回文数，注意负数都不是回文数。同时LeetCode官方也提示了要注意溢出的问题，并额外要求空间复杂度是$O(1)$。这使得将int变量转换为string变量的想法落空。于是采用先获取int变量宽度然后双向取出对应位的值进行对比的做法。时间复杂度$O(\log_{10}{n})$，空间复杂度$O(1)$。
耗时$132$ ms,排名$17.25\%$。
同时发现每次提交得到的耗时结果都不一样，玄学…

Better

思路

还没看到更好的思路