LeetCode 401. Binary Watch（二进制手表）

题目描述

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

• The order of output does not matter.
• The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
• The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

解法一

思路

这题简单来说就是给定二进制1的个数，找出所有可能的4位二进制数和6位二进制数组合。

假设有一个方法get_combination(length, num_ones)可以得到所有长为length、1的个数为num_ones的二进制数，那么这题的处理框架就是：

result = []
for ones_hour in range(0, num + 1):
    ones_minute = num - ones_hour
    hours = get_combination(4, ones_hour)
    minutes = get_combination(6, ones_minute)
    for hour in hours:
        result.append('%d:%02d' % (hour, minute))

下面来看看get_combination(length, num_ones)如何实现，怎么得到长为length、1的个数为num_ones的二进制数呢？这里采用DFS的方式，即遍历长为length的二进制数的每一位，每一位选择是否将当前位置1，一旦置1的位数达到了num_ones，则添加到结果中。以get_combination(4, 2)为例：

           ↓      ↓      ↓      ↓
0000 -> 0000 -> 0000 -> 0000 -> 0000 (NO)
                                1000 (NO)
                        0100 -> 0100 (NO)
                                1100 (YES)
                0010 -> 0010 -> 0010 (NO)
                             -> 1010 (YES)
                        0110 (YES)
        0001 -> 0001 -> 0001 -> 0001 (NO)
                                1001 (YES)
                        0101 (YES)
                0011 (YES)

output: [1100, 1010, 0110, 1001, 0101, 0011]

Python

class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        def get_combination(length, num_ones, base, pool):
            if num_ones == 0:
                pool.append(base)
                return
            if length == 0 or length < num_ones:
                return
            get_combination(length - 1, num_ones - 1, base + (1 << (length - 1)), pool)
            get_combination(length - 1, num_ones, base, pool)

        result = []
        for ones_hour in range(0, num + 1):
            ones_minute = num - ones_hour
            hours = []
            minutes = []
            get_combination(4, ones_hour, 0, hours)
            get_combination(6, ones_minute, 0, minutes)
            for hour in hours:
                if hour > 11:
                    continue
                for minute in minutes:
                    if minute > 59:
                        continue
                    result.append('%d:%02d' % (hour, minute))
        return result

Java

public class Solution {
    public List<String> readBinaryWatch(int num) {
        class Utils {
            void getCombination(int length, int numOnes, int base, List<Integer> pool) {
                if (numOnes == 0) {
                    pool.add(base);
                    return;
                }
                if (length == 0 || length < numOnes) {
                    return;
                }
                getCombination(length - 1, numOnes - 1, base + (1 << (length - 1)), pool);
                getCombination(length - 1, numOnes, base, pool);
            }
        }
        Utils utils = new Utils();
        List<String> result = new ArrayList<>();
        for (int onesHour = 0; onesHour <= num; onesHour++) {
            int onesMinute = num - onesHour;
            List<Integer> hours = new ArrayList<>();
            List<Integer> minutes = new ArrayList<>();
            utils.getCombination(4, onesHour, 0, hours);
            utils.getCombination(6, onesMinute, 0, minutes);
            for (int hour : hours) {
                if (hour > 11) {
                    continue;
                }
                for (int minute : minutes) {
                    if (minute > 59) {
                        continue;
                    }
                    result.add(String.format("%d:%02d", hour, minute));
                }
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        class Utils {
        public:
            void getCombination(int length, int numOnes, int base, vector<int> &pool) {
                if (numOnes == 0) {
                    pool.push_back(base);
                    return;
                }
                if (length == 0 || length < numOnes) {
                    return;
                }
                getCombination(length - 1, numOnes - 1, base + (1 << (length - 1)), pool);
                getCombination(length - 1, numOnes, base, pool);
            }
        };
        Utils utils;
        vector<string> result;
        for (int onesHour = 0; onesHour <= num; onesHour++) {
            int onesMinute = num - onesHour;
            vector<int> hours;
            vector<int> minutes;
            utils.getCombination(4, onesHour, 0, hours);
            utils.getCombination(6, onesMinute, 0, minutes);
            for (int hour : hours) {
                if (hour > 11) {
                    continue;
                }
                for (int minute : minutes) {
                    if (minute > 59) {
                        continue;
                    }
                    if (minute > 9) {
                        result.push_back(to_string(hour) + ":" + to_string(minute));
                    } else {
                        result.push_back(to_string(hour) + ":0" + to_string(minute));
                    }
                }
            }
        }
        return result;
    }
};