快乐数(难度:简单)
方法一:使用“快慢指针”思想找出循环
“快指针”每次走两步,“慢指针”每次走一步,当二者相等时,即为一个循环周期。此时,判断是不是因为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; } }
|
方法二:递归
- 不是快乐数的数称为不快乐数(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
|