数组与哈希简单2 种解法
#202快乐数
反复把整数替换为各位数字平方和，判断序列最终是否到达 1。
#哈希表#数学#快慢指针
原题
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2：
输入：n = 2 输出：false
提示：
1 <= n <= 231 - 1
解题主线
- 状态空间有限，序列要么到达 1，要么进入不含 1 的环。
解法 1：哈希集合判环
记录已经出现的状态；遇到 1 成功，重复状态说明进入环。
-
时间复杂度： O(log n)，状态很快收敛到常数范围
-
空间复杂度： O(log n)
import java.util.HashSet;
import java.util.Set;
final class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
// 状态到达 1 则成功；重复出现则说明已进入不含 1 的环。
while (n != 1 && seen.add(n)) n = next(n);
return n == 1;
}
private int next(int number) {
int sum = 0;
// 每轮提取最低十进制位，构造唯一的后继状态。
while (number > 0) {
int digit = number % 10;
sum += digit * digit;
number /= 10;
}
return sum;
}
}实现提示
- 修复未使用输入且恒返回 true 的旧代码。
解法 2：Floyd 快慢指针
把数字变换看作链表后继函数；快指针每轮走两步，检测是否在 1 或环中相遇。
-
时间复杂度： O(log n)
-
空间复杂度： O(1)
final class Solution {
public boolean isHappy(int n) {
int slow = n;
int fast = next(n);
// 快慢指针相遇表示入环；fast 到达 1 表示进入固定点。
while (fast != 1 && slow != fast) {
slow = next(slow);
fast = next(next(fast));
}
return fast == 1;
}
private int next(int number) {
int sum = 0;
// 数位平方和是状态序列的“后继函数”。
while (number > 0) {
int digit = number % 10;
sum += digit * digit;
number /= 10;
}
return sum;
}
}边界与易错点
- 旧实现从 res=0 开始迭代，完全没有使用输入 n，并且无条件返回 true。
- 集合写法应把 n 作为首个状态；Floyd 写法需同时检测 slow == fast 与 fast == 1。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q202_isHappyNum.java