大家好呀，我是快乐的蛋蛋。
今天解决快乐数，同样还是哈希表实战系列，快乐的知识又要增加了。
LeetCode 202：快乐数
题意
判断正整数 n 是不是快乐数。
快乐数定义：
（1）每次将正整数替换为它每个位置上的数字的平方和。
（2）重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
（3）如果可以变为 1，这个数就是快乐数。
示例
输入：19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
提示
- 1 <= n <= 2^31 -1
题目解析
这道快乐数，把它归为难度简单的一类题，我感觉更多的是代码层面上。
实际上这道题，乍一看很具有迷惑性，看“示例”的时候很容易把它当作一道数学题。
当你一不小心陷入这个数学题的怪圈之后，基本就走进了死胡同。
所以读题细致，也是大家在平时刷题要注意的。
这道题我是怎么知道可以用哈希解决呢？重点是在“无限循环”上。
什么叫循环，循环就是出现了一遍又一遍，如果循环了那肯定就不是快乐数。
那这道题就可以转化成：【在“将正整数替换为它每个位置上的数字的平方和”过程中，新出现的正整数是否曾经出现过。】
你看，现在就很明了了，我们记录出现过的正整数，然后将新元素与之前出现过的正整数比较。
在一堆数中查找一个数，当然是祭出哈希，毕竟是查找中的秒男，时间复杂度为 O(1)。
不过这里和之前做的【字母异位词】还不太一样，字母异位词是有限的，只有 26 个小写字母，建一个长度为 26 的数组即可。
快乐数则不行，因为对目前的我们来说不清楚会产生多少个不同的数，也不清楚每个数的值是多少。
碰到这种对目前来说是未知数量和未知数值大小的情况，我们可以使用集合 set 来解决。
想明白了这个，那快乐数的求解每次就可以光明正大的分为两步：
- 将当前数进行数位分离，求各位上平方的和。
- 每次生成的数，查是否在哈希集合中，在的话就不是快乐数，不在的话就添到集合里。
图解
以 n = 19 为例。
首先说一下如何进行数位分离，很简单：
每次用 n 对 10 取余（19 % 10 = 9），再求平方（happy_sum = 9 * 9 = 81），最后对 10 整除（n = 19 / 10 = 1）。
# 求正整数 num 每个位置上数字的平方和 def getNext(self, num): happy_sum = 0 while num: happy_sum += (num % 10) ** 2 num = num // 10 return happy_sum
下面就正式开始图解。
首先初始化一个集合，记录过程数据。
# 记录过程数据 mid = set()
第 1 步，n = 19，数位分离求平方和 1² + 9² = 82，82 不在集合中，遂添加进集合。
# 如果替换后的数再之前出现过，则说明陷入无限循环，此数不是快乐数 if n in mid: return False else: mid.add(n)
第 2 步，n = 82，数位分离求平方和 8² + 2² = 68，68 不在集合中，遂添加进集合。
第 3 步，n = 68，数位分离求平方和 6² + 8² = 100，100 不在集合中，同样添加进集合。
第 4 步，n = 100，数位分离求平方和为 1，返回 True，所以最初的 n = 19 为快乐数。
# 如果为1，则是快乐数 if n == 1: return True
可能还会有小婊贝不清楚为啥曾经出现过就肯定不是快乐数，直接举个例子吧。
以 n = 2 为例吧，我省去中间步骤，直接看下图。
这道题的时间复杂度由两部分组成：一是求每个位置上数字的平方和为 O(logn)，二是看新元素是否在集合中，单个查询的时间复杂度为 O(1)，因为总会是在有限的个数内解决掉这个问题，所以总的时间复杂度为 O(logn)。
因为额外建了一个集合 mid，所以空间复杂度为 O(logn)。
代码实现
Python 代码实现
class Solution: # 求正整数 num 每个位置上数字的平方和 def getNext(self, num): happy_sum = 0 while num: happy_sum += (num % 10) ** 2 num = num // 10 return happy_sum def isHappy(self, n: int) -> bool: # 记录过程数据 mid = set() while True: # 将当前数替换为它每个位置上的数字的平方和。 n = self.getNext(n) # 如果为1，则是快乐数 if n == 1: return True # 如果替换后的数再之前出现过，则说明陷入无限循环，此数不是快乐数 if n in mid: return False else: mid.add(n)
Java 代码实现
class Solution { private int getNextNumber(int n) { int res = 0; while (n > 0) { int temp = n % 10; res += temp * temp; n = n / 10; } return res; } public boolean isHappy(int n) { Set<Integer> record = new HashSet<>(); while (n != 1 && !record.contains(n)) { record.add(n); n = getNextNumber(n); } return n == 1; } }
