快乐数

快乐数(难度:简单)

2

方法一:使用“快慢指针”思想找出循环

“快指针”每次走两步,“慢指针”每次走一步,当二者相等时,即为一个循环周期。此时,判断是不是因为1引起的循环,是的话就是快乐数,否则不是快乐数。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public boolean isHappy(int n) {
int slow = n;
int fast = n;
do{
slow = helper(slow);
fast = helper(fast);
fast = helper(fast);
} while(slow != fast);
return slow == 1;
}

public int helper(int n){
int sum = 0;
while(n>0){
int re = n%10;
sum += re*re;
n = n/10;
}
return sum;
}
}
1

方法二:递归

  • 不是快乐数的数称为不快乐数(unhappy number),所有不快乐数的数位平方和计算,最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中
  • 已知规律: [1 ~ 4] 中只有 1 是快乐数,[5 ~ ∞] 的数字要么回归到 1 要么回归到 4 或 3
  • 因此仅需在 n > 4 时调用递归
代码
1
2
3
class Solution:
def isHappy(self, n: int) -> bool:
return self.isHappy(sum(int(i) ** 2 for i in str(n))) if n > 4 else n == 1
3