问题描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

示例 2：
输入：n = 2
输出：false

约束条件：

  • 1 <= n <= 2^31 - 1

解题思路

判断一个数是否为"快乐数"的核心在于检测在转换过程中是否会出现循环。如果数字最终变为 1，那么它是快乐数。如果进入一个不包含 1 的循环，那么它就不是快乐数。

这个问题可以巧妙地使用快慢指针（Floyd 循环查找算法）来解决，这种方法常用于判断链表等序列中是否存在环。

  1. 我们定义一个辅助函数 calculateHappy(num)，用于计算一个数各位数字的平方和。
  2. 在主函数 isHappy(n) 中，我们初始化两个指针：
    • low（慢指针）：每次通过 calculateHappy 转换一次。
    • fast（快指针）：每次通过 calculateHappy 转换两次。
  3. 我们不断迭代这个转换过程：
    • low = calculateHappy(low)
    • fast = calculateHappy(calculateHappy(fast))
  4. 如果 fast 指针追上了 low 指针（即 low == fast），这意味着我们进入了一个循环。
  5. 循环结束时，如果相遇点的值是 1，则原始数 n 是快乐数；否则，它不是快乐数。

为什么快慢指针能检测循环？

  • 如果序列中没有循环（理论上对于快乐数问题，它总会进入循环或到达1），快指针将永远领先于慢指针。
  • 如果序列中有循环，慢指针进入循环后，快指针最终会在循环内追上慢指针。想象一下在操场跑圈，跑得快的人总会追上跑得慢的人。

实现细节

calculateHappy(num int) 函数

这个函数负责计算给定数字 num 的各位数字的平方和。

  • 它通过一个循环来处理数字的每一位：
    • digit := num % 10 获取最低位的数字。
    • res += digit * digit 将该数字的平方累加到结果 res 中。
    • num /= 10 移除最低位的数字。
  • 循环直到 num 变为 0，此时所有位都已处理完毕。

isHappy(n int) 函数

  • 初始化慢指针 low 为原始数 n。
  • 初始化快指针 fast 为 calculateHappy(n)（即走了一步）。
  • 进入主循环，条件是 low != fast。
    • 在循环内部，慢指针走一步：low = calculateHappy(low)。
    • 快指针走两步：fast = calculateHappy(calculateHappy(fast))。
  • 当 low == fast 时，循环终止。此时，它们相遇在某个点上。
  • 返回 fast == 1（或 low == 1），判断相遇点是否为 1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package main

// @lc app=leetcode.cn id=202 lang=golang
//
// [202] 快乐数
//

// @lc code=start
func isHappy(n int) bool {
	// 使用快慢指针判断是否会陷入循环
	// 慢指针每次走一步
	low := n
	// 快指针每次走两步，初始走一步
	fast := calculateHappy(n)

	// 当快慢指针相遇时，退出循环
	// 如果 n 本身是 1，calculateHappy(1) 是 1，low 和 fast 初始就可能相等，但需要先判断
    // 如果 n=1, low=1, fast=calculateHappy(1)=1. 循环不进入，直接返回 fast==1 (true).
    // 如果 n 不是 1, 但 calculateHappy(n) = n (例如 n=7, calculateHappy(7)=49, calculateHappy(49)=97...), 不会立即陷入.
	for low != fast {
		low = calculateHappy(low)
		fast = calculateHappy(calculateHappy(fast)) // 快指针再走两步
	}
	// 如果相遇点是 1，则是快乐数；否则不是
	return fast == 1
}

// calculateHappy 计算一个数各位数字平方和
func calculateHappy(num int) int {
	res := 0
	for num != 0 {
		digit := num % 10
		res += digit * digit
		num /= 10
	}
	return res
}

// @lc code=end

复杂度分析

  • 时间复杂度：(O(\log n))

    • calculateHappy(m) 函数的复杂度与数字 m 的位数相关，即 (O(\log m))。
    • 对于一个数 n，经过 calculateHappy 转换后，其值会显著减小。例如，对于一个 d 位数，其最大可能的平方和是 (d \times 9^2)。
      • 如果 n = 999 (3位数), (3 \times 9^2 = 3 \times 81 = 243).
      • 如果 n = 1999999999 (10位数, 约 (2 \times 10^9)), 最大平方和 (1^2 + 9 \times 9^2 = 1 + 729 = 730).
      • 对于 (2^{31}-1) (最大约 (2.1 \times 10^9)), 也是10位数，最大平方和类似，不会超过几百。
    • 这意味着无论初始的 n 有多大，经过少数几步转换后，数值会落入一个较小的范围内（例如，小于几百）。
    • 一旦数值进入这个小范围，后续的转换序列和任何可能的循环都将在这个有限的数字集合中发生。Floyd 算法检测到循环或达到 1 的迭代次数是有限的，可以视为一个常数 (C)。
    • 因此，总的时间复杂度主要由初始几次对较大数 n 进行 calculateHappy 转换所主导，即 (O(\log n))。

  • 空间复杂度：(O(1))

    • 我们只使用了 low 和 fast 两个变量来存储中间值，不随输入 n 的大小而改变。

关键收获

  • 循环检测：快乐数问题本质上是一个序列中的循环检测问题。
  • 快慢指针 (Floyd 算法)：这是一种非常经典且高效的循环检测算法，空间复杂度为 (O(1))。
  • 状态收敛：理解数字经过"各位平方和"转换后会迅速减小并进入一个有限的状态空间，是理解算法有效性的关键。
  • 辅助函数：将核心计算（如 calculateHappy）封装在辅助函数中可以使主逻辑更清晰。