ChoDocs

外观

LeetCode 401. 二进制手表 ​

作者:Choi Yang
更新于:17 小时前
字数统计:1.1k 字
阅读时长:5 分钟

题目描述 ​

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

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

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

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

示例：

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

提示：

javascript
输出的顺序没有要求。
小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 "13:00", "0:61" 等时间。

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

解题思路 ​

回溯算法，我的解法类似于全排列做法，将 10 个小灯泡进行排列组合，然后根据 0 和 1 来判断灯泡是否亮，如果亮了，加上对应二进制，然后将 0-3分给小时来计算，将 4-9分给分钟来计算，但是要考虑一下，就是可能会出现重复情况，于是用 Set数据结构维护一下就好了。

javascript
function readBinaryWatch(num) {
  const res = new Set()
  const vis = Array.from({ length: 10 }).fill(0)
  const check = (hour, minutes) => {
    if (hour >= 0 && hour <= 11 && minutes >= 0 && minutes <= 59)
      return true
    return false
  }
  const dfs = (t, vis) => {
    if (t == 0) {
      const hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8
      const minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32
      if (check(hour, minutes)) {
        const tmp = `${hour}:${minutes >= 10 ? minutes : `0${minutes}`}`
        res.add(tmp)
      }
    }
    for (let i = 0; i < 10; i++) {
      if (vis[i])
        continue
      vis[i] = 1
      dfs(t - 1, vis)
      vis[i] = 0
    }
  }
  dfs(num, vis)
  return [...res]
}
cpp
class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        vector<int> vis(10, 0);
        auto check = <CustomLink title="&" href="int hour, int minutes" /> {
            if (hour >= 0 && hour <= 11 && minutes >= 0 && minutes <= 59) return true;
            return false;
        };
        function<void(int, int)> dfs = <CustomLink title="&" href="int t, int cnt" /> {
            if (t == 0) {
                int hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8;
                int minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32;
                if (check(hour, minutes)) {
                    string tmp = to_string(hour) + ":" + (minutes >= 10 ? to_string(minutes) : "0" + to_string(minutes));
                    res.push_back(tmp);
                }
                return;
            }
            for (int i = cnt; i <= 10 - t; i++) {
                if (vis[i]) continue;
                vis[i] = 1;
                dfs(t - 1, i + 1);
                vis[i] = 0;
            }
        };
        dfs(num, 0);
        return res;
    }
};
java
class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        int[] vis = new int[10];
        boolean check = (hour, minutes) -> {
            if (hour >= 0 && hour <= 11 && minutes >= 0 && minutes <= 59) return true;
            return false;
        };
        dfs(num, 0, vis, res, check);
        return res;
    }

    private void dfs(int t, int cnt, int[] vis, List<String> res, boolean check) {
        if (t == 0) {
            int hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8;
            int minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32;
            if (check(hour, minutes)) {
                String tmp = hour + ":" + (minutes >= 10 ? minutes : "0" + minutes);
                res.add(tmp);
            }
            return;
        }
        for (int i = cnt; i <= 10 - t; i++) {
            if (vis[i] == 1) continue;
            vis[i] = 1;
            dfs(t - 1, i + 1, vis, res, check);
            vis[i] = 0;
        }
    }
}
python
class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        res = []
        vis = [0] * 10
        def check(hour, minutes):
            if hour >= 0 and hour <= 11 and minutes >= 0 and minutes <= 59:
                return True
            return False
        def dfs(t, cnt):
            if t == 0:
                hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8
                minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32
                if check(hour, minutes):
                    tmp = str(hour) + ":" + (str(minutes) if minutes >= 10 else "0" + str(minutes))
                    res.append(tmp)
                return
            for i in range(cnt, 10 - t + 1):
                if vis[i] == 1: continue
                vis[i] = 1
                dfs(t - 1, i + 1)
                vis[i] = 0
        dfs(num, 0)
        return res

补充，后面看到有大佬这样做，进行了去重操作，关键点在回溯 for循环那里。其实这个相当于全排列了。

javascript
function readBinaryWatch(num) {
  const res = []
  const vis = Array.from({ length: 10 }).fill(0)
  const check = (hour, minutes) => {
    if (hour >= 0 && hour <= 11 && minutes >= 0 && minutes <= 59)
      return true
    return false
  }
  const dfs = (t, cnt, vis) => {
    if (t == 0) {
      const hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8
      const minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32
      if (check(hour, minutes)) {
        const tmp = `${hour}:${minutes >= 10 ? minutes : `0${minutes}`}`
        res.push(tmp)
      }
      return
    }
    for (let i = cnt; i <= 10 - t; i++) {
      if (vis[i])
        continue
      vis[i] = 1
      dfs(t - 1, i + 1, vis)
      vis[i] = 0
    }
  }
  dfs(num, 0, vis)
  return res
}
javascript
学如逆水行舟，不进则退

Contributors ​

Choi Yang
文章作者：Choi Yang
文章链接：
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ChoDocs！