102.回文数
题目
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
示例 1：
- 输入：x = 121
- 输出：true
示例 2：
- 输入：x = -121
- 输出：false
- 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
- 输入：x = 10
- 输出：false
- 解释：从右向左读, 为 01 。因此它不是一个回文数。
思路
最容易想到的方法是：把整数转换成字符串，然后检查字符串是否回文。但这样需要额外 O(n) 的空间，并且涉及字符串操作。
更好的方法是只反转数字的后半部分，并与前半部分比较。因为回文数的后半部分反转后应该等于前半部分。
例如： 1221：前半部分 12，后半部分反转后也是 12，相等 → 回文。 12321：前半部分 12，后半部分反转后是 123（多了一位），去掉最后一位后是 12，相等 → 回文。 这样做的优点： 不需要处理整个数字，避免溢出（反转整个数字可能溢出，但反转一半不会）。 空间复杂度 O(1)。
最直观的想法是：把这个数字的后半部分倒过来，再和前半部分比。 但不用把整个数字都倒过来，只倒一半就够了。因为如果一个数是回文，中间往左和往右本来就是对称的。 怎么做？
-
先排除两种一定不是回文的情况：
- 负数，比如 -121，前面有个 -，不可能对称。
- 末尾是 0 但本身不是 0，比如 10，反过来会变成 01，不一样。
- 然后把右边的数字一位一位“拿出来”，拼成 rev
-
当 rev 已经和原数的左半边一样长时，就停下
-
最后比较：
- 偶数位：前半部分 == 后半部分
- 奇数位：中间那一位不用管，所以 前半部分 == 后半部分 / 10
举个例子 1221
- 从右边拿出 1，rev = 1
- 再拿出 2，rev = 12
- 这时左边剩下 12
- 左边 12 和右边 12 一样，所以是回文
举个例子 12321
- 一直拿到 rev = 123
- 左边剩下 12
- 这是奇数长度，中间的 3 不用管
- 所以比较 12 和 123 / 10 = 12，一样，就是回文
while (num > reversedHalf) 这个判断的原理
核心思想： 用数值大小来代替位数技术
我们没办法直接知道数字有多少位(除非用循环数一遍)，但我们可以在翻转的过程中，观察num(剩余的前半部分)和reversedHalf(反转的后半部分)的数值大小关系，来判断是否已经处理了一半。
直观感受:
- 一开始，num 很大（整个数字），reversedHalf 是 0，显然 num > reversedHalf。
- 每反转一位，num 少一位（数值大约除以10），reversedHalf 多一位（数值大约乘以10再加一位）。
- 当 num 的位数变得小于等于 reversedHalf 的位数时，数值上就会发生翻转：num 不再大于 reversedHalf。
也就是说，当 num <= reversedHalf 时，就意味着我们已经处理了至少一半的数字。
为什么不是 while (num != 0)？
如果写成 while (num != 0)，就会把整个数字反转完，比如 1221 会变成 num=0, reversedHalf=1221，这样虽然也能判断，但有两个缺点： - 可能溢出：对于接近 int 最大值的数字，反转后可能超过 int 范围（例如 2147483647 反转后溢出）。 - 效率稍低：多反转了一半的位数（其实没必要）。
而我们的条件 while (num > reversedHalf) 恰好停在中间，避免了上述问题。
class Solution {
fun isPalindrome(x: Int): Boolean {
// 1. 负数一定不是回文数
// 因为负号放到最后就不成立了
if (x < 0) return false
// 2. 如果一个数不是 0，但最后一位是 0，也一定不是回文数
// 比如 10，反过来是 01，和 10 不一样
if (x % 10 == 0 && x != 0) return false
var num = x // 还没处理完的左半边
var rev = 0 // 已经反过来的右半边
// 3. 只要左边剩下的部分还比右边长，就继续处理
// 这表示我们还没到中间
while (num > rev) {
// 4. 取出 num 的最后一位
val lastDigit = num % 10
// 5. 把这位加到 rev 的后面
// 例如 rev=12, lastDigit=3 -> rev变成123
rev = rev * 10 + lastDigit
// 6. num 去掉最后一位
// 例如 num=1234 -> num变成123
num /= 10
}
// 7. 循环结束时：
// - 偶数位：num 和 rev 完全一样
// - 奇数位：rev 比 num 多中间那个数，要把 rev / 10 再比
return num == rev || num == rev / 10
}
}
复杂度
- 时间复杂度: O(log₁₀ n)，循环次数约为数字位数的一半。
- 空间复杂度: O(1)，只用了几个变量。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!