【Day 48 】2022-12-18 - 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[zjsuper]

class Solution: def readBinaryWatch(self, turnedOn: int) -> List[str]: ans = []

how many on hour, how many on min

    #if turnedOn == 0 or turnedOn >9:
    #    return []
    def dfs(ans,hour, num):
        if hour>num:
            return 
        for h in itertools.combinations([1,2,4,8],hour):
            if sum(h) > 11:
                continue
            for m in itertools.combinations([1,2,4,8,16,32],num-hour):
                if sum(m) > 59:
                    continue
                time = "%d:%02d" % (sum(h),sum(m))
                ans.append(time)
        dfs(ans,hour+1, num)
    dfs(ans,0, turnedOn)
    return ans

[Alyenor]

function readBinaryWatch(turnedOn: number): string[] {
const ans = [];
    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) {
                ans.push(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
    }
    return ans;
};

[FlipN9]

/**
    Approach 1: 枚举所有的 h 和 m, 计算他们的 bitCount, 看位数和是否等于 turnedOn
                12 * 60 = 720 种组合
    TC: O(1)    SC: O(1)
*/
class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(h).append(":");
                    sb.append(m < 10 ? "0" : "").append(m);
                    res.add(new String(sb));
                }
            }
        }
        return res;
    }
}

/**
    Approach 2: 枚举 2^10 = 1024 种灯的开闭组合
                高 4 位: 小时     低 6 位: 分钟, 
                若小时和分钟的值 均在合规范围内, 并且 二进制中 1 的个数为 turnedOn, 加入 res
    TC: O(1)    SC: O(1)            
*/
class Solution1 {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 1024; i++) {
            int h = i >> 6, m = i & 63;
            if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
                StringBuilder sb = new StringBuilder();
                sb.append(h).append(":");
                sb.append(m < 10 ? "0" : "").append(m);
                res.add(new String(sb));
            }
        }
        return res;
    }
}

[chenming-cao]

解题思路

枚举。按照题意，对于有效的时间，小时的取值范围时0-11，分钟的取值范围是0-59。总共720种可能。我们对这720种可能组合逐一判定，看是否满足亮灯个数要求。如果满足要求，则按照字符串要求格式存入数组中。最后返回数组即可。判断亮灯个数是要看二进制数中1的个数，这里调用Integer.bitCount(int num)函数，可以直接得到1的个数。

代码

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(i);
                    sb.append(":");
                    if (j < 10) sb.append(0);
                    sb.append(j);
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(1)，双层循环总共运行720次，为常数
• 空间复杂度：O(1)

[mayloveless]

思路

列举小时可能的值，列举分钟可能的值，拼接在一起。

代码

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    const res = [];
    for(let i=0;i<=turnedOn;i++) {
        const hour = combine([1,2,4,8],i, true);
        const min = combine([1,2,4,8,16,32],turnedOn-i);
        for(let h=0;h<hour.length;h++) {
            for(let n=0;n<min.length;n++) {
                res.push(hour[h]+':'+min[n])
            }
        }
    }
    return res;
};

var combine = function(nums, k, isHour) {
    if (k>nums.length) return [];

    const res = [];
    var combineFunc = function(count, path) {
        if (path.length === k) {
           const num = Number(_.sum(path));
            if (isHour) {
                if (num >=0 && num <= 11) {
                    res.push(num);
                }
            } else {
                if (num >=10 && num <= 59) {
                    res.push(num);
                }
                if (num >=0 && num <= 9) {
                    res.push('0'+num);
                }
            }
            return 
        }
        for (let i = count;i<nums.length;i++) {
            path.push(nums[i]);
            combineFunc(i+1, path)
            path.pop();
        }
    }
    combineFunc(0, []);
    return res;
};

[buer1121]

class Solution: def readBinaryWatch(self, turnedOn: int) -> List[str]:

