LeetCode 202：快乐数

题意

判断正整数 n 是不是快乐数。

快乐数定义：

（1）每次将正整数替换为它每个位置上的数字的平方和。

（2）重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。

（3）如果可以变为 1，这个数就是快乐数。

示例

示例 1：

输入：n = 19 输出：true

解释： 12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1

示例 2：

输入：n = 2 输出：false

题目解析

重点是在“无限循环”上。

什么叫循环，循环就是出现了一遍又一遍，如果循环了那肯定就不是快乐数。

那这道题就可以转化成：【在“将正整数替换为它每个位置上的数字的平方和”过程中，新出现的正整数是否曾经出现过。】

你看，现在就很明了了，我们记录出现过的正整数，然后将新元素与之前出现过的正整数比较。

在一堆数中查找一个数，当然是祭出哈希。

碰到这种对目前来说是未知数量和未知数值大小的情况，我们可以使用集合 set 来解决。

想明白了这个，那快乐数的求解每次就可以光明正大的分为两步：

将当前数进行数位分离，求各位上平方的和。 每次生成的数，查是否在哈希集合中，在的话就不是快乐数，不在的话就添到集合里。

代码讲解

`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)