每日算法——letcode系列

问题 Reverse Integer

Difficulty: Easy

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.

class Solution {
public:
    bool isPalindrome(int x) {
        
    }
};

翻译

回文数

难度系数：简单

不用其他空间，判断一个数是否为回文数

注意事项：

负数是否是回文数？

如果想把整数转成字符串，注意不用其他空间的限制？

也许你在试着通过反转这个整数来解决，然而，如果你用反转整数来解决这个问题， 你知道反转可能会造成越界， 怎么来处理这种情况？

有更通用的方式来解决这个问题。

思路

如果是字符串，只需要双指针批向首尾两端，判断是否相等，再向中间遍历。
同理对于整数，取出最高位和最低位，比较是否相等，相等再处理次高位和次低位。

代码

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0){
            return false;
        }
        
        // 求整数位数
        int len = 1;
        while (x / len >= 10) {
            len *= 10;
        }
        
        while (x != 0) {
            int hight = x / len;
            int low = x % 10;
            if (hight != low){
                return false;
            }
            x = (x % len) / 10;
            len /= 100;
        }
        
        return true;
    }
};