題目連結: Binary Watch

題目描述為: 有一個2進位刻度的手錶，頂部有4個LED燈，對應數值 [8,4,2,1]，用來表示 hours(0-11)。底部有6個LED燈，對應數值 [32,16,8,4,2,1]，用來表示 minutes (0-59)。每個LED燈亮或不亮來表示該數值有沒有被使用。
題目會給定一個非負整數 N ，表示有 N 個LED燈亮著，要求我們返回所有可能的時間。
題目有補充說明返回的格式: hour 表示法必須是 0,1,2,...,10,11， minutes 表示法必須是 00,01,02,...,12。
而返回的順序不需處理。

例子1: n=1,
output=["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]。

思路 1: 燈號對應法

10個LED燈亮或不亮的所有情況總共 1024 種情形，我們可以遍歷所有情況檢查以下幾個條件: 1.燈亮數是否符合要求，2. 轉換的時間是否為合法的表示法 ( hours 要小於12，且 minutes 要小於 60 )。最後轉成正確格式後返回。

• 複雜度評估
  設輸入的數值為 N，此方法需要的步驟均不超過1024次，與 N 無關，時間複雜度為 O(1)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func readBinaryWatch(num int) []string {
    
    var leds [10] int
    var tmp,pos,r int
    var ans []string
   
    for i:=0;i<1024;i++{
        
        leds =[10] int{} 
        tmp,pos,r=i,len(leds)-1,0
    
		for tmp>0{
			r=tmp%2
            
			if r!=0{
				leds[pos]++
			} 
			tmp/=2
			pos--	
		}
        
        if !isCorrectNum(leds,num){
            continue
        }
        
        h,m:=convertLEDToTime(leds)
    
        if isLegalTime(h,m){
		
            s:=convertToRequiredFormat(h,m)
            ans=append(ans,s)
		}
						
	}
        
        
    return ans
    
}


func isCorrectNum ( leds [10]int,num int ) ( bool){
    
	c:=0
	
    for _,v:=range leds{
        if v!=0{
            c++
        }
    }
    
    if c!=num {
        return false
	}
    
    return true
    
}


func convertLEDToTime ( leds [10]int) ( hours int,minutes int){
    
	tmp:=0
    
    
    for i,v:=range leds{
        
        if v==0{
            continue
        }
        
        
        if i<6 {
            tmp=1<<uint(i)
			minutes+=tmp
        }else {
            tmp=1<<uint((i-6))
			hours+=tmp
        }
        
    }
    
	return hours,minutes
}


func isLegalTime( hours int,minutes int) ( bool){
    
    if hours<12 && minutes <60{
        return true
    }
    
    return false
    
}

func convertToRequiredFormat(hours int,minutes int) (s string){
    
    	ts:=""
		if minutes<10{
			ts="0"
		}
			
		s=strconv.Itoa(hours)+ ":"+ts+strconv.Itoa(minutes)
    
       return s
    
}

思路 2: 組合數分配法

設輸入的整數為 n，我們可以分配給 hours k個LED亮燈，minutes 則為(n-k)個LED亮燈，然後把亮燈對應的數值表示出來，以 hours 為例，4 個 LED 燈選 k 個亮，即為 $C_4^k = \binom{4}{k} = \frac{4!}{k!(4-k)!}$，其中 0≤k≤4，minutes 同理。

• 複雜度評估
  設輸入的數值為 n，當 hours 選了 k個燈亮時， minutes 則需要選 (n-k)個燈亮，總共步驟不超過 $\sum_{k=0}^n C_k^4 \times C_{n-k}^6$ 次，此數值有界，故時間複雜度為O(1)，此方法只用了常數量變數，與 n 無關，空間複雜度為 O(1)。

參考程式碼

func readBinaryWatch(n int) []string {
	var ans []string
    leds:=make( []bool,10)

	var dfs func(int, int)
	dfs = func(idx, n int) {
		var h, m int
		if n == 0 {
			m, h = convertToTimeValue(leds[:6]),convertToTimeValue(leds[6:])
            
            if isLegalTime(h,m){
                s:=convertToRequiredFormat(h,m)
                ans=append(ans,s)
            }
			
			return
		}

		for i := idx; i < len(leds)-n+1; i++ {
			leds[i] = true
			dfs(i+1, n-1)
			leds[i] = false
		}
	}

	dfs(0, n)

	return ans
}

var bs = []int{1, 2, 4, 8, 16, 32}

func convertToTimeValue(leds []bool) (sum int) {
    
    for i,v:=range leds {
		if v==true {
			sum += bs[i]
		}
	}

	return sum
}

func isLegalTime( hours int,minutes int) ( bool){
    
    if hours<12 && minutes <60{
        return true
    }
    
    return false
    
}

func convertToRequiredFormat(hours int,minutes int) (s string){
    
    	ts:=""
		if minutes<10{
			ts="0"
		}
			
		s=strconv.Itoa(hours)+ ":"+ts+strconv.Itoa(minutes)
    
       return s
    
}

小結:

方法 1 與方法 2 共用了輔助函式。
此題尚有許多種實現方式，其核心思想大致與方法 1、2相同。
方法 1 遍歷所有LED燈情況，我們也可以仿造此方法，遍歷 hours(0-11) 及 minutes(0-59) 的所有情況。
設輸入的燈亮數為 N，方法 2 利用遞迴遍歷所有燈亮數為 N 的組合，而組合數尚有諸多應用如列舉所有情形，詳細過程可參考此篇文。
我將解法加上簡單的測試，上傳程式碼到此。