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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

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

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

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

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

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

   通过测试用例：11510 / 11510

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

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

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

   还有一种方法比较巧妙，我们利用乘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 := 0for x > revertedNumber {revertedNumber = revertedNumber * 10 + x % 10x /= 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%的用户

四、总结：

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