99 - 二进制手表

题目

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。

每个 LED 代表一个 0 或 1，最低位在右侧。

img

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

案例:

输入: n = 1 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

注意事项:

• 输出的顺序没有要求。

• 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。

• 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。

解答

这题目给我看傻了，题解也看傻了

作者：ljj666

链接：https://leetcode-cn.com/problems/binary-watch/solution/cjian-jian-dan-dan-de-ji-xing-dai-ma-jie-jue-wen-t/

/**
 * @param {number} num
 * @return {string[]}
 */
const count1 = function (n) {
  let res = 0
  while (n !== 0) {
    n = n & (n - 1)
    res++
  }
  return res
}

var readBinaryWatch = function (num) {
  let res = []
  for (let i = 0; i < 12; i++) {
    for (let j = 0; j < 60; j++) {
      if (count1(i) + count1(j) === num) {
        res.push(i.toString() + ":" + (j < 10 ? "0" + j.toString() : j.toString()))
      }
    }
  }
  return res
};

Runtime: 56 ms, faster than 66.18% of JavaScript online submissions for Binary Watch.

Memory Usage: 34.3 MB, less than 100.00% of JavaScript online submissions for Binary Watch.

其中的count1()是用来计算二进制中1的个数

n&(n-1)能清除二进制最低位的1

func count1(n int) int {
    var res int
    for n != 0 {
        n = n & (n - 1)
        res++
    }
    return res
}

func readBinaryWatch(num int) []string {
    var res []string
    for i := 0; i < 12; i++ {
        for j := 0; j < 60; j++ {
            if count1(i)+count1(j) == num {
                min := strconv.Itoa(j)
                if j < 10 {
                    min = "0" + min
                }
                fmt.Println("min", min)
                result := strconv.Itoa(i) + ":" + min
                res = append(res, result)
            }
        }
    }
    return res
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Binary Watch.

Memory Usage: 2.9 MB, less than 100.00% of Go online submissions for Binary Watch.

用过从int转string，总是忘记用这个函数😂😂，然后就会转出一堆乱码。。

class Solution:
    def count1(self, n: int) -> int:
        res = 0
        while n != 0:
            n &= n - 1
            res += 1
        return res

    def readBinaryWatch(self, num: int) -> List[str]:
        res = []
        for i in range(12):
            for j in range(60):
                if Solution.count1(self, i) + Solution.count1(self, j) == num:
                    res.append(str(i) + ":" + (("0" + str(j)) if j < 10 else str(j)))
        return res

Runtime: 44 ms, faster than 24.96% of Python3 online submissions for Binary Watch.

Memory Usage: 13.8 MB, less than 9.09% of Python3 online submissions for Binary Watch.

需要在代码当中导入List这个类型，不然会报错。。

from typing import List

python的三元运算符。。😂

递归回溯

作者：WiseMove 链接：https: // leetcode - cn.com / problems / binary - watch / solution / python3di - gui - hui - su - by - wisemove /

我一开始看到手表的想法也是这个思路，但怎么都写不出来。。

还是这个大佬厉害。。

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        hour = [1, 2, 4, 8]
        minute = [1, 2, 4, 8, 16, 32]
        h_len, m_len = len(hour), len(minute)
        res = []

        def time(combination, led, start):
            if led == 0:
                if combination[1] < 10:
                    res.append(str(combination[0]) + ':0' + str(combination[1]))
                else:
                    res.append(str(combination[0]) + ':' + str(combination[1]))
            else:
                for i in range(start, h_len + m_len):
                    if i < h_len:
                        combination[0] += hour[i]
                        if combination[0] < 12:
                            time(combination, led - 1, i + 1)
                        combination[0] -= hour[i]
                    else:
                        combination[1] += minute[i - h_len]
                        if combination[1] < 60:
                            time(combination, led - 1, i + 1)
                        combination[1] -= minute[i - h_len]

        cur = [0] * 2
        time(cur, num, 0)
        return res

Runtime: 40 ms, faster than 56.81% of Python3 online submissions for Binary Watch.

Memory Usage: 14 MB, less than 9.09% of Python3 online submissions for Binary Watch.

暴力美学

作者：SherryOKOK 链接：https: // leetcode - cn.com / problems / binary - watch / solution / cheng - xu - yuan - de - bao - li - mei - xue - by - sherryokok /

简单题解决不花里胡哨😂笑死了

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        if num < 0 or num > 10:
            return None
        res = []
        for i in range(num + 1):
            j = num - i
            if i > 3 or j > 5:
                continue
            hour = self.hours(i)
            minute = self.minutes(j)
            for a in hour:
                for b in minute:
                    res.append(a + ':' + b)
        return res

    def hours(self, num):
        if num == 0:
            res = ['0']
        elif num == 1:
            res = ['1', '2', '4', '8']
        elif num == 2:
            res = ['3', '5', '9', '6', '10']
        elif num == 3:
            res = ['7', '11']
        return res

    def minutes(self, num):
        if num == 0:
            res = ['00']
        elif num == 1:
            res = ['01', '02', '04', '08', '16', '32']
        elif num == 2:
            res = ['03', '05', '09', '17', '33', '06', '10', '18', '34', '12', '20', '36', '24', '40', '48']
        elif num == 3:
            res = ['07', '11', '19', '35', '13', '21', '37', '25', '41', '49', '14', '22', '38', '26', '42', '50', '28', '44', '52', '56']
        elif num == 4:
            res = ['58', '54', '46', '30', '57', '53', '45', '29', '51', '43', '27', '39', '23', '15']
        elif num == 5:
            res = ['59', '55', '47', '31']
        return res

Runtime: 40 ms, faster than 56.81% of Python3 online submissions for Binary Watch.

Memory Usage: 13.7 MB, less than 9.09% of Python3 online submissions for Binary Watch.