DAY20: LeetCode 202 快乐数：从 Set 判重到 快慢指针

LeetCode 202 快乐数：从 Set 判重到 Floyd 快慢指针

• LeetCode 202 快乐数
• 一、怎么把数字一位一位拆出来？
• 二、普通版本：字典查平方 + Set 判重
• 三、优化一：平方没必要使用字典保存
• 四、还能继续优化吗？
• 五、优化二：Floyd 快慢指针判环
• • 为什么这样可以判断？
  • • 情况一：fast 到达 1
    • 情况二：slow 和 fast 相遇
• 六、从 Set 是怎么想到快慢指针的？
• 七、三个版本的区别

LeetCode 202 快乐数

LeetCode 202 快乐数

这道题会不断进行同一个操作：

把当前数字的每一位取出来，分别平方以后相加，得到新的数字，然后继续重复。

例如, n = 19：

19 → 1² + 9² → 82

82 → 8² + 2² → 68

68 → 6² + 8² → 100

100 → 1² → 1

最终能够得到 1，所以 19 是快乐数。

整个流程看下来, 可以想到这道题真正需要解决两个问题：

一、怎么把数字一位一位拆出来？

比如：

n = 1234

可以通过：

digit = n % 10

取得最后一位：

4

然后：

n //= 10

删除最后一位：

1234 → 123

继续：

123 → 3
12 → 2
1 → 1
0 → 停止

所以不需要提前知道 n 是几位数，只需要：

while n > 0:
digit = n % 10
total += digit * digit
n //= 10

就可以把所有位都处理完。

二、普通版本：字典查平方 + Set 判重

我最开始想到，可以提前把 0 ~ 9 的平方保存到字典里：

(因为一位数就是在这个范围里面)

nums = {}

for i in range(10):
nums[i] = i ** 2

后面得到某一位 digit 时，直接查询使用：

nums[digit]

取出对应的平方。

🚩 另一个问题是：什么时候停止？

例如非快乐数可能会出现：

2
→ 4
→ 16
→ 37
→ 58
→ 89
→ 145
→ 42
→ 20
→ 4 ← 第二次出现了
→ 16
→ …

这里 4 第二次出现以后，后面的过程就会和之前完全一样，因此已经进入了一个循环，不可能再突然得到 1。

所以可以使用一个 set 用于保存之前出现过的数字：

seen = set()

如果：

n in seen

说明当前数字已经出现过一次，也就是进入了循环，可以直接：

return False

✨ 完整代码：

class Solution:
def isHappy(self, n: int) –> bool:
nums = {}

for i in range(10):
nums[i] = i ** 2

seen = set()

while n != 1:
if n in seen:
return False

seen.add(n)

total = 0

while n > 0:
digit = n % 10
total += nums[digit]
n //= 10

n = total

return True

三、优化一：平方没必要使用字典保存

虽然字典查表可以做，但这里实际上只有 0 ~ 9 十个数字，而且计算：

digit * digit

本身非常简单。

使用字典还需要先创建字典，再进行哈希查找，所以这里直接计算反而更加自然。

于是：

total += nums[digit]

可以直接改成：

total += digit * digit

代码就简化成：

class Solution:
def isHappy(self, n: int) –> bool:
seen = set()

while n != 1:
if n in seen:
return False

seen.add(n)

total = 0

while n > 0:
digit = n % 10
total += digit * digit
n //= 10

n = total

return True

这里也可以保留 1、10、100 作为提前成功的条件。

因为：

10 → 1² + 0² → 1
100 → 1² + 0² + 0² → 1

所以当某一轮已经得到 10 或 100 时，其实已经可以确定最后一定会到 1，没必要再多进行一次拆位和平方求和。

因此可以写成：

while n != 100 and n != 10 and n != 1:

这样例如：

19
→ 82
→ 68
→ 100
→ 直接返回 True

而不是再继续计算：

100
→ 1
→ True

