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;
}
};