枚举的方法

    ans = list()
    for h in range(12):
        for m in range(60):
            if bin(h).count("1") + bin(m).count("1") == turnedOn:
                ans.append(f"{h}:{m:02d}")
    return ans

[wtdcai]

代码

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans = list()
        for h in range(12):
            for m in range(60):
                if bin(h).count("1") + bin(m).count("1") == turnedOn:
                    ans.append("{}:{:02d}".format(h,m))
        return ans

复杂度分析

O(1)
O(1)

[jackgaoyuan]

func readBinaryWatch(turnedOn int) []string {
    bits := make([]int, 10)
    var res []string
    cache := make(map[int]bool)
    dfs(bits, 0, turnedOn, cache, &res)
    return res
}

func dfs(bits []int, count int, turnedOn int, cache map[int]bool, res *[]string) {
    num := convertToInt(bits)
    if cache[num] {
        return
    }
    defer func(){
        cache[num] = true   
    }()
    if count == turnedOn {
        time, ok := getTime(bits)
        if ok {
            *res = append(*res, time)
        }
        return
    }
    for i := 0; i < len(bits); i++ {
        if bits[i] == 0 {
            bits[i] = 1
            dfs(bits, count + 1, turnedOn, cache, res)
            bits[i] = 0
        }
    }
}

func convertToInt(bits []int) int {
    var res int
    for i := len(bits) - 1; i >= 0; i-- {
        res += bits[i] * int(math.Pow(2, float64(len(bits) - 1 - i)))
    }
    return res
}

func getTime(bits []int) (time string, valid bool) {
    hourBit := bits[0:4]
    minuteBit := bits[4:]
    var hour, minute int
    for i := len(hourBit) - 1;  i >= 0; i-- {
        hour += hourBit[i] * int(math.Pow(2, float64(len(hourBit) - 1 - i)))
    }
    for i := len(minuteBit) - 1;  i >= 0; i-- {
        minute += minuteBit[i] * int(math.Pow(2, float64(len(minuteBit) - 1 - i)))
    }
    if hour < 12 && minute < 60 {
        if minute < 10 {
            time = fmt.Sprintf("%d:0%d", hour, minute)
        } else {
            time = fmt.Sprintf("%d:%d", hour, minute)
        }
        valid = true
        return
    }
    valid = false
    return
}

Time: O(C10 turnOn)

[zywang0]

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(i);
                    sb.append(":");
                    if (j < 10) sb.append(0);
                    sb.append(j);
                    res.add(sb.toString());
                }
            }
        }
        return res;
    }
}

[bookyue]

code

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (bitCount(i) + bitCount(j) == turnedOn)
                    res.add(i + ":" + (j <= 9 ? "0" + j : j));
            }
        }

        return res;
    }

    private int bitCount(int num) {
        int count = 0;
        while (num > 0) {
            num = num & (num - 1); // num -= num & (-num);
            count++;
        }

        return count;
    }

[Moin-Jer]

class Solution { public List readBinaryWatch(int turnedOn) { List res = new ArrayList<>(); for (int i = 0; i < 12; i++) { for (int j = 0; j < 60; j++) { if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) { StringBuilder sb = new StringBuilder(); sb.append(i); sb.append(":"); if (j < 10) sb.append(0); sb.append(j); res.add(sb.toString()); } } } return res; } }

[ringo1597]

代码

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    ans.add(h + ":" + (m < 10 ? "0" : "") + m);
                }
            }
        }
        return ans;
    }
}

[xuanaxuan]

var readBinaryWatch = function (num) { const res=[]

//直接遍历  0:00 -> 12:00   每个时间有多少1
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;

} //计算二进制中1的个数 function count1(n) { let res = 0; while (n != 0) { n = n & (n - 1); res++; } return res; }

