或许你不知道的是,Leetcode 中是有很多 数学题 的,本文要解析的题 快乐数 就是其中到一个典型问题,本题将基于数据结构 set
来求解。
今天要给大家分析的面试题是 LeetCode 上第 202 号问题,
LeetCode - 202. 快乐数
https://leetcode-cn.com/problems/happy-number/
题目描述
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
示例:
1 |
|
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
解题思路:
中学数学中我们学到一个概念集合(英文是 set),集合的最大特点是元素不能重复。Python中,set 是一组 key 的集合。
于是可以使用迭代法和 set 这种数据结构来求解此题。
具体操作为: 迭代地求给定数的各位数字的平方和,维护一个 set,迭代循环的出口是平方和为1或已在 set 中出现过。
已AC
的代码为:
1 |
|
运行结果:
执行用时 : 36 ms
, 在所有 Python3 提交中击败了99.72%
的用户.
相应的,如需测试,本地可执行的代码为:
1 |
|
示例代码: https://github.com/JustDoPython/leetcode-python/tree/master/leetcode-202