回文数

Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

1 2	Input: 121 Output: true

Example 2:

1
2
3

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

1
2
3

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

题目大意

给定一个整数，即会出现正数与负数
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数

解题思路

根据上述对于回文数的定义，可以将数字进行反转，如果反转后的数字与原数字相同即可确定为回文数，这里会有一个问题，反转后的数字可能会大于 math.MaxInt32，导致溢出。

这里转换一种思路，32位整型取值范围为 -2147483648 ~ 2147483647，可以对给定的整数的一半数字进行翻转，与另一半进行比较，二者相同即可判定为回文数，同时解决了可能溢出的问题。

如给定 1452541，我们可以看到数字长度为奇数，所以对 541 进行翻转，得到 145 ，与整数另一半相同，判定为回文数

一种临界情况即给定数字为负数，因为包含 - 号，翻转后 -121 -> 121-；另一种临界情况为，给定的整数最后一位为 0，除 0 以外的任意整数都不满足，确定不是回文数，所以对于负数统一返回 false

处理方式我们和整数反转中使用的方式类似

Q: 我们如何知道反转数字的位数已经达到原始数字位数的一半？

A: 我们将原始数字除以 10，然后给反转后的数字乘上 10，所以，当原始数字小于反转后的数字时，就意味着我们已经处理了一半位数的数字。

代码

func isPalindrome(x int) bool {
    // 1.当 x < 0 时，x 不是回文数
    // 2.数字的最后一位是 0, 为了使该数字为回文, 只有 0 满足这一属性
    if(x < 0 || (x % 10 == 0 && x != 0)) {
        return false
    }

    rev := 0
    for x > rev {
        rev = rev * 10 + x % 10
        x /= 10
    }

    return x == rev || x == rev/10
}

复杂度分析

时间复杂度： $O(\log_{10}(n))$
空间复杂度： $O(1)$

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。