[snmyj]

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        res = []
        def count(i):
            res = 0
            while i != 0:
                i = i & (i - 1)
                res += 1
            return res
        for i in range(12):
            c = count(i)
            if c == num:
                res.append("%d:%02d" %(i, 0))
                continue
            for j in range(60):
                s = count(j)
                if (s + c) == num:
                    res.append("%d:%02d" %(i, j))
        return res

[klspta]

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int i = 0; i < 1024; ++i) {
            int h = i >> 6, m = i & 63;
            if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
                ans.add(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
        return ans;
    }
}

[BruceZhang-utf-8]

思路

• 回溯+dfs

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
     List<Integer> mins;
    List<String> res;

    public List<String> readBinaryWatch(int num) {
        res = new ArrayList<>();
        mins = new ArrayList<>();
        for (int i = 0; i < 6 && num >= i; i++) {
            dfs(0, 0, i, true);
            dfs(0, 0, num - i, false);
            mins.clear();
        }
        return res;
    }

    private void dfs(int st, int sum, int cnt, boolean flag) {
        if (cnt == 0) {
            if (flag) {
                mins.add(sum);
            } else {
                if (!mins.isEmpty()) { 
                    for (int m : mins) {
                        // res.add(String.format("%d:%02d", sum, m));
                        StringBuilder sb = new StringBuilder();
                        sb.append(sum).append(':');
                        if (m < 10) {
                            sb.append('0');
                        }
                        sb.append(m);
                        res.add(sb.toString());
                    }
                }
            }
            return;
        }

        for (int i = st; i < (flag ? 6 : 4); i++) {
            int temp = (int)Math.pow(2, i);
            if (flag && sum + temp >= 60 || !flag && sum + temp >= 12) {
                break;
            }
            dfs(i + 1, sum + temp, cnt - 1, flag);
        }
    }

}

[paopaohua]

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new  ArrayList<String>();
        for(int h =0 ; h < 12 ;h++){
            for(int m = 0;m < 60;m++){
                if(Integer.bitCount(h) + Integer.bitCount(m) == turnedOn)
                    ans.add(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
        return ans;
    }
}

[Jetery]

401. 二进制手表

思路

暴力枚举

代码 (cpp)

class Solution {
public:
    int count(int n) {
        int ret = 0;
        while (n) {
            n = n & (n - 1);
            ret++;
        }
        return ret;
    }
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int i = 0; i < 12; i++) 
            for (int j = 0; j < 60; j++) {
                if (count(i) + count(j) == turnedOn) {
                    string h = to_string(i);
                    string min = to_string(j);
                    string temp = h + ":" + (j < 10 ? "0" + min : min);
                    ans.push_back(temp);
                }
            }

        return ans;
    }
};

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(1)

[saitoChen]

思路

遍历watch的小时和分钟，将他们转换成2进制，接着获取二进制中所有的1，1的个数就是turnedOn

• js转换成二进制的方法是num.toStrint(2)

代码

const transform2Binary = (num) => num.toString(2)
const getOneCount = (binary) => binary.split('0').join('').length

const readBinaryWatch = (turnedOn) => {
    const result = []
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m <= 59; m++) {
            if (getOneCount(transform2Binary(h)) + getOneCount(transform2Binary(m)) === turnedOn) {
                result.push(h + ":" + (m < 10 ? "0" : "") + m)
            }
        }
    }
    return result
}

##  复杂度分析
时间复杂度：O(1)
空间复杂度：O(1)

[Elon-Lau]

const transform2Binary = (num) => num.toString(2) const getOneCount = (binary) => binary.split('0').join('').length

const readBinaryWatch = (turnedOn) => { const result = [] for (let h = 0; h < 12; h++) { for (let m = 0; m <= 59; m++) { if (getOneCount(transform2Binary(h)) + getOneCount(transform2Binary(m)) === turnedOn) { result.push(h + ":" + (m < 10 ? "0" : "") + m) } } } return result }

复杂度分析

时间复杂度：O(1) 空间复杂度：O(1)

