快乐数——哈希表
编写一个算法来判断一个数n是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
- 如果这个过程结果为1，那么这个数就是快乐数。
如果n是快乐数就返回true；不是，则返回false。
思路：不容易判断的点在于无限循环的情况。
数字平方和一定会让数变小
设一个数有 k 位，那么它的最大值是：10^k - 1。
它的各位数字最大是 9。每位平方最大是 81。
所以 k 位数的平方和最大是：81 * k。
而 k 位数本身至少是：10^(k-1)
比较：
| 位数 | 最小 k 位数 | 数位平方和最大值 |
|---|---|---|
| 3 | 100 | 81 * 3 = 243 |
| 4 | 1000 | 81 * 4 = 324 |
| 5 | 10000 | 81 * 5 = 405 |
你会发现：
从 4 位数开始，下一步一定会掉到 324 以下。
从这开始，无论你多大，最终都会掉进一个固定的小范围内。
✔ 情况 A：最终变成 1（快乐）
✔ 情况 B：在某处形成循环（不快乐）
所以无限循环，也就是非快乐数，必然意味着某个数重复出现。
class Solution: def isHappy(self, n: int) -> bool: s=set() while True: n=self.getSum(n) if n==1: return True else: if n in s: return False s.add(n) def getSum(self,n): sum = 0 while n: sum+=(n%10)**2 n//=10 return sum print(Solution().isHappy(19))