每日一道算法题（二）—快乐数

每日一道算法题（二）—快乐数

问题描述

判断一个数是否为快乐数。

快乐数 定义为：

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

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例

算法思路

1.快乐数的判定条件：

• 如果某个数字最终变为 1，那么它是快乐数；
• 如果出现循环，即某个数字已经出现过，但不是 1，那么它就不是快乐数。

2.如何检测循环：

• 可以使用 哈希集合（set） 来存储每次出现的平方和，若平方和再次出现，说明进入了循环，此时可以返回 False。

关键步骤：

• 初始化一个哈希集合，用来记录已经出现过的数字。
• 对给定的数字 n，不断计算其各位数字的平方和。
• 如果平方和为 1，则返回 True，表示这是一个快乐数。
• 如果平方和已经在哈希集合中出现过，返回 False，表示进入了无限循环，n 不是快乐数。

代码实现

# 我的代码：
def isHappy(n: int) -> bool:
    def get_next_number(num):
        total_sum = 0
        while num > 0:
            digit = num % 10
            total_sum += digit ** 2
            num //= 10
        return total_sum
    
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next_number(n)
    
    return n == 1

# 官方代码：
def isHappy(n: int) -> bool:
    def get_next(n):
        while(n>0):
            n,digit = divmod(n,10)
            count += digit **2
        return count

    seen = set()
    while n!=1 and n not in seen:
        seen.append(n)
        n = get_next(n)

    return n == 1

注意：

使用 set() 而不是 list 的原因主要有以下几点：

1. 查找效率不同：

• set：集合的查找时间复杂度是 O(1)，因为它是基于哈希表实现的，能在常数时间内判断一个元素是否存在于集合中。
• list：列表的查找时间复杂度是 O(n)，因为需要逐个遍历元素来判断是否存在于列表中。

在这个算法中，每次计算新的数字 n 时，都需要判断该数字是否已经出现过。使用 set 可以在常数时间内完成查找，而使用 list 则需要遍历整个列表，效率较低。

2. 不需要顺序：

• set：集合是无序的，适合用来存储唯一的元素，且不关心元素的顺序。
• list：列表是有序的，元素有先后顺序，但在这个算法中并不需要关心这些数字出现的顺序，只要能快速判断某个数字是否出现过即可。因此，set 是更合适的数据结构。

3. 去重功能：

• set：集合自动保证元素的唯一性，即不会出现重复元素。当我们尝试将一个数字添加到 set 时，如果该数字已经存在，set 不会再添加它。
• list：列表允许重复元素，若使用 list，则需要额外编写代码来确保不添加重复的数字。

4. 总结：

使用 set 比 list 更适合这个场景，更高效且简洁是因为：

1. 查找效率高：set 的查找复杂度是 O(1)，list 是 O(n)；
2. 无需顺序：我们只需要知道某个数字是否出现过，不关心顺序；
3. 去重功能：set 自动去重，避免重复计算。