LeetCode面试系列 第4天:No.202 - 快乐数

或许你不知道的是,Leetcode 中是有很多 数学题 的,本文要解析的题 快乐数 就是其中到一个典型问题,本题将基于数据结构 set 来求解。

Leetcode

今天要给大家分析的面试题是 LeetCode 上第 202 号问题,

LeetCode - 202. 快乐数

https://leetcode-cn.com/problems/happy-number/

题目描述

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

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

示例:

1
2
输入: 19
输出: true

解释:

12 + 92 = 82

82 + 22 = 68

62 + 82 = 100

12 + 02 + 02 = 1


解题思路:

中学数学中我们学到一个概念集合(英文是 set),集合的最大特点是元素不能重复。Python中,set 是一组 key 的集合。

于是可以使用迭代法和 set 这种数据结构来求解此题。

具体操作为: 迭代地求给定数的各位数字的平方和,维护一个 set,迭代循环的出口是平方和为1或已在 set 中出现过。

AC的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isHappy(self, n: int) -> bool:
        unhappy = set()
        while n not in unhappy and n != 1:
            unhappy.add(n)
            n = self.GetSquareSum(n)
        return n == 1    

    def GetSquareSum(self, n: int) -> bool:
        sum0 = 0
        while n > 0:
            r = n - int(n/10)*10
            n = int(n/10)
            sum0 += r * r
        return sum0

运行结果:

执行用时 : 36 ms, 在所有 Python3 提交中击败了99.72%的用户.

相应的,如需测试,本地可执行的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isHappy(self, n: int) -> bool:
        unhappy = set()
        while n not in unhappy and n != 1:
            unhappy.add(n)
            n = self.GetSquareSum(n)
        return n == 1    

    def GetSquareSum(self, n: int) -> bool:
        sum0 = 0
        while n > 0:
            r = n - int(n/10)*10
            n = int(n/10)
            sum0 += r * r
        return sum0

sol = Solution()
print(sol.isHappy(19))


示例代码: https://github.com/JustDoPython/leetcode-python/tree/master/leetcode-202

Python Geek Tech wechat
欢迎订阅 Python 技术,这里分享关于 Python 的一切。