0202. 快乐数 #

标签：哈希表、数学
难度：简单

题目大意 #

给定一个整数 n，判断 n 是否为快乐数。

快乐数定义：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果可以变为 1，那么这个数就是快乐数。

解题思路 #

根据题意，不断重复操作，数可能变为 1，也可能是无限循环。无限循环其实就相当于链表形成了闭环，可以用哈希表来存储为一位生成的数，每次判断该数是否存在于哈希表中。如果已经出现在哈希表里，则说明进入了无限循环，该数就不是快乐数。如果没有出现则将该数加入到哈希表中，进行下一次计算。不断重复这个过程，直到形成闭环或者变为 1 。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def getNext(self, n: int):
        total_sum = 0
        while n > 0:
            n, digit = divmod(n, 10)
            total_sum += digit ** 2
        return total_sum


    def isHappy(self, n: int) -> bool:
        num_set = set()
        while n != 1 and n not in num_set:
            num_set.add(n)
            n = self.getNext(n)
        return n == 1