目标
编写一个算法来判断一个数 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 <= 2^31 - 1
思路
难点是如何确定停止条件，我甚至想过记录循环次数如果超过某一个数就返回false。我意识到这可能是一个数学问题，就放弃了。
看了题解才明白，问题看似是开放的，但也是有规律的，关键是如何分析这个问题。
考虑最终可能出现的情况：
- 最终会得到 1。
- 最终会进入循环。
- 值会越来越大，最后接近无穷大。
考虑不同位数数字的最大值，进行一次计算的结果：
| 位数 | 最大值 | 下一个值 |
|---|---|---|
| 1 | 9 | 81 |
| 2 | 99 | 162 |
| 3 | 999 | 243 |
| 4 | 9999 | 324 |
| 13 | 9999999999999 | 81*13=1053 |
相应位上小于最大值的数字，其下一个值也必定小于最大值的下一个值。
意识到存在循环是很重要的，然后我们可以使用哈希表记录出现过的元素，也可以使用弗洛伊德循环检测算法（Floyd's Cycle-Finding Algorithm）又称为龟兔赛跑算法（Tortoise and Hare Algorithm），注意不是图论中求最短路径的弗洛伊德算法。
// todo 自己实现一下
代码
/**
* @date 2024-06-15 20:59
*/
public class IsHappy202 {
/**
* 快慢指针，也是用来检测链表中是否存在环
* 快慢如果相遇就说明存在环，否则快的先遇到1
*/
class Solution_v1 {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
/**
* Set记录每次的数字，如果重复就返回false
*/
class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
/**
* 实际上只会存在一个循环4→16→37→58→89→145→42→20→4
*/
private static Set<Integer> cycleMembers =
new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
while (n != 1 && !cycleMembers.contains(n)) {
n = getNext(n);
}
return n == 1;
}
}
性能
略