快乐数 图解题解
这道题到底在问什么
- 输入
- n = 19
- 输出
- true（19→82→68→100→1）
最优解：一步一步想明白
- 3记住两件事：① 反复求数位平方和往下走；② 用 seen 记住走过的数，撞见重复就是死循环。下面先演一个快乐的，再演一个不快乐的。
- 4先看一个快乐的例子：从 7 开始。下面这串是它将要走过的链，seen 集合现在还是空的。
- 5指针停在 7。先在 seen 里查 7——没见过，把它记进 seen，接着算它的各数位平方和。
- 6算 7 的数位平方和：7² = 49 = 49。下一个数是 49，指针往后挪一格继续。
- 7指针停在 49。先在 seen 里查 49——没见过，把它记进 seen，接着算它的各数位平方和。
- 8算 49 的数位平方和：4² + 9² = 16 + 81 = 97。下一个数是 97，指针往后挪一格继续。
- 9指针停在 97。先在 seen 里查 97——没见过，把它记进 seen，接着算它的各数位平方和。
- 10算 97 的数位平方和：9² + 7² = 81 + 49 = 130。下一个数是 130，指针往后挪一格继续。
- 11指针停在 130。先在 seen 里查 130——没见过，把它记进 seen，接着算它的各数位平方和。
- 12算 130 的数位平方和：1² + 3² + 0² = 1 + 9 + 0 = 10。下一个数是 10，指针往后挪一格继续。
- 13指针停在 10。先在 seen 里查 10——没见过，把它记进 seen，接着算它的各数位平方和。
- 14算 10 的数位平方和：1² + 0² = 1 + 0 = 1。下一个数是 1，指针往后挪一格继续。
- 15链一路走到了 1。到 1 就停下，7 是快乐数，返回 true。
- 16再看一个不快乐的例子：从 2 开始。这串链最后会绕回一个见过的数——那就是死循环的信号。
- 17指针停在 2。seen 里没有 2，把它记进去，再算它的各数位平方和。
- 18算 2 的数位平方和：2² = 4 = 4。下一个数是 4，继续往后走。
- 19指针停在 4。seen 里没有 4，把它记进去，再算它的各数位平方和。
- 20算 4 的数位平方和：4² = 16 = 16。下一个数是 16，继续往后走。
- 21指针停在 16。seen 里没有 16，把它记进去，再算它的各数位平方和。
- 22算 16 的数位平方和：1² + 6² = 1 + 36 = 37。下一个数是 37，继续往后走。
- 23指针停在 37。seen 里没有 37，把它记进去，再算它的各数位平方和。
- 24算 37 的数位平方和：3² + 7² = 9 + 49 = 58。下一个数是 58，继续往后走。
- 25指针停在 58。seen 里没有 58，把它记进去，再算它的各数位平方和。
- 26算 58 的数位平方和：5² + 8² = 25 + 64 = 89。下一个数是 89，继续往后走。
- 27指针停在 89。seen 里没有 89，把它记进去，再算它的各数位平方和。
- 28算 89 的数位平方和：8² + 9² = 64 + 81 = 145。下一个数是 145，继续往后走。
- 29指针停在 145。seen 里没有 145，把它记进去，再算它的各数位平方和。
- 30算 145 的数位平方和：1² + 4² + 5² = 1 + 16 + 25 = 42。下一个数是 42，继续往后走。
- 31指针停在 42。seen 里没有 42，把它记进去，再算它的各数位平方和。
- 32算 42 的数位平方和：4² + 2² = 16 + 4 = 20。下一个数是 20，继续往后走。
- 33指针停在 20。seen 里没有 20，把它记进去，再算它的各数位平方和。
- 34算 20 的数位平方和：2² + 0² = 4 + 0 = 4。下一个数是 4，继续往后走。
- 35轮到 4 时先查 seen——4 早就记过了（绿色那格）！这说明从这里开始会无限绕圈，永远到不了 1，2 不是快乐数，返回 false。
⚠️ 容易写错的地方
✗ 错：不记 seen，直接 while n != 1 死循环
✓ 对：用 seen 记住走过的数，撞重复就停
不快乐的数会无限绕圈，没有 seen 兜底程序就卡死
✗ 错：把数位平方和写成「数位之和」
✓ 对：是每个数位的平方再相加（d²）
少了平方，整个变换就错了，得到的链和题意不符
✗ 错：循环结束后忘了判断 n 是否等于 1
✓ 对：出循环再 return n == 1
循环可能因「到 1」或「撞循环」两种原因结束，必须靠 n==1 区分快乐与否
完整代码（Python / C++ / Java）
Python
def isHappy(n):
seen = set() # 记录见过的数
while n != 1 and n not in seen: # 没到 1 且没循环就继续
seen.add(n)
n = sum(int(d)**2 for d in str(n)) # 各数位平方和
return n == 1 # 停在 1 = 快乐数C++
int next(int n){ int s=0; while(n){int d=n%10; s+=d*d; n/=10;} return s; }
bool isHappy(int n){
unordered_set<int> seen;
while(n!=1 && !seen.count(n)){
seen.insert(n);
n = next(n);
}
return n==1;
}Java
int next(int n){ int s=0; while(n>0){int d=n%10; s+=d*d; n/=10;} return s; }
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = next(n);
}
return n == 1;
}复杂度
时间
O(log n)
几步内数就缩到三位数以内，之后路径长度有上界，整体接近常数级
空间
O(log n)
seen 集合最多存下路径上出现过的那些数，数量有限
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 快乐数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么需要 seen 集合，去掉行不行？+
不行。快乐数会走到 1 自然停下，但不快乐的数会陷入一个固定的循环（比如 4→16→37→58→89→145→42→20→4…），没有 seen 记录、靠 while n!=1 会永远跑下去。seen 就是用来认出「这个数第二次出现了」从而判定循环。
除了 seen 集合，还有别的判循环方法吗？+
有。可以用快慢指针（Floyd 判圈）：一个指针每次走一步、一个每次走两步，两者相遇说明有环、且环里不含 1 就返回 false。它把空间从 O(log n) 降到 O(1)，思路和判断链表是否有环一样。
所有不快乐的数最后都会进同一个循环吗？+
是的。除了快乐数，其余正整数最终都会落进同一个循环：4→16→37→58→89→145→42→20→4。所以有些写法干脆直接判断「是否落到 4」来代替 seen 集合。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 快乐数 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。