0401. Binary Watch

# 401. 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:

``````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”.

## 解题思路 #

• 给出数字 n，要求输出二进制表中所有可能的时间
• 题目中比较坑的是，分钟大于 60 的都不应该打印出来，小时大于 12 的也不应该打印出来，因为是非法的。给出的 num 大于 8 的也是非法值，最终结果应该输出空字符串数组。
• 这道题的数据量不大，可以直接用打表法，具体打表函数见 `findReadBinaryWatchMinute()``findReadBinaryWatchHour()` 这两个函数。

## 代码 #

``````
package leetcode

import (
"fmt"
"strconv"
)

// 解法一
func readBinaryWatch(num int) []string {
memo := make([]int, 60)
// count the number of 1 in a binary number
count := func(n int) int {
if memo[n] != 0 {
return memo[n]
}
originN, res := n, 0
for n != 0 {
n = n & (n - 1)
res++
}
memo[originN] = res
return res
}
// fmtMinute format minute 0:1 -> 0:01
fmtMinute := func(m int) string {
if m < 10 {
return "0" + strconv.Itoa(m)
}
return strconv.Itoa(m)
}

var res []string
// traverse 0:00 -> 12:00
for i := 0; i < 12; i++ {
for j := 0; j < 60; j++ {
if count(i)+count(j) == num {
res = append(res, strconv.Itoa(i)+":"+fmtMinute(j))
}
}
}
return res
}

// 解法二 打表
var (
hour    = []string{"1", "2", "4", "8"}
minute  = []string{"01", "02", "04", "08", "16", "32"}
hourMap = map[int][]string{
0: {"0"},
1: {"1", "2", "4", "8"},
2: {"3", "5", "9", "6", "10"},
3: {"7", "11"},
}
minuteMap = map[int][]string{
0: {"00"},
1: {"01", "02", "04", "08", "16", "32"},
2: {"03", "05", "09", "17", "33", "06", "10", "18", "34", "12", "20", "36", "24", "40", "48"},
3: {"07", "11", "19", "35", "13", "21", "37", "25", "41", "49", "14", "22", "38", "26", "42", "50", "28", "44", "52", "56"},
4: {"15", "23", "39", "27", "43", "51", "29", "45", "53", "57", "30", "46", "54", "58"},
5: {"31", "47", "55", "59"},
}
)

func readBinaryWatch1(num int) []string {
var res []string
if num > 8 {
return res
}
for i := 0; i <= num; i++ {
for j := 0; j < len(hourMap[i]); j++ {
for k := 0; k < len(minuteMap[num-i]); k++ {
res = append(res, hourMap[i][j]+":"+minuteMap[num-i][k])
}
}
}
return res
}

/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
// 以下是打表用到的函数
// 调用 findReadBinaryWatchMinute(num, 0, c, &res) 打表
func findReadBinaryWatchMinute(target, index int, c []int, res *[]string) {
if target == 0 {
str, tmp := "", 0
for i := 0; i < len(c); i++ {
t, _ := strconv.Atoi(minute[c[i]])
tmp += t
}
if tmp < 10 {
str = "0" + strconv.Itoa(tmp)
} else {
str = strconv.Itoa(tmp)
}
// fmt.Printf("找到解了 c = %v str = %v\n", c, str)
fmt.Printf("\"%v\", ", str)
return
}
for i := index; i < 6; i++ {
c = append(c, i)
findReadBinaryWatchMinute(target-1, i+1, c, res)
c = c[:len(c)-1]
}
}

// 调用 findReadBinaryWatchHour(num, 0, c, &res) 打表
func findReadBinaryWatchHour(target, index int, c []int, res *[]string) {
if target == 0 {
str, tmp := "", 0
for i := 0; i < len(c); i++ {
t, _ := strconv.Atoi(hour[c[i]])
tmp += t
}
str = strconv.Itoa(tmp)
//fmt.Printf("找到解了 c = %v str = %v\n", c, str)
fmt.Printf("\"%v\", ", str)
return
}
for i := index; i < 4; i++ {
c = append(c, i)
findReadBinaryWatchHour(target-1, i+1, c, res)
c = c[:len(c)-1]
}
}

``````

Apr 8, 2023