041 · Happy Number

algorithm

Published

June 22, 2026

My First Thoughts

这道题应该更偏向算法题，而不是数学，核心还是循环和计算，数学思维好像并没有那么多

题目说得很直接：每一轮都把当前数字变成“每一位数字的平方和”。所以核心操作应该就是拆数字：

n % 10

可以拿到当前数字的最后一位。然后再用：

n = n // 10

把最后一位去掉。这样一直循环，直到当前数字被拆完。

比如 19：

1^2 + 9^2 = 82

这里数字原来的顺序其实不重要。640 和 064 拆出来以后，平方和都是：

6^2 + 4^2 + 0^2

所以第一步可以先写出“算下一轮数字”的部分：

total = 0

while n != 0:
    remainder = n % 10
    n = n // 10
    total += remainder ** 2

这段代码算完以后，total 就是下一轮要继续判断的新数字。

然后自然会想到：

if total != 1:
    happynumber(total)
else:
    return True

也就是说，如果还没到 1，就继续对 total 做同样的事情。

但这里马上会遇到一个问题：什么时候返回 False？

因为有些数字可能一直算下去，但永远不会变成 1。如果只是不断递归或者不断循环，就没有停下来的条件。

最先想到的就是：如果某个数字已经出现过了，那后面一定会重复同一段过程。因为同一个数字的“各位数字平方和”永远是固定的。

所以可以用一个 seen 记录见过的数字：

seen = set()

每次算出一个新数字以后，就看看它是不是已经出现过：

if total in seen:
    return False

如果没出现过，就继续走下去。这里用 set 比 list 更适合，因为我们反复要问“这个数字以前见过没有”，set 做这种存在性检查更直接。

这个方向应该就很接近正解了。剩下要整理的是：不要让 seen 在每次递归里重新创建，也不要丢掉递归返回值。更简单的方式是不用递归，直接用一个循环表达“不断转换当前数字”。

Why That Is Not Enough

原来的想法里，最关键的洞察是对的：

如果一个数字重复出现，后面就会进入循环；如果这个循环里没有 1，答案就是 False。

真正需要修正的是控制流程。

如果写成递归，容易出现两个问题。

第一，seen 必须一直保存之前见过的数字。如果在递归函数里面每次都写：

seen = set()

那每一层都会重新创建一个空集合，之前见过的数字就丢了。这样就检测不到循环。

第二，如果递归调用写成：

happynumber(total)

但前面没有 return，那么里面算出来的 True 或 False 不会传回外层。

当然递归也能写对，比如把 seen 当参数传下去，或者写一个内部 helper。但这道题本质上是在重复同一件事：

当前 n -> 下一个 n -> 再下一个 n

所以用 while 循环会更自然。循环里只需要维护两个状态：

当前正在判断的 n
已经见过的数字 seen

Final Idea

从原来的拆位思路出发，保留两个核心动作：

把当前数字 n 转成各位数字的平方和
用 seen 判断当前数字是否已经出现过

循环条件可以写成：

while n != 1:

只要 n 还不是 1，就说明还没证明它是快乐数，需要继续转换。

每一轮先检查：

if n in seen:
    return False

如果当前 n 已经见过，那从这里开始后面会重复之前的过程，不可能突然变成新的结果。所以可以直接返回 False。

如果没见过，就把它加入 seen：

seen.add(n)

然后计算下一轮的数字：

total = 0

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

n = total

这里最后的：

n = total

就是把“下一轮数字”放回 n，让外层循环继续判断。

如果循环能结束，说明 n == 1，直接返回 True。

Why It Works

每个正整数经过一次转换后，都会得到一个确定的新数字。

也就是说，对于同一个 n，它的下一步永远相同：

n -> 各位数字平方和

所以整个过程只有两种可能：

某一轮变成 1
某一轮回到以前见过的数字，进入循环

如果变成 1，根据题目定义，它就是快乐数。

如果遇到以前见过的数字，比如：

2 -> ... -> 4 -> ... -> 2

那么从第二次出现 2 开始，后面的过程会和第一次出现 2 时完全一样。这个过程已经绕成了环。如果在重复之前没有遇到 1，后面也不会再遇到 1。

因此，用 seen 保存已经处理过的数字，就可以安全地判断什么时候该返回 False。

Code

def isHappy(n):
    seen = set()

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

        seen.add(n)

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

        n = total

    return True

也可以把“算各位数字平方和”单独拆成一个小函数：

def get_next(n):
    total = 0

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

    return total


def isHappy(n):
    seen = set()

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

        seen.add(n)
        n = get_next(n)

    return True

第二种写法把“怎么计算下一轮”和“什么时候停下来”分开了，读起来更清楚。

Complexity

Time	\(O(k \cdot d)\) - `k` 是转换的轮数，`d` 是每轮数字的位数；每一轮都要拆开当前数字的每一位
Space	\(O(k)\) - `seen` 保存已经出现过的数字

Takeaway

遇到“不断重复某个转换过程”的题目，除了想清楚每一步怎么计算，还要问：什么时候能确定失败？如果状态重复出现，后面的过程也会重复，这时可以用 seen 记录状态，把无限过程变成可终止的判断。

← Quiz