友情支持
如果您觉得这个笔记对您有所帮助,看在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 <= 2
31
-1
思路分析
竟然可以使用"双指针",类似判断链表中是否有环的思路!妙!
双指针的思路,来个图就一目了然了:

-
一刷
-
二刷
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
28
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-10 21:40
*/
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;
}