LeetCode 401. 二进制手表

作者:Choi Yang

更新于:7 个月前

字数统计:1.1k 字

阅读时长:5 分钟

题目描述

二进制手表顶部有 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

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

javascript

var readBinaryWatch = function (num) {
  let res = new Set();
  let vis = new Array(10).fill(0);
  let check = (hour, minutes) => {
    if (hour >= 0 && hour <= 11 && minutes >= 0 && minutes <= 59) return true;
    return false;
  };
  let dfs = (t, vis) => {
    if (t == 0) {
      let hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8;
      let minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32;
      if (check(hour, minutes)) {
        let 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循环那里。其实这个相当于全排列了。

var readBinaryWatch = function (num) {
  let res = [];
  let vis = new Array(10).fill(0);
  let check = (hour, minutes) => {
    if (hour >= 0 && hour <= 11 && minutes >= 0 && minutes <= 59) return true;
    return false;
  };
  let dfs = (t, cnt, vis) => {
    if (t == 0) {
      let hour = vis[0] * 1 + vis[1] * 2 + vis[2] * 4 + vis[3] * 8;
      let minutes = vis[4] * 1 + vis[5] * 2 + vis[6] * 4 + vis[7] * 8 + vis[8] * 16 + vis[9] * 32;
      if (check(hour, minutes)) {
        let 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;
};

学如逆水行舟，不进则退

Contributors

Choi Yang