題目連結: Happy Number

此題描述為給定一個正整數，要我們判斷此數是否為快樂數。
快樂數定義為: 將該數字所有位數的平方相加，得到的新數再次求所有位數的平方和，不斷循環，若最終結果為 1 則為快樂數。

例子 1: iuput=19 , output= true。
1²+9²=82
8²+2²=68
6²+8²=100
1²+0²+0²=1

思路 1 : Hash 法

我們可以用一 map 將計算過程中處理過的數字都記錄起來: 以例子1 為例，要記錄的數字為: 19,82,68,100,1。若遇到 1 ，則為快樂數。若重複遇到處理過的數字，則表示進入循環，此時不會是快樂數。

• 複雜度評估
  設判定的數字為 n ，其位數為 N，因每個位數計算過程產生的數字必< 10x10，所以計算過程中產生的不循環數，其個數上界為 100N，時間複雜度為O(N)。此方法同時建立了一組 map 來記錄處理過的數字，空間複雜度為 O(N)。

參考程式碼

func isHappy(n int) bool {     
    
  	m := make(map[int]bool)
	m[n] = true

	for n != 1 {
		n = helper(n)
		if m[n] == true {
			return false
		}

		m[n] = true
	}

	return true
}

func helper( n int)  (next int){
    
    r:=0
    for n!=0 {
        r=n%10
        next += r*r
        n=n/10
    }
    return next
    
}

思路 2: 快慢指針法

我們也可以將處理過的數字視為一組 Linked List，判定是否有循環 (cycle)。此時可仿造 day16-Linked List Cycle 的方法 2: 讓 slow 表示進行 1 次位數平方和計算， fast 表示進行 2 次位數平方和計算， 若最終相遇點為數值 1，表示為快樂數。

• 複雜度評估
  設判定的數字為 n ，其位數為 N，因每個位數計算過程產生的數字必< 10x10，所以計算過程中產生的不循環數，其個數上界為 100N，時間複雜度為O(N)。此方法只使用了常數個變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func isHappy(n int) bool {
    slow:=n
    fast:=helper(n)
    
    for fast!=1 && fast!=slow{
        slow=helper(slow)
        fast=helper(helper(fast))
    }
    
    
    return fast==1
}

func helper( n int)  (next int){
    
    r:=0
    for n!=0 {
        r=n%10
        next += r*r
        n=n/10
    }
    return next
}

思路 3 : 觀察法

設 n 為給定的正整數，我們觀察計算過程中數字的變化可發現位數平方和 (sum)會有小於10的時候，而對數字 2~9 進行運算可發現除了 7 以外，其他均會進入不為 1 的循環，因此只要判斷當 sum 小於10 時，是否為 1 或 7 即可。

• 複雜度評估
  設判定的數字為 n ，其位數為 N，因每個位數計算過程產生的數字必< 10x10，所以計算過程中產生的不循環數，其個數上界為 100N，時間複雜度為O(N)。此方法只使用了常數個變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func isHappy(n int) bool {     
    
  for n != 1 {
		n = helper(n)
		if n < 10 {
			if n == 1 || n == 7 {
				return true
			}
			return false
		}
	}

	return true
}

func helper( n int)  (next int){
    
    r:=0
    for n!=0 {
        r=n%10
        next += r*r
        n=n/10
    }
    return next
    
}

小結:

此題我複雜度估計是對位數 N 評估。
解法 1,2,3 共用了輔助函式。
解法 2 為快慢指針法的應用情境之一。
解法 3 為快樂數基本性質。
我將解法加上簡單的測試 上傳程式碼到此。