编写一个算法来判断一个数 n 是不是快乐数。

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

如果 n 是快乐数就返回 True ;不是,则返回 False 。

思路

  1. 数字转字符列表依次计算平方的和
  2. 检查是不是在已知的非快乐数中,是则继续计算;不是且不为1,那就是新的非快乐数,记录并返回False;都不是则它是未知的快乐数,记录并返回True
  3. 平方和部分用字典预存储0-9的平方结果
class Solution:
    def isHappy(self, n: int) -> bool:
        stock = {
            "0" : 0,
            "1" : 1,
            "2" : 4,
            "3" : 9,
            "4" : 16,
            "5" : 25,
            "6" : 36,
            "7" : 49,
            "8" : 64,
            "9" : 81,
        }
        self.happy_stack = [0, 1]
        self.non_happy_stack = []

        def check(n):
            if n in self.happy_stack:
                return True
            _sum = sum([stock[num] for num in str(n)])
            if _sum in self.non_happy_stack:
                return False
            elif _sum != 1:
                self.non_happy_stack.append(_sum)
                return check(_sum)
            else:
                self.happy_stack.append(_sum)
                return True
        return check(n)

数字各位平方和

不知道这样会不会快一点

def get_sum(n):
    _sum = 0
    while n > 0:
        _sum += (n % 10) ** 2
        n = int(n / 10)
    return _sum

标签: LeetCode

添加新评论