友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
202. 快乐数
编写一个算法来判断一个数 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
思路分析
竟然可以使用"快慢指针"，类似判断链表中是否有环的思路！妙！
快慢指针的思路，来个图就一目了然了：
除了使用快慢指针，也可以使用 Set 存已经计算过的数字。
- 一刷
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
/** * Runtime: 1 ms, faster than 99.99% of Java online submissions for Happy Number. * * Memory Usage: 33.4 MB, less than 10.60% of Java online submissions for Happy Number. * * Copy from: https://leetcode.com/problems/happy-number/discuss/56917/My-solution-in-C(-O(1)-space-and-no-magic-math-property-involved-)[My solution in C( O(1) space and no magic math property involved ) - LeetCode Discuss] * * @author D瓜哥 · https://www.diguage.com * @since 2020-01-10 21:40 */ public boolean isHappy(int n) { int slow = n; int fast = n; do { slow = digitSquareSum(slow); fast = digitSquareSum(fast); fast = digitSquareSum(fast); if (fast == 1) { return true; } } while (slow != fast); return false; } public int digitSquareSum(int n) { int sum = 0; while (n != 0) { int temp = n % 10; sum += temp * temp; n /= 10; } return sum; }
- 二刷
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
/** * @author D瓜哥 · https://www.diguage.com * @since 2025-03-06 21:56 */ public boolean isHappy(int n) { int slow = n, fast = n; do { slow = squareSum(slow); fast = squareSum(fast); fast = squareSum(fast); if (fast == 1) { return true; } } while (slow != fast); return false; } private int squareSum(int num) { int sum = 0; while (num > 0) { int n = num % 10; sum += n * n; num /= 10; } return sum; }
- 三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-09-08 19:17:10
*/
public boolean isHappy(int n) {
int slow = n, fast = n;
do {
slow = calc(slow);
fast = calc(fast);
fast = calc(fast);
if (fast == 1) {
return true;
}
} while (fast != slow);
return false;
}
private int calc(int n) {
int result = 0;
while (n != 0) {
int mod = n % 10;
result += mod * mod;
n /= 10;
}
return result;
}