或许你不知道的是，Leetcode 中是有很多 数学题 的，本文要解析的题 快乐数 就是其中到一个典型问题，本题将基于数据结构 set 来求解。
今天要给大家分析的面试题是 LeetCode 上第 202 号问题，
LeetCode - 202. 快乐数
https://leetcode-cn测试数据/problems/happy-number/
题目描述编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例:
输入:?19输出:?true
解释:
贡献者: LeetCode
题目难度: Easy
相关话题
相关话题
哈希表
https://leetcode-cn测试数据/tag/hash-table/
数学
https://leetcode-cn测试数据/tag/math
相似题目
各位相加
https://leetcode-cn测试数据/problems/add-digits/ ?难度: 简单
丑数
https://leetcode-cn测试数据/problems/ugly-number/ ?难度: 简单
解题思路:
中学数学中我们学到一个概念 集合 (英文是set)，集合的最大特点是 元素不能重复 。Python中，set是一组key的集合。
于是可以使用迭代法和set这种数据结构来求解此题。
具体操作为: 迭代地求给定数的各位数字的平方和，维护一个set，迭代循环的出口是平方和为1或已在set中出现过。
已 AC 的代码为:
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
运行结果:
执行用时 : 36ms , 在所有 Python3 提交中击败了 99.72% 的用户
代码要点:
Python 中 "/" 并不是 C 语言中的 "/"(整除)，Python 中 / 的结果是浮点数，如果需要得到整数，需使用 "//"，也可使用 int()?函数来处理
Python的 同一个 class?中一个函数 a 调用另一个函数 b，只需使用关键字 def?定义好函数 a 和 函数 b，在 a 中使用 self.b?即可
相应的，如需测试，本地可执行的代码为:
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))
系列文章 ? ? ? ??
??LeetCode面试系列 第3天：No.67 - 二进制数求和 ? ? LeetCode面试系列 第2天：No.136 - 只出现一次的数 ? ? ???Leetcode面试系列 第1天：Leetcode 89 - 格雷码 ??第20天：Python 之装饰器 ? ? 第19天：Web 开发 Flask 介绍??? ? ? ? ? ? ? ? 第18天：Python 之迭代器? ? ??第17天：Python 之引用? ? ? 第16天：Python 错误和异常?? ?? 第15天：Python 输入输出
?
??第14天：Python 高阶函数
?
??第13天：Python 函数的参数?
?
??第12天：Python 集合
?
??第11天：Python 字典第10天：Python 类与对象
第9天：Python?Tupple
第8天：Python List
第7天：Python 数据结构--序列
第6天：Python 模块和包
第5天：Python 函数
第4天：Python 流程控制
第3天：Python 变量与数据类型
第2天：Python 基础语法
第1天：Python 环境搭建
查看更多关于LeetCode面试系列 第4天：No.202 - 快乐数的详细内容...