未分類

Binary Watch

Backtracking, BitManipulation, Go, LeetCode, Math

Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

1
2
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
  • The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.
提示 解題應用
Backtracking 遞回
BitManipulation 二進位位元組合

Default:

1
2
3
func backTracking(bin string, led int) []string {
}

解答思路:

一開始本來想用一陣列存著1,2,4,8,16,32然後再分別去排序組合所有情況，然而跟直接二進位組合只有0與1的情況相比，寫起來實在複雜太多，所以用二進位來傳值遞回的方式組合出所有的情況，你可以選擇小時與分鐘拆開來處理，不過因為手錶的信號也就10個燈，2的10次方不過1024種組合，所以我是將全數列出後才判斷小時與分鐘的規格是否正確。

程式碼解說:

因為是使用遞回的關係，所以是不斷的呼叫自己，而直到長度到達10(手錶全部的燈)才停止遞回並做判斷，因為題目有限制一定要亮多少個燈的情況下的所有組合，所以如果前面還沒達到目標的燈數了，就再後頭補1並將燈數-1繼續遞回，其餘仍繼續後頭補0(表示不亮燈)尋找其它可能，最後等到兩者長度都達到10判斷結束後再一起合併將結果做回傳

1
2
3
4
5
6
7
8
9
10
11
12
func backTracking(bin string, led int) []string {
	var tmp []string
	var hrStr string
	var minStr string
	if len(bin) == 10 {
	...
	}
	if led > 0 {
		tmp = backTracking(bin+"1", led-1)
	}
	return append(backTracking(bin+"0", led), tmp...)
}

至於長度已經到達10的判斷，首先要先將沒有亮滿燈數的情況給除去(目標燈數歸0)，接著取前面四位元(代表四個燈)當做小時，其餘的則是當作分鐘，並將二進位字串轉回數字來判斷小時是否介於0~11，分鐘是否介於0~59，如果都符合則再判斷分鐘長度是否只有個位數來決定是否要在前面補0，最後才合併回傳字串陣列，若上述任一情況不符，則回傳空的字串陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
if led == 0 {
	hours, _ := strconv.ParseInt(bin[:4], 2, 64)
	minutes, _ := strconv.ParseInt(bin[4:], 2, 64)
	if hours <= 11 && minutes <= 59 {
		hrStr = strconv.Itoa(int(hours))
		minStr = strconv.Itoa(int(minutes))
		if len(minStr) == 1 {
			minStr = "0" + minStr
		}
		return []string{hrStr + ":" + minStr}
	}
}
return []string{}

完整程式碼:

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
func readBinaryWatch(num int) []string {
    return backTracking("", num)
}
func backTracking(bin string, led int) []string {
	var tmp []string
	var hrStr string
	var minStr string
	if len(bin) == 10 {
		if led == 0 {
			hours, _ := strconv.ParseInt(bin[:4], 2, 64)
			minutes, _ := strconv.ParseInt(bin[4:], 2, 64)
			if hours <= 11 && minutes <= 59 {
				hrStr = strconv.Itoa(int(hours))
				minStr = strconv.Itoa(int(minutes))
				if len(minStr) == 1 {
					minStr = "0" + minStr
				}
				return []string{hrStr + ":" + minStr}
			}
		}
		return []string{}
	}
	if led > 0 {
		tmp = backTracking(bin+"1", led-1)
	}
	return append(backTracking(bin+"0", led), tmp...)
}

總結:

若需要列出所有二進位組合的情況，利用遞回新增0與1的方式是最快的選擇。

分享到