【LeetCode通关全记录】9. 回文数

题目地址：9. 回文数

转换成字符串并反转、比较字符串（实际上就是转换成rune切片并且比较）的解法因为太简单所以这里就不分享啦，主要来看看怎样不转换成字符串解决这个问题。

解法：反转数字并和原数比较

首先考虑特殊情况：

1. 0是回文数，这个不会影响后面的正常解法，因为如果是0的话会直接跳出循环返回true；
2. 小于0的数字因为前面有个负号，所以肯定不可能是回文数；
3. 10的倍数都不可能是回文数，因为反转之后0在最高位，这显然是不行的。

排除这两种情况后我们可以这样做：设置一个变量记录反转后的数字，每次将原数对10取余并给反转数乘10后加到反转数上，最后比较两者是否相同即可。官方题解的反转一半数字是这个解法的变体，效率稍高一些。

需要注意的是这里不需要像官方题解所说的那样考虑溢出的问题，因为只要是回文数那么反转后的数字一定和原数相等所以肯定不会溢出，若不是回文数导致溢出那就算溢出了也不会对算法的正确性产生影响，因为溢出之后的数字肯定和原数不相等。

func isPalindrome(x int) bool {
    // 小于0的因为有负号所以一定不是回文数
    if x < 0 {
        return false
    }
    // 10的倍数都不是回文数,因为最高位不可能是0
    if x % 10 == 0 && x != 0 {
        return false
    }
    // 把数字反转并和原数比较
    num := x
    rev := 0
    for x != 0 {
        rev = rev * 10 + x % 10
        x /= 10
    }
    return rev == num
}

执行用时: 20 ms（超过50%的Golang提交记录）

内存消耗: 5 MB（超过55%的Golang提交记录）

时间复杂度：O(logn)，每次循环都会将原数除以10，所以时间与问题规模呈对数关系；

空间复杂度：O(1)，只使用了常数个数的存储空间。