【Day 48 】2024-05-25 - 401. 二进制手表

[azl397985856]

401. 二进制手表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/binary-watch/

前置知识

暂无

题目描述

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

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

例如，上面的二进制手表读取 “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”。
超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 "13:00", "0:61" 等时间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[Hermione666]

class Solution: def readBinaryWatch(self,num: int) -> list: def count1(n): return bin(n).count('1')

    res = []
    # Directly iterate from 0:00 to 11:59, count the number of 1s in the binary representation
    for i in range(12):
        for j in range(60):
            if count1(i) + count1(j) == num:
                # Format the time correctly with leading zeros for minutes less than 10
                res.append(f"{i}:{j:02d}")
    return res

[Dtjk]

class Solution { public: vector readBinaryWatch(int turnedOn) { vector ans; if(turnedOn>=9)return {}; for(int i=0;i<1024;i++){ int h=i>>6,m=i&63; if(h<12&&m<60&&__builtin_popcount(i)==turnedOn){ ans.push_back(to_string(h)+":"+(m<10?"0"+to_string(m):to_string(m))); } } return ans; } };

[CathyShang]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        minute = [1, 2, 4, 8, 16, 32]
        hour = [1, 2, 4, 8]
        h_len, m_len = len(hour), len(minute)
        ans = []    
        def time(combi, led,  start):
            if led == 0:
                if combi[1] < 10:
                    ans.append(str(combi[0]) + ':0' + str(combi[1]))
                else:
                    ans.append(str(combi[0]) + ':' + str(combi[1]))
            else:
                for i in range(start, h_len + m_len):
                    if i < h_len:
                        combi[0] += hour[i]
                        if combi[0] <= 11:
                            time(combi, led - 1, i + 1)
                        combi[0] -= hour[i]
                    else:
                        combi[1] += minute[i - h_len]
                        if combi[1] <= 59:
                            time(combi, led - 1, i + 1)
                        combi[1] -= minute[i - h_len]       
        cur = 2 * [0]
        time(cur, turnedOn, 0)
        return ans

[zhiyuanpeng]

class Solution: def readBinaryWatch(self, turnedOn: int) -> List[str]: ans = [] for a in range(12): for b in range(60): if (bin(a) + bin(b)).count('1') == turnedOn: ans.append(str(a) +":" + str(b).rjust(2, '0')) return ans

[hillsonziqiu]

解法

/*
 * @lc app=leetcode.cn id=401 lang=javascript
 *
 * [401] 二进制手表
 */

// @lc code=start
/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function (turnedOn) {
  const result = [];

  for (let h = 0; h < 12; h++) {
    for (let m = 0; m < 60; m++) {
      if (
        h.toString(2).split(0).join("").length +
          m.toString(2).split(0).join("").length ===
        turnedOn
      ) {
        const minuteNum = m < 10 ? `0${m}` : m;
        result.push(`${h}:${minuteNum}`);
      }
    }
  }

  return result;
};
// @lc code=end

复杂度分析

• 时间复杂度：O(1); 可枚举场景
• 空间复杂度：O(1);