Problem
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".
题意
如图所示，有一块Binary Watch，小时用{8, 4, 2, 1}四个数码灯的亮和灭来指示，分钟用{32, 16, 8, 4, 2, 1}六个数码灯的亮和灭来指示。
上图中，小时位置，1和2亮着，所以小时是3(= 1 + 2)；分钟位置，16、8、1亮着，所以分钟是25(= 16 + 8 + 1)，所示时间是3:25.
问题的输入是亮灯的个数，要求计算出所有可能的时间。
分析
本题被放在了回溯问题分类下面，自然考虑用回溯的思想来解决这个问题。
对于本题而言，每个灯有两种状态（亮和灭），对应在回溯法里就是两个分支。亮的时候，当前灯代表的数字就应该被加在当前的小时/分钟总数上；而当前灯代表的数字是跟递归的深度有关的，可以在递归函数中增加一个指示深度的参数来实现这一点。
而问题又被分为了两个部分，小时和分钟是分开计算的，这就得出了两种可能的解法：
- 只维护一棵递归树，从小时或分钟任意一部分的最低位开始递归；同时我们又要求小时和分钟分开计算，可以借助当前深度来判断现在应该计算小时还是分钟。这里给出一个函数头，具体的实现就不展开了。
void _foo(int curHour, int curMin, int depth);
- 对小时和分钟分别维护一棵递归树，两棵递归树的最大高度和恒等于亮灯的总位数，这样比较方便操作。笔者下面贴出的第一份代码就实现了这个思路。
非回溯解法
该解法是笔者在写完回溯解法后，在该题的Solution中受大神的启发，通过计算某个时间的亮灯位数是否和当前给定的亮灯位数匹配，来判断该时间是否是一个解，这里也贴上自己实现的代码。
Code
两棵递归树
//Runtime: 3ms
class Solution {
public:
vector<string> readBinaryWatch(int num) {
maxBit = num;
_dfs();
return result;
}
private:
vector<string> result;
vector<int> minBuf;
vector<int> hourBuf;
int maxBit;
void _minDfs(int remainBits, int curMin, int height){
//如果当前剩余可以亮的灯数比还未判断的（包括当前位）的灯的数量还多的话，不可能满足，故return
if (remainBits > 6 - height || curMin > 59) return;
if (remainBits == 0){
minBuf.push_back(curMin);
return;
}
_minDfs(remainBits - 1, curMin + pow(2, height), height + 1);
_minDfs(remainBits, curMin, height + 1);
}
void _hourDfs(int remainBits, int curHour, int height){
//如果当前剩余可以亮的灯数比还未判断的（包括当前位）的灯的数量还多的话，不可能满足，故return
if (remainBits > 4 - height || curHour > 11) return;
if (remainBits == 0){
hourBuf.push_back(curHour);
return;
}
_hourDfs(remainBits - 1, curHour + pow(2, height), height + 1);
_hourDfs(remainBits, curHour, height + 1);
}
void _dfs(){
for (int i = 0, j = maxBit - i; i <= maxBit && i <= 4; i++, j--){
minBuf.clear();
hourBuf.clear();
_hourDfs(i, 0, 0);
_minDfs(j, 0, 0);
_combineHourAndMin();
}
return;
}
void _combineHourAndMin(){
sort(hourBuf.begin(), hourBuf.end());
sort(minBuf.begin(), minBuf.end());
for (int i = 0; i < hourBuf.size(); i++)
for (int j = 0; j < minBuf.size(); j++)
result.push_back(string(_tranInt2Str(hourBuf[i], minBuf[j])));
return;
}
string _tranInt2Str(int curHour, int curMin){
string curTime;
char buf[10];
sprintf(buf, "%d", curHour);
curTime = buf;
curTime += ":";
if (curMin < 10)
curTime += "0";
sprintf(buf, "%d", curMin);
curTime += buf;
return curTime;
}
};
BitsCount法
class Solution {
public:
vector<string> readBinaryWatch(int num) {
for (int h = 0; h < 12; h++)
for (int m = 0; m < 60; m++)
if (_bitCount(h, m) == num)
result.push_back(string(_tranInt2Str(h, m)));
return result;
}
private:
vector<string> result;
int _bitCount(int hour, int min){
int hBit = 0;
int mBit = 0;
for (int i = 8; i >= 0; i /= 2){
if (hour == 0) break;
if (hour % i != hour){
hBit++;
hour %= i;
}
}
for (int i = 32; i >= 0; i /= 2){
if (min == 0) break;
if (min % i != min){
mBit++;
min %= i;
}
}
return hBit + mBit;
}
string _tranInt2Str(int curHour, int curMin){
string curTime;
char buf[10];
sprintf(buf, "%d", curHour);
curTime = buf;
curTime += ":";
if (curMin < 10)
curTime += "0";
sprintf(buf, "%d", curMin);
curTime += buf;
return curTime;
}
};
怀疑自己智商之神级代码系列
最后再贴一份来自Solution的神级代码，又是让人怀疑自己智商系列。
可以看到该作者对C++内的数据结构和方法了解得比较多，其实也不是真的说自己智商低吧···主要还是C++的底子太差，代码经验少。
vector<string> readBinaryWatch(int num) {
vector<string> rs;
for (int h = 0; h < 12; h++)
for (int m = 0; m < 60; m++)
if (bitset<10>(h << 6 | m).count() == num)
rs.emplace_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));
return rs;
}
