算法：回文数

发表于 分类于 Disqus：

题目

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

示例 1：

1
2
输入：x = 121
输出：true

示例 2：

1
2
3
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

1
2
3
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

  • -231 <= x <= 231 - 1

**进阶：**你能不将整数转为字符串来解决这个问题吗？

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isPalindrome(_ x: Int) -> Bool {
  if x < 0 || (x != 0 && x % 10 == 0) {
    return false
  }
  
  var p = x
  var n = 0
  while p > n {
    n = n * 10 + p % 10
    p /= 10
  }
  
  return n == p || n / 10 == p
}

我们来详细分析一下这个算法的每个步骤：

1. 排除负数和尾部为零的情况

1
2
3
if x < 0 || (x != 0 && x % 10 == 0) {
  return false
}

  • 负数不能是回文数，因为负号只会出现在数字的前面，不可能出现在数字的后面。

  • 如果数字以 0 结尾，且数字不为 0 本身，那么它也不能是回文数。例如，10 和 100 等数字就不能是回文数，因为它们反过来就不会是有效的数字。

因此，首先排除负数和尾部为零的非零数字。

2. 初始化变量

1
2
var p = x
var n = 0

  • p 是我们用来操作输入数字的变量，初始值为 x。

  • n 是我们用来构建数字反转部分的变量，初始值为 0。

3. 反转数字的后半部分

1
2
3
4
while p > n {
  n = n * 10 + p % 10
  p /= 10
}

  • 这里使用 while p > n 作为条件，表示我们会反转数字的后半部分直到它大于或等于数字的前半部分。这个操作的目的是让 n 变成数字 x 的后半部分的反转，而 p 逐渐变成前半部分。

  • 在每次迭代中：

    • n = n * 10 + p % 10：把 p 的最后一位数字加到 n 的末尾，构建反转后的数字 n。

    • p /= 10：将 p 向右移一位，即去掉 p 的最后一位。

通过这个过程，n 将逐渐成为 x 的后半部分的反转，p 将逐渐成为 x 的前半部分。

4. 判断回文条件

1
return n == p || n / 10 == p

  • 一旦 p 小于或等于 n，表示我们已经处理完了数字的一半。此时有两个情况：

    • 如果 n == p，表示前半部分和后半部分完全相等，数字是回文数。

    • 如果 n / 10 == p，表示 n 有一个额外的数字（例如奇数位的中间数字），通过去掉这个多余的数字（即 n / 10），我们得到的值与 p 相等，数字仍然是回文数。

举个例子：

  • 对于 121：

    • 首先 n 会变成 12，p 变成 1，然后退出循环。

    • 此时 n / 10 等于 1，p 也是 1，所以返回 true。

  • 对于 123：

    • 首先 n 会变成 32，p 变成 1，然后退出循环。

    • n / 10 等于 3，p 是 1，结果是 false。

总结：

  • 这个算法通过反转数字的后半部分来判断数字是否为回文。我们只需要将数字的一半反转，然后比较两部分是否相等。

  • 时间复杂度：O(log₁₀(x))，因为我们每次都在处理 x 的一位数字，直到处理到一半。

  • 空间复杂度：O(1)，只用了常量空间。