难度: Easy
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2：
输入：n = 2 输出：false
提示：
1 <= n <= 231 - 1运行时间: 19 ms
内存: 16.1 MB
class Solution:
def isHappy(self, n: int) -> bool:
record = []
record.append(n)
while 1:
n = self.getSum(n)
if n == 1:
return True
if n in record:
return False
else:
record.append(n)
def getSum(self, n: int) -> int:
new_sum = 0
while n:
r = n % 10
new_sum += r*r
n = n // 10
return new_sum
该题解的思路是利用哈希集合检测循环。从给定的整数 n 开始，不断计算每一位上的平方和替换 n，直到 n 为 1 或者出现了之前计算过的 n，表示进入了循环。如果最后 n 等于 1，则是快乐数，否则不是。
时间复杂度: O(logn * loglogn)
空间复杂度: O(logn)
class Solution:
def isHappy(self, n: int) -> bool:
record = [] # 使用列表记录出现过的数字
record.append(n)
while 1:
n = self.getSum(n)
if n == 1:
return True
if n in record: # 如果新数已经在列表中，说明陷入循环，不是快乐数
return False
else:
record.append(n)
def getSum(self, n: int) -> int:
new_sum = 0
while n:
r = n % 10 # 取出 n 的最后一位
new_sum += r*r # 计入平方和
n = n // 10 # 去掉 n 的最后一位
return new_sum
使用列表来记录数字确实能工作，但查找效率相对较低，因为列表的查找时间是线性的。在这种情况下，使用哈希集合（例如 Python 中的 set）会更合适，因为哈希集合的平均查找时间为常数时间 O(1)，这能显著提高算法的效率，尤其是当数字的范围较大或者循环链较长时。因此，替换列表为哈希集合是一个优化算法性能的好选择。
根据快乐数的定义，如果数字 n 不是快乐数，那么计算过程中生成的数字会开始重复，形成一个循环。这是因为整数的平方和的计算会最终达到一个有限的数值范围内。如果未达到 1 而开始循环，这表明我们已经遇到了之前计算过的数字，因此算法检查数字是否已在记录中出现，就可以判断是否进入了循环。一旦检测到循环，算法将停止并返回 false。这样，算法要么找到快乐数 1 并返回 true，要么发现循环并返回 false，因此算法总会停止。
函数 `getSum` 中的除以 10 和取余操作用来分离出数字的每一位，并计算其平方和。这种方法不受数字大小的影响，对于非常大的数字同样有效。整数操作在计算机中是基本操作，可以处理任何大小的整数，只要它们在计算机内存和数据类型的表示范围内。在 Python 中，整数类型具有自动的大小扩展，可以处理非常大的数字而不会溢出。因此，这些操作对于任何大小的整数都是安全且有效的。