快乐数

发表于 分类于 阅读次数：

快乐数（难度：简单）

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