401.二进制手表 about leetcode

[zzcyes]

题解

方法一：暴力法

/**
 * @param {number} num
 * @return {string[]}
 */
var readBinaryWatch = function(num) {
    if (num == 0) return ["0:00"];
    let result = [];
    for (let i = 0; i < 12; i++) {
        for (let j = 0; j < 60; j++) {
            if (calcNumLight(i) + calcNumLight(j) == num) {
                let str = `${i}:`;
                if (j < 10) {
                    str += `0${j}`;
                } else {
                    str += `${j}`;
                }
                result.push(str);
            }
        }
    }
    return result;
};

function calcNumLight(n) {
    let result = 0;
    while (n > 0) {
        result += n % 2;
        n = Math.floor(n / 2);
    }
    return result;
}

方法二：回溯

/**
 * @param {number} num
 * @return {string[]}
 */
var readBinaryWatch = function(num) {
    if (num === 0) {
        return ["0:00"];
    }
    const res = [];
    let h = num < 4 ? num : 3,
        m = num < 4 ? 0 : num - 3;
    while (0 <= h) {
        let hours = [];
        let mins = [];
        if (h < 4 && m < 6) {
            hours = getBinarys(h, 4, new Set());
            mins = getBinarys(m, 6, new Set());
        }
        for (const hh of hours) {
            for (const mm of mins) {
                res.push(`${hh}:${mm < 10 ? '0' + mm : mm}`);
            }
        }
        h--;
        m++;
    }
    return res;
};

function getBinarys(n, k, times) {
    if (n === 0) {
        return [0];
    }
    backtrack(new Array(k).fill(0), 0, n, times);
    return [...times.values()];
}

function backtrack(arr, m, n, times) {
    if (m === n) {
        const num = parseInt(arr.join(''), 2);
        const limit = arr.length < 6 ? 12 : 60;
        if (num < limit) {
            times.add(num);
        }
    }
    for (let i = 0; i < arr.length; i++) {
        if (arr[i]) continue;
        arr[i] = 1;
        backtrack(arr, m + 1, n, times);
        arr[i] = 0;
    }
}