202. 快乐数
题目描述
对一个正整数反复做如下操作：把它换成各位数字的平方和。
如果某一时刻得到 1，就称最初的数为快乐数。如果过程陷入一个不含 1 的循环，永远到不了 1，它就不是快乐数。
输入正整数 n，是快乐数返回 true，否则返回 false。
输入：n = 19 输出：true
解释：19 → 82 → 68 → 100 → 1，最终得到 1。
输入：n = 2 输出：false
解释：2 进入一个不含 1 的循环，永远得不到 1。
数据范围
1 <= n <= 2^31 - 1
解题思路：快慢指针
把“求各位平方和”看成一条链表的 next 指针：n → nxt(n) → nxt(nxt(n)) → …。一个不超过 10 位的数，平方和至多 810，所以这条链很快进入一个有限范围，最终要么到达 1（1 的下一个还是 1），要么进入一个不含 1 的环。这就是链表判环：慢指针每次走一步，快指针每次走两步。快指针先碰到 1 就是快乐数；快慢指针在非 1 处相遇，说明有不含 1 的环。无需哈希集合记录访问过的数。
为什么正确
第 k 轮结束时，slow 是序列的第 k 项，fast 是第 2k+1 项；快指针始终在前面，且在环上每轮与慢指针的距离缩短 1。
复杂度分析
时间 O(log n)：第一步之后数字不超过 810，尾巴和环都很短；额外空间 O(1)。
易错点
快指针要从 nxt(n) 开始，否则 slow == fast 一开始就成立；结束后要判断 fast == 1 而不是 slow == fast，因为到达 1 后两者也可能都等于 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isHappy(self, n: int) -> bool:
def nxt(x):
total = 0
while x > 0:
x, d = divmod(x, 10)
total += d * d
return total
slow, fast = n, nxt(n)
while fast != 1 and slow != fast:
slow = nxt(slow)
fast = nxt(nxt(fast))
return fast == 1class Solution {
int nxt(int x) {
int total = 0;
while (x > 0) {
int d = x % 10; x /= 10;
total += d * d;
}
return total;
}
public boolean isHappy(int n) {
int slow = n, fast = nxt(n);
while (fast != 1 && slow != fast) {
slow = nxt(slow);
fast = nxt(nxt(fast));
}
return fast == 1;
}
}class Solution {
public:
int nxt(int x) {
int total = 0;
while (x > 0) {
int d = x % 10; x /= 10;
total += d * d;
}
return total;
}
bool isHappy(int n) {
int slow = n, fast = nxt(n);
while (fast != 1 && slow != fast) {
slow = nxt(slow);
fast = nxt(nxt(fast));
}
return fast == 1;
}
};func nxt(x int) int {
total := 0
for x > 0 {
d := x % 10; x /= 10
total += d * d
}
return total
}
func isHappy(n int) bool {
slow, fast := n, nxt(n)
for fast != 1 && slow != fast {
slow = nxt(slow)
fast = nxt(nxt(fast))
}
return fast == 1
}var isHappy = function(n) {
const nxt = x => {
let total = 0;
while (x > 0) {
const d = x % 10; x = Math.floor(x / 10);
total += d * d;
}
return total;
};
let slow = n, fast = nxt(n);
while (fast !== 1 && slow !== fast) {
slow = nxt(slow);
fast = nxt(nxt(fast));
}
return fast === 1;
};function isHappy(n: number): boolean {
const nxt = (x: number): number => {
let total = 0;
while (x > 0) {
const d = x % 10; x = Math.floor(x / 10);
total += d * d;
}
return total;
};
let slow = n, fast = nxt(n);
while (fast !== 1 && slow !== fast) {
slow = nxt(slow);
fast = nxt(nxt(fast));
}
return fast === 1;
}其他解法
两种解法都把反复计算看成一条可能有环的链。哈希集合靠记录访问过的结点来发现环；快慢指针靠两个指针相遇来发现环，省掉了集合。
解法 2：哈希集合检测循环 时间 O(log n)，空间 O(log n)
不断用“各位数字平方和”更新 n，并把出现过的数字记进哈希集合。得到 1 就是快乐数；如果得到的数字已经在集合里，说明进入了不包含 1 的循环，返回 false。
思路最直接，容易想到。需要额外空间保存已经出现过的数字。
class Solution:
def isHappy(self, n: int) -> bool:
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = sum(int(d) ** 2 for d in str(n))
return n == 1class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
int total = 0;
while (n > 0) {
int d = n % 10;
total += d * d;
n /= 10;
}
n = total;
}
return n == 1;
}
}class Solution {
public:
bool isHappy(int n) {
unordered_set<int> seen;
while (n != 1 && !seen.count(n)) {
seen.insert(n);
int total = 0;
while (n > 0) {
int d = n % 10;
total += d * d;
n /= 10;
}
n = total;
}
return n == 1;
}
};func isHappy(n int) bool {
seen := map[int]bool{}
for n != 1 && !seen[n] {
seen[n] = true
total := 0
for n > 0 {
d := n % 10
total += d * d
n /= 10
}
n = total
}
return n == 1
}var isHappy = function(n) {
const seen = new Set();
while (n !== 1 && !seen.has(n)) {
seen.add(n);
let total = 0;
while (n > 0) {
const d = n % 10;
total += d * d;
n = Math.floor(n / 10);
}
n = total;
}
return n === 1;
};function isHappy(n: number): boolean {
const seen = new Set<number>();
while (n !== 1 && !seen.has(n)) {
seen.add(n);
let total = 0;
while (n > 0) {
const d = n % 10;
total += d * d;
n = Math.floor(n / 10);
}
n = total;
}
return n === 1;
};