不过这只是一个很小的提前退出优化，主要减少的是一轮额外计算，并不会改变整体时间复杂度。

四、还能继续优化吗？

现在剩下的额外空间主要来自：

seen = set()

但重新观察 seen 的作用，会发现我们其实并不关心：

之前到底出现过哪些数字。

真正关心的只是：

当前数字有没有进入循环？

这就和之前做过的环形链表判环非常像。也就是 [ 141 ] 这道题

把每一次“各位平方和”看成从一个状态走向下一个状态：

n
→ next(n)
→ next(next(n))
→ …

快乐数：

19 → 82 → 68 → 100 → 1

非快乐数：

2 → 4 → 16 → 37 → … → 20 → 4 → 16 → …
↑ ↓
└─────────┘

这样看以后，问题已经变成：

这条不断向后的路径，最终是到达 1，还是进入一个环？

既然是在判断有没有环，就可以联想到之前环形链表使用过的：

快慢指针 / Floyd 判环。

五、优化二：Floyd 快慢指针判环

首先把“一次转换”单独写成一个函数：

def get_next(n):
total = 0

while n > 0:
digit = n % 10
total += digit * digit
n //= 10

return total

它负责：

19 → 82
82 → 68
68 → 100
100 → 1

也就是给一个当前数字，返回它的下一个数字。

接下来设置两个指针：

slow = n
fast = get_next(n)

其中：

slow → 每次进行一次转换

fast → 每次进行两次转换

也就是：

slow = get_next(slow)

fast = get_next(get_next(fast))

这和环形链表完全对应：

slow = slow.next
fast = fast.next.next

在快乐数中则变成：

slow = next(slow)
fast = next(next(fast))

只是原来的“走到下一个节点”，现在变成了“计算下一次数值”。

为什么这样可以判断？

最终只有两种情况。

情况一：fast 到达 1

例如：

19 → 82 → 68 → 100 → 1

如果：

fast == 1

说明这条路径最终能够走到 1，因此是快乐数。

情况二：slow 和 fast 相遇

如果这条路径进入循环，那么和环形链表一样：

slow 每次走一步
fast 每次走两步

两者最终一定会在环中相遇。

所以：

slow == fast

而此时又没有到 1，就说明进入了非快乐数的循环。

因此循环条件可以写成：

while fast != 1 and slow != fast:

只要：

还没到 1
并且
快慢指针还没相遇

就继续走。

🚩 完整代码：

class Solution:
def isHappy(self, n: int) –> bool:
def get_next(n):
total = 0

while n > 0:
digit = n % 10
total += digit * digit
n //= 10

return total

slow = n
fast = get_next(n)

while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))

return fast == 1

六、从 Set 是怎么想到快慢指针的？

最开始使用 set：

不断计算新的 n
↓
每出现一个 n 就保存到 seen
↓
如果以后再次出现
↓
说明进入循环

然后继续想：

我保存这些数字，真正的目的是什么？

不是为了以后使用它们的值，而只是为了判断：

有没有出现循环？

既然只是判环，就不一定需要保存所有历史状态。

于是可以把：

n → 下一个 n → 下一个 n → …

看成一条链。

然后联想到环形链表：

普通链表判环：
slow 一步
fast 两步

快乐数判环：
slow 做一次转换
fast 做两次转换

所以优化过程就是：

Set 记录所有历史状态
↓
发现真正需要的只是“是否成环”
↓
把每一个数字看成一个节点
↓
把平方和转换看成 next
↓
问题变成链表判环
↓
使用 Floyd 快慢指针
↓
不再需要 seen

七、三个版本的区别

所以这道题最后可以记住这两个核心知识点：

1. % 10 取最后一位，// 10 删除最后一位，可以处理不知道位数的整数。

2. 如果一个过程会不断从当前状态产生唯一的下一个状态，那么“状态重复”其实就是成环，这时候除了 Set 判重，还可以进一步考虑 Floyd 快慢指针判环。