LeetCode 9. 回文数

LeetCode 9. 回文数

一、题目描述：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，121 是回文，而 123 不是。 示例 1： 输入：x = 121 输出：true 示例 2： 输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3： 输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。 提示： -231 <= x <= 231 - 1 进阶：你能不将整数转为字符串来解决这个问题吗？ 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/palindrome-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

这道题考察了什么思想？你的思路是什么？

我的思路很简单，如果数字大于0，将其转化为字符串，然后将字符串的第一个字符与最后一个字符进行比较，如果相等，再将字符串的第二个字符与倒数第二个字符进行比较，以此类推，直到出现不相等的情况，或者指针到达中心仍没出现不等的情况，我们就认为这个数是回文数。如果数字小于0，我们直接认为不是回文数，返回false。

这种思路能够通过，但是时间复杂度和空间复杂度都比较高：

执行用时：16 ms, 在所有 Go 提交中击败了51.19%的用户

内存消耗：4.6 MB, 在所有 Go 提交中击败了25.46%的用户

通过测试用例：11510 / 11510

做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？

是一次通过的，只是在调试的时候，因为写Python写惯了，忘记了x是int类型，在将x转化为string类型时，仍然将结果赋值给x，导致出错。

有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

还有一种方法比较巧妙，我们利用乘10和除10的方法，提取数字x的后一半并逆转，然后将原数字中的后一半去除，然后将原数字x除以10与逆转的后一半进行比较，如果相等则返回true，否则返回false。

func isPalindrome(x int) bool {
    // 特殊情况：
    // 如上所述，当 x < 0 时，x 不是回文数。
    // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
    // 则其第一位数字也应该是 0
    // 只有 0 满足这一属性
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false
    }

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

    // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
    // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
    // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
    return x == revertedNumber || x == revertedNumber / 10
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/palindrome-number/solution/hui-wen-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、AC 代码：

func isPalindrome(x int) bool {
    if x < 0{
        return false
    }

    y := strconv.Itoa(x)
    for i:=0;i<(len(y)/2)+1;i++{
        if(y[i] != y[len(y)-i-1]){
            return false
        }
    }
    return true
}

执行用时：8 ms, 在所有 Go 提交中击败了91.71%的用户

内存消耗：4.4 MB, 在所有 Go 提交中击败了51.63%的用户

四、总结：

这道题目最好是不要转换为字符串，因为这将耗费许多额外的空间和时间。