Contents

[Golang][Leetcode][HashTable]刷題系列-202-Happy Number


202. Happy Number


Level : Easy

原題連結 : Click

題目 :

Write an algorithm to determine if a number n 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.
  • 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.

Return true if n is a happy number, and false if not.


Example :

Note

Input: n = 19

Output: true

Explanation:

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1


Input: n = 2

Output: false


解題思路 :

  • 題目定義了何謂Happy Number,要我們去判斷他給的這個數是否為Happy Number
  • 先釐清Happy Number的定義:
    1. 這個數字不能為負數
    2. 將他每一個位數分開來各拿去做平方後,在加起來,得到了一個新的數字
    3. 將此數字循環上面運算直到他這個數字變成1,他便是Happy Number,或是他會無限循環因為他永遠得不到1,他便不是Happy Number

  • 因為題目說有無限循環的可能,這時候使用hash table,因為可以標記起來他每次得到的新數字
  • 因為當他只要再次得到以前得到過的數字,不可能是Happy Number,將程式結束跳出死循環

以下是我的解法:

Runtime: 0 ms, faster than 100.00% of Go online submissions for Happy Number.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func isHappy(n int) bool {
    
    happyMap := make(map[int]bool)
    
    for n != 1 && !happyMap[n] {
       
        happyMap[n] = true
        n = getSum(n)
    
    }
    
    return n == 1
    
    
}

func getSum(n int) (sum int) {
    
    for n > 0 {
        sum += (n%10) * (n%10)
        n = n/10
    }
    
    return
}



最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!