LeetCode Binary Watch

LeetCode 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".

class Solution {
public:
// cur为传入的二进制串，comb要把ones个1填入[s,t)中
void comb(vector<int>& res, int cur, int s, int t, int ones) {
if (ones == 0)res.push_back(cur);
else {
for (int i = s; i < t; ++i) {
if ((cur&(1 << i)) == 0) {
comb(res, cur | (1 << i), i + 1, t, ones - 1); // 递归把ones-1个1填入[i+1,t)中
}
}
}
}
vector<string> ans;
for (int hour = 0; hour <= 3; ++hour) {
if (hour > num)break;
vector<int> hours;
comb(hours, 0, 0, 4, hour);
vector<int> minutes;
comb(minutes, 0, 0, 6, num - hour);
for (int i = 0; i < hours.size(); ++i) {
if (hours[i] > 11)continue;
string tmp_h = to_string(hours[i]);
for (int j = 0; j < minutes.size(); ++j) {
if (minutes[j] > 59)continue;
string tmp_m = to_string(minutes[j]);
if (tmp_m.size() < 2)tmp_m = "0" + tmp_m;
ans.push_back(tmp_h + ":" + tmp_m);
}
}
}
return ans;
}
};