LeetCode面试系列 第4天：No.202 - 快乐数
或许你不知道的是，Leetcode 中是有很多 数学题 的，本文要解析的题 快乐数 就是其中到一个典型问题，本题将基于数据结构 set 来求解。
今天要给大家分析的面试题是 LeetCode 上第 202 号问题，
LeetCode - 202. 快乐数
https://leetcode-cn.com/problems/happy-number/
题目描述
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例:
输入: 19输出: true
解释:
贡献者: LeetCode
题目难度: Easy
相关话题
相关话题
哈希表
https://leetcode-cn.com/tag/hash-table/
数学
https://leetcode-cn.com/tag/math
相似题目
各位相加
https://leetcode-cn.com/problems/add-digits/ 难度: 简单
丑数
https://leetcode-cn.com/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 == 1def GetSquareSum(self, n: int) -> bool:sum0 = 0while n > 0:r = n - int(n/10)*10n = int(n/10)sum0 += r * rreturn 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 == 1def GetSquareSum(self, n: int) -> bool:sum0 = 0while n > 0:r = n - int(n/10)*10n = int(n/10)sum0 += r * rreturn sum0sol = 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 错误和异常 第10天：Python 类与对象
第9天：Python Tupple
第8天：Python List
第7天：Python 数据结构--序列
第6天：Python 模块和包
第5天：Python 函数
第4天：Python 流程控制
第3天：Python 变量与数据类型
第2天：Python 基础语法
第1天：Python 环境搭建