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:

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

分析

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

20 -> 4 -> 16 -> 37 -> 58 -> 90 -> 81
                  ^                 |
                  |                 v
                  |                 65
                  |                 |
                  |                 v
                  61 <- 56 <- 64 <- 80

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

程序设计

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

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

代码如下，

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 函数按照规则生成新的值，实现如下

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

提交后 AC，完整代码如下：

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 解法参考以前写的文章链表有环