Palindrome Number

傷城~ 2022-06-04 05:29 167阅读 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.

# 分析 #

## 1. 题目要求 ##

给出一个 int 类型的整数，判断该整数是否为回文数。要求不使用额外的空间。

## 2. 求解思路 ##

1. 如何没有最后一个要求，我们可以提取出每一位上的数字（与将整数转换成 string 差不多），然后判断是否为回文数。

2. 可以求解出该整数反转之后的整数，判断两个整数是否相同。但是，对于一个 int 类型的整数，求解出其反转后的整数，有可能溢出。如果在求解过程中将 int 转换出 long long 类型的则可以正确求解，不会出现溢出的情况。

3. 也可以反转其后半部分的数字，与前半部分进行比较，看是否相同。该方法在 int 内不会溢出。例如：12344321，其后半部分反转后为 1234，前半部分为 1234。相同，为回文数。

注意：负数不是回文数。

## 3. 代码如下 ##

class Solution {
    public:
        bool isPalindrome(int x) {
            if (x < 0 || (x % 10 == 0 && x != 0)) return false;
            int a = 0;
            while (a < x) {
                a = a * 10 + x % 10;
                x /= 10;
            }
            if (a == x || a / 10 == x) return true;
            else return false;
        }
    };