[Alexno1no2]

这竟然是个简单题，抄会都难
'''
总体思路
在10个灯中选num个灯点亮，如果选择的灯所组成的时间已不合理（小时超过11，分钟超过59）就进行剪枝
也就是从0到10先选一个灯亮，再选当前灯的后面的灯亮，再选后面的灯的后面的灯亮，一直到num个灯点满
具体思路
为了方便计算，分别设置了小时数组和分钟数组
递归的四个参数分别代表：剩余需要点亮的灯数量，从索引index开始往后点亮灯，当前小时数，当前分钟数
每次进入递归后，先判断当前小时数和分钟数是否符合要求，不符合直接return
for循环枚举点亮灯的情况，从index枚举到10，每次枚举，
减少一个需要点亮的灯数量num - 1
从当前已点亮的灯后面选取下一个要点亮的灯 i + 1
在hour中增加当前点亮灯的小时数，如果i大于3，当前灯是分钟灯而不是小时灯，则加上0个小时
在minute中增加当前点亮灯的分钟数，如果i没有大于3，当前灯是小时灯而不是分钟灯，则加上0分钟
当剩余需要点亮的灯数量为0的时候，已枚举完一种情况，根据题目要求的格式加到res列表中
返回res

'''
class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]
        minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]
        res = []
        def backtrack(num, index, hour, minute):
            if hour > 11 or minute > 59:
                return
            if num == 0:
                res.append('%d:%02d' % (hour, minute))
                return
            for i in range(index, 10):
                backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i])

        backtrack(num, 0, 0, 0)
        return res

[A-pricity]

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
const readBinaryWatch = num => {
    const nums = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]
    let visited = new Array(nums.length).fill(0)
    let result = []

    readBinaryWatchCore(nums, visited, result, 0, num, 0)

    return result
}

/**
 * 回溯法核心方法
 * 
 * @param {[Number]} nums // 灯对应的值
 * @param {[Number]} visited // 所有灯的状态 
 * @param {[string]} result // 所有时间字符串 
 * @param {Number} step // 当前点亮灯的数量
 * @param {Number} num // 灯的数量 
 * @param {Number} start // 下一盏灯范围的起始位置 
 */
const readBinaryWatchCore = (nums, visited, result, step, num, start) => {
    if (step === num) {
        result.push(date(nums, visited))
        return
    }

    for (let i = start; i < visited.length; i++) {
        visited[i] = 1

        if (!timeValid(nums, visited)) {
            visited[i] = 0
            continue
        }

        readBinaryWatchCore(nums, visited, result, step + 1, num, i + 1)
        visited[i] = 0
    }
}

/**
 * 检查生成的时间是否有效
 * @param {[Number]} nums 
 * @param {[Number]} visited 
 */
const timeValid = (nums, visited) => {
    let h = 0, m = 0
    for (let i = 0; i < visited.length; i++) {
        if (visited[i] === 0) continue

        if (i < 4) h += nums[i]
        else m += nums[i]
    }

    return h >= 0 && h <= 11 && m >= 0 && m <= 59
}

/**
 * 转成时间字符串
 * @param {[Number]} nums 
 * @param {[Number]} visited 
 */
const date = (nums, visited) => {
    let h = 0, m = 0
    for (let i = 0; i < visited.length; i++) {
        if (visited[i] === 0) continue

        if (i < 4) h += nums[i]
        else m += nums[i]
    }

    return `${h}:${m < 10 ? "0" : ""}${m}`
}

[chiehw]

基本思路：回溯

设亮灯数为 num，假设『分钟』使用了 x 个灯，剩下始终的数为 num - x，在下面代码为代表 onLedNum - onMinLedNum，这样就能将『分钟』的灯和『小时』的灯分开计算。

