09. 回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

• -2^31 <= x <= 2^31 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

题解

根据题干可知：

1. 当 x 为负数时，由于负号的存在，必定不为回文数；
2. 当 x 为非负个位整数时，必定是回文数；

所以可以直接通过简单判断，将这两种情况直接返回：

if (x < 0) return false;
if (x >= 0 && x <= 9) return true;

对于剩余 x >= 10 的情况，比较好理解的方法就是将 x 转换为字符串，然后判断字符串是否为回文串即可。

解法一：字符串为回文串

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        if (x >= 0 && x <= 9) return true;
        std::string tmp = std::to_string(x);
        for (int i = 0; i < tmp.size() / 2; i++) {
            if (tmp[i] != tmp[tmp.size() - 1 - i]) return false;
        }
        return true;
    }
};

解法二： 反转一半数字

官方题解给出另一个解法，通过比较翻转数字，比较翻转结果和原始数字是否相等来判断是否为回文数。

但是官方也提到，这种解法存在部分数字反转后溢出的问题。不过换个角度想，根据回文数的定义，反转后应该等于这个数本身，这也就意味着，由于输入必然不会溢出，那么如果反转后数字出现溢出，那么这个数必然不是回文数。

即使进行逻辑优化，判断反转结果是否溢出仍然是不可避免的，并且并没有对时间复杂度产生优化。因此官方基于反转数字提出了一种更优化的解法，即反转一半数字。

根据回文数的特征，将后半部分的数字进行反转，应该要和前半部分数字相等（当数字位数为奇数时，这个逻辑仍然成立，只需去除中间位即可）。

这个解法的关键在于：如何判断当前已经反转了一半的数字。

由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。

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

总结

1. 通过回文数特征，提取出 x < 0 ，0 <= x <= 9，以及 x 为 10 的倍数这几种特殊情况，快速判断返回；
2. 将 x 是否为回文数问题，转换为 x 这个字符串是否为回文串问题；
3. 根据回文数特征，回文数反转后等于数字本身，但是需注意直接反转存在溢出问题；
4. 回文数后半部分反转后等于前半部分，通过判断 x <= 反转结果 y, 得到此时已经反转一半数字；
5. 当数字为奇数位时，只需去除中间位，判断剩余部分 x == y / 10 即可；