Leetcode-202 Happy Number

Description

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

1
2
3
4
5
6
7
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

分析

Happy Number 按照计算规则最终会止于 1,来看一个非 Happy Number 的会怎样,我们尝试一下 20,

1
2
3
4
5
6
7
20 -> 4 -> 16 -> 37 -> 58 -> 90 -> 81
^ |
| v
| 65
| |
| v
61 <- 56 <- 64 <- 80

观察发现,非 Happy Number 按照计算规则生成的数据链会成环,最终无法终止。所以我们只需要将计算结果保存在 HashMap 中,按照计算规则生成一个数时判断这个数是否在 HashMap 中,如果存在则说明会成环,该数不是 Happy Number。

程序设计

按照如上分析,程序设计时拆分两个步骤,

  1. 按照计算规则生成下一个数
  2. 判断是否是 Happy Number

代码如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isHappy(self, n: int) -> bool:
memo = {}
next = n
while True:
next = self.genarate(next)
if next == 1:
return True
if memo.get(next):
return False
memo[next] = True


def genarate(self, n: int) -> int:
pass

其中 genarate 函数按照规则生成新的值,实现如下

1
2
3
4
5
6
7
8
def genarate(self, n: int) -> int:
sum = 0
while (n != 0):
d = n % 10
sum += d * d
n = n // 10

return sum

提交后 AC,完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def isHappy(self, n: int) -> bool:
memo = {}
next = n
while True:
next = self.genarate(next)
if next == 1:
return True
if memo.get(next):
return False
memo[next] = True


def genarate(self, n: int) -> int:
sum = 0
while (n != 0):
d = n % 10
sum += d * d
n = n // 10

return sum

优化

由分析得出,本体的关键点在于判断是否成环,以上解法使用 HashMap (或 HashSet),空间复杂度为 O(n),n 为链表的长度,如果要优化空间复杂度可以使用 Floyd 判断圈算法。Leetcode 题目之 Linked List Cycle 解法参考以前写的文章 链表有环

本文标题:Leetcode-202 Happy Number

文章作者:Syncher

发布时间:2019年07月31日 - 00:07

最后更新:2019年08月02日 - 09:08

原始链接:https://0x400.com/2019-07-31-lc-202-happy-number.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。