9-Palindrome-Number.md

Palindrome Number

确定一个整数是否是回文, 整数是回文即从前往后和从后往前读是一样的

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
说明: 从左向右读是 -121, 从右向左读是 121-, 因此它不是一个回文

示例 3:

输入: 10
输出: false
说明: 从右向左读是 01, 因此它不是一个回文

附加:

可以不将整数转化为字符串而解决它吗?

解法

方法 1: 还原一半数字

直觉

第一种方法即将数字转换为字符串, 然后检查字符串是否是回文, 但是这会需要额外的非常量空间来创建字符串, 并且在问题描述中这样是不被允许的
第二种方法是反转数字本身, 然后将这个数字与源数值比较, 如果它们相同, 则数字是回文; 然而, 如果反转的数字大于 INT.MAX, 我们将会遇到整型溢出问题
基于第二种方法的思想, 为了避免反转数字的溢出问题, 如果我们仅反转一般整型数字会怎样? 毕竟, 回文的后半部分反转应该与数字的前半部分相同, 如果数字是回文
例如, 如果输入是 1221, 如果我们能反转数字 1221 的后半部分, 从 21 到 12, 然后将其与前半部分数字 12 比较, 因为 12 等于 12, 我们就知道这个数字是回文
让我们看如何将此想法翻译为算法

算法

首先我们应该先关心一些边界问题; 所有的负数都不是回文, 例如: -123 不是一个回文, 因为 '-' 不等于 '3'; 所以对所有负数我们可以直接返回 false
现在让我们考虑如何反转后半部分数字; 对于数字 1221, 如果我们将 1221 % 10, 我们将得到数位 1, 为了继续从最后一位得到第二个数位, 我们需要从 1221 移除上一位数位, 我们可以通过将它除以 10 得到, 1221 / 10 = 122; 然后我们再次将其模以 10 得到最后一位数位, 122 % 10 = 2, 如果我们将最后一位数位乘以 10 再加上第二位数位, 1 * 10 + 2 =12, 这就是我们想要转换的数字; 继续处理更多的数位会得到反转的数字
现在的问题是, 我们如何知道我们已经到达了数字的一半?
因为我们将数字除以 10, 然后将反转数字乘以 10, 当源数小于反转数字时, 即意味着我们已经处理了一般的数字

class Solution {
    public boolean isPalindrome(int x) {
        // x is negative integer number or the last digit of the number is 0
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int reverseX = 0;
        while (x > reverseX) {
            reverseX = reverseX * 10 + x % 10;
            x = x / 10;
        }
        return x == reverseX || x == reverseX / 10;
    }
}

复杂度分析

• 时间复杂度: $O(\log_10(n))$, 我们每次迭代将输入除以 10, 所以时间复杂度是 $O(\log_10(n))$
• 空间复杂度: $O(1)$

参考: Palindrome Number