未分類

Happy Number

Go, HashTable, LeetCode, Math

Happy Number

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:

19 is a happy number

1
2
3
4
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
提示 解題應用
Math 規律觀查
HashTable HashMap

Default:

1
2
3
func isHappy(n int) bool {
}

解答思路:

相當直覺好解的題目，不過重點在於什麼時候停下來，其實就是一路記錄總合的結果，直到發現有值重覆的情況或是最後總合為1兩種情況，其餘的就是一直不斷的重覆探究各種可能的結果，有一數列在開頭一小段之後，中間的數列便出現了不斷重覆的情況有人稱為龜兔賽跑定理，總而言之在這裡只要用hashMap做儲存，一發現該值的總合已經存在裡頭，表示此刻已經開始重覆先前的數列，如果先前都不是總合為1，那麼肯定之後重覆的數列也不會出現了。

程式碼解說:

如果要判斷總合是否出現重覆，那麼一開始給的值記得也要塞入hashmap中，不過我們只關注key的值是否重覆出現，至於value則是都可以，這裡我就直接塞與key一樣的值，第一個迴圈發現hashmap沒有這個值的話就繼續查看下一個總合，不過在那之前先把其值給存入hashmap，接著將舊的總合歸0，然後開始重新計算每位數次方總合的結果，如果總合為1當然就是目標值回傳true，否則就再繼續判斷是否hashmap存在這個總合的結果，然後重覆上述步驟直到找到目標或發覆重覆結果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sum := n
hashMap := make(map[int]int)
_, ok := hashMap[sum]
for !ok {
	hashMap[sum] = sum
	sum = 0
	for n != 0 {
		sum += (n % 10) * (n % 10)
		n = n / 10
	}
	if sum == 1 {
		return true
	}
	n = sum
	_, ok = hashMap[sum]
}
return false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isHappy(n int) bool {
	sum := n
	hashMap := make(map[int]int)
	_, ok := hashMap[sum]
	for !ok {
		hashMap[sum] = sum
		sum = 0
		for n != 0 {
			sum += (n % 10) * (n % 10)
			n = n / 10
		}
		if sum == 1 {
			return true
		}
		n = sum
		_, ok = hashMap[sum]
	}
	return false
}

總結:

快樂數的找法就和龜兔賽跑定理一樣，其實就是一路記錄總合的結果，直到發現有值出現重覆或是達成指定結果兩種情況，其餘的就是一直不斷的重覆探究各種可能的結果，而因為不需理會值之間的關係，便以hashmap做儲存來方便快速查詢。

分享到