题目描述
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例:
输入:19输出:true
解释:
- 贡献者: LeetCode
- 题目难度: Easy
- 相关话题
相关话题
相似题目
- 各位相加
https://leetcode-cn.com/problems/add-digits/ 难度: 简单 - 丑数
https://leetcode-cn.com/problems/ugly-number/ 难度: 简单
解题思路:
中学数学中我们学到一个概念集合(英文是set)，集合的最大特点是元素不能重复。Python中，set是一组key的集合。
于是可以使用迭代法和set这种数据结构来求解此题。
具体操作为: 迭代地求给定数的各位数字的平方和，维护一个set，迭代循环的出口是平方和为1或已在set中出现过。
已 AC的代码为:
classSolution:def isHappy(self, n: int)-> bool:unhappy = set()while n notin unhappy and n !=1:unhappy.add(n)n = self.GetSquareSum(n)return n ==1defGetSquareSum(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 即可
相应的，如需测试，本地可执行的代码为:
classSolution:def isHappy(self, n: int)-> bool:unhappy = set()while n notin unhappy and n !=1:unhappy.add(n)n = self.GetSquareSum(n)return n ==1defGetSquareSum(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 - 格雷码