假设总亮灯数为 3，当前『分钟』的亮灯数为 1，则『小时』的亮灯数为 2。每一轮 dfs 可以计算一个亮灯数的值，当『分钟』的需要计算的灯为 0 时，就将结果保存到 minuteArr 中。只亮一个灯，那么 minuteArr 可能的值为

1, 2, 4, 8, 16, 32

当计算『小时』时，『小时』所需要计算的灯为 0 时，就将其和 minuteArr 中的所有值组合（他们都来自于 for 循环的同一层）。

代码：

enum Led{
    MinuteLed,
    HourLed
};
const int MINUTE = 6;
const int HOUR = 4;
const int ledValue[6] = {1, 2, 4, 8, 16, 32};

class Solution {
private:
    vector<string> res;
    vector<int> minuteArr;

    void dfs(Led ledType, int needCalcLed, int start, int sum){
        if(ledType == MinuteLed && needCalcLed == 0){
            minuteArr.emplace_back(sum);
            return;
        }
        if(ledType == HourLed && needCalcLed == 0){
            char timeCharArr[6];
            for(int minute: minuteArr){
                sprintf(timeCharArr, "%d:%02d", sum, minute);
                res.emplace_back(string{ timeCharArr });
            }
            return;
        }

        int ledTotal = ledType == MinuteLed? MINUTE: HOUR;
        int curValue;
        for(int i=start; i<ledTotal; i++){
            curValue = sum + ledValue[i];
            if(ledType == MinuteLed && curValue >= 60){
                break;
            }
            if(ledType == HourLed && curValue >= 12){
                break;
            }
            dfs(ledType, needCalcLed-1, i+1, curValue);
        }
    }
public:
    vector<string> readBinaryWatch(int onLedNum) {
        int onHourLedNum;
        for(int onMinLedNum=0; onMinLedNum <= onLedNum && onMinLedNum < MINUTE; onMinLedNum++){
            onHourLedNum = onLedNum - onMinLedNum;
            dfs(MinuteLed, onMinLedNum, 0, 0);
            dfs(HourLed, onHourLedNum, 0, 0);

            minuteArr.clear();
        }
        return res;
    }
};

[neado]

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        def possible_number(count, minute=False):
            if count == 0: return [0]
            if minute:
                return filter(lambda a: a < 60, map(sum, combinations([1, 2, 4, 8, 16, 32], count)))
            return filter(lambda a: a < 12, map(sum, combinations([1, 2, 4, 8], count)))
        ans = set()
        for i in range(min(4, num + 1)):
            for a in possible_number(i):
                for b in possible_number(num - i, True):
                    ans.add(str(a) + ":" + str(b).rjust(2, '0'))
        return list(ans)

[RestlessBreeze]

代码

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

[Elsa-zhang]

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        return [str(a) + ":" + f'{b:02d}' for a in range(12) for b in range(60) if (bin(a)+bin(b)).count('1') == turnedOn]

[MaylingLin]

思路

---

笛卡尔积问题

代码

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        def possible_number(count, minute=False):
            if count == 0: return [0]
            if minute:
                return filter(lambda a: a < 60, map(sum, combinations([1, 2, 4, 8, 16, 32], count)))
            return filter(lambda a: a < 12, map(sum, combinations([1, 2, 4, 8], count)))
        ans = set()
        for i in range(min(4, num + 1)):
            for a in possible_number(i):
                for b in possible_number(num - i, True):
                    ans.add(str(a) + ":" + str(b).rjust(2, '0'))
        return list(ans)

复杂度

---

• Time: $O(N)$
• Space: $O(N)$

[whoam-challenge]

class Solution: def readBinaryWatch(self, turnedOn: int) -> List[str]: ans = list() for h in range(12): for m in range(60): if bin(h).count("1") + bin(m).count("1") == turnedOn: ans.append(f"{h}:{m:02d}") return ans

[tiandao043]

思路

枚举，看了题解 __builtin_popcount( )计算有几个二进制1很好用。

代码

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> 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;
    }
};

O(1)