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，小時(shí)用{8, 4, 2, 1}四個(gè)數(shù)碼燈的亮和滅來(lái)指示的妖，分鐘用{32, 16, 8, 4, 2, 1}六個(gè)數(shù)碼燈的亮和滅來(lái)指示足陨。
上圖中，小時(shí)位置星虹，1和2亮著镊讼，所以小時(shí)是3(= 1 + 2)；分鐘位置蝶棋，16、8嫡良、1亮著，所以分鐘是25(= 16 + 8 + 1)寝受，所示時(shí)間是3:25.
問(wèn)題的輸入是亮燈的個(gè)數(shù)，要求計(jì)算出所有可能的時(shí)間京闰。
分析
本題被放在了回溯問(wèn)題分類(lèi)下面甩苛，自然考慮用回溯的思想來(lái)解決這個(gè)問(wèn)題。
對(duì)于本題而言痊土，每個(gè)燈有兩種狀態(tài)（亮和滅）墨林，對(duì)應(yīng)在回溯法里就是兩個(gè)分支。亮的時(shí)候旭等，當(dāng)前燈代表的數(shù)字就應(yīng)該被加在當(dāng)前的小時(shí)/分鐘總數(shù)上；而當(dāng)前燈代表的數(shù)字是跟遞歸的深度有關(guān)的隙袁，可以在遞歸函數(shù)中增加一個(gè)指示深度的參數(shù)來(lái)實(shí)現(xiàn)這一點(diǎn)弃榨。
而問(wèn)題又被分為了兩個(gè)部分，小時(shí)和分鐘是分開(kāi)計(jì)算的坛梁，這就得出了兩種可能的解法：
- 只維護(hù)一棵遞歸樹(shù)腊凶，從小時(shí)或分鐘任意一部分的最低位開(kāi)始遞歸拴念；同時(shí)我們又要求小時(shí)和分鐘分開(kāi)計(jì)算，可以借助當(dāng)前深度來(lái)判斷現(xiàn)在應(yīng)該計(jì)算小時(shí)還是分鐘政鼠。這里給出一個(gè)函數(shù)頭，具體的實(shí)現(xiàn)就不展開(kāi)了万搔。
void _foo(int curHour, int curMin, int depth);
- 對(duì)小時(shí)和分鐘分別維護(hù)一棵遞歸樹(shù)，兩棵遞歸樹(shù)的最大高度和恒等于亮燈的總位數(shù)昧谊，這樣比較方便操作酗捌。筆者下面貼出的第一份代碼就實(shí)現(xiàn)了這個(gè)思路。
非回溯解法
該解法是筆者在寫(xiě)完回溯解法后胖缤，在該題的Solution中受大神的啟發(fā)，通過(guò)計(jì)算某個(gè)時(shí)間的亮燈位數(shù)是否和當(dāng)前給定的亮燈位數(shù)匹配狗唉，來(lái)判斷該時(shí)間是否是一個(gè)解涡真，這里也貼上自己實(shí)現(xiàn)的代碼。
Code
兩棵遞歸樹(shù)
//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){
//如果當(dāng)前剩余可以亮的燈數(shù)比還未判斷的（包括當(dāng)前位）的燈的數(shù)量還多的話(huà)澳迫，不可能滿(mǎn)足剧劝，故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){
//如果當(dāng)前剩余可以亮的燈數(shù)比還未判斷的（包括當(dāng)前位）的燈的數(shù)量還多的話(huà)，不可能滿(mǎn)足拢锹，故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;
}
};
懷疑自己智商之神級(jí)代碼系列
最后再貼一份來(lái)自Solution的神級(jí)代碼卒稳，又是讓人懷疑自己智商系列他巨。
可以看到該作者對(duì)C++內(nèi)的數(shù)據(jù)結(jié)構(gòu)和方法了解得比較多，其實(shí)也不是真的說(shuō)自己智商低吧···主要還是C++的底子太差捻爷，代碼經(jīng)驗(yàn)少份企。
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;
}
