1. 题目

1.1 英文

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.2 中文

检测一个整形是否是一个回文（从左往右看和从右往左看都相等的数），不要使用额外空间。

提示：

  • 负数是否是回文？
  • 如果你想将整形转化成字符串，注意不要使用额外空间的限制。
  • 你可以尝试反转整形。然而，如果你解决了“反转整形”的问题，那你可能知道反转整形可能会导致溢出，你该如何控制这个情况。
  • 解决这个问题有一个更通用的方法。

2. 解答

接下来我们就来用这个更通用的方法来解决，Go语言实现。

func isPalindrome(x int) bool {
    // 小于0 或者 末尾是0而本身不是0 时，不符合情况
    if x < 0 || ( x % 10 == 0 && x != 0 ){
        return false
    }

    revertedNum := 0
    // x大于revertedNum时说明还未过一半，继续循环
    for x > revertedNum {
        revertedNum = revertedNum * 10 + x % 10
        x = x / 10
    }

    // 判断 x==revertedNum/10 的情况用在当长度为奇数时；比如1234321，最后得到的是123和1234
    return x == revertedNum || x == revertedNum / 10
}

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