LeetCode 二进制手表
二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)。
每个 LED 代表一个 0 或 1,最低位在右侧。
例如,上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量,返回所有可能的时间。
案例:
输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
注意事项:
输出的顺序没有要求。
小时不会以零开头,比如 “01:00” 是不允许的,应为 “1:00”。
分钟必须由两位数组成,可能会以零开头,比如 “10:2” 是无效的,应为 “10:02”。
思路分析:
第一步:我们对于给定的亮的灯个数num进行分解,分成小时灯个数hoursCnt、分钟灯个数minsCnt。
第二步:然后对小时灯个数hoursCnt小时的情况进行构造。(比如,当hoursCnt == 1,可以构造成小时为 1,2,4,8)
第三步:接着对分钟灯个数minsCnt分钟的情况进行构造。(比如,当minsCnt== 1,可以构造成分钟为 1,2,4,8,16,32)
第四步:最后将小时的集合和分钟集合进行搭配组合。
class Solution {
public:
vector<string> readBinaryWatch(int num) {
vector<string> result;
int hoursCntMax = min(num, 3);//hours可能亮的灯最大个数
//第一步:对num进行分解为hoursCnt和minsCnt,且hoursCnt + minsCnt == num
for (int hoursCnt = 0; hoursCnt <= hoursCntMax; ++hoursCnt) {
int minsCnt = num - hoursCnt;//mins需要亮的个数
if (minsCnt > 5) {//剪枝,不难发现分钟最多只能亮5个灯
continue;
}
//第二步:广度优先搜索hours亮hoursCnt个灯的情况
queue<int> hoursQue;
hoursQue.push(0);//亮0个灯,只有一种情况
//从0个灯开始,每次将n - 1个灯的状态再亮一个灯,达到n个灯
for (int cnt = 0; cnt < hoursCnt; ++cnt) {
//将上一次队列中的所有状态都亮一盏灯
int tempQueSize = hoursQue.size();
for (int index = 0; index < tempQueSize; ++index) {
int nowFront = hoursQue.front();
hoursQue.pop();
//然后穷举这一盏的权
for (int nextValue = 1; nextValue <= 8; nextValue *= 2) {
//为了防止出现重复,所以只能选择比当前还大的权
if (nextValue > nowFront && nowFront + nextValue < 12) {
hoursQue.push(nowFront + nextValue);
}
}
}
}
//第三步:广度优先搜索mins亮minsCnt个灯的情况
queue<int> minsQue;
minsQue.push(0);//亮0个灯,只有一种情况
//从0个灯开始,每次将n - 1个灯的状态再亮一个灯,达到n个灯
for (int cnt = 0; cnt < minsCnt; ++cnt) {
//将上一次队列中的所有状态都亮一盏灯
int tempQueSize = minsQue.size();
for (int index = 0; index < tempQueSize; ++index) {
int nowFront = minsQue.front();
minsQue.pop();
//然后穷举这一盏的权
for (int nextValue = 1; nextValue <= 32; nextValue *= 2) {
//为了防止出现重复,所以只能选择比当前还大的权
if (nextValue > nowFront && nowFront + nextValue < 60) {
minsQue.push(nowFront + nextValue);
}
}
}
}
//第四步:将小时的集合和分钟集合进行搭配组合。
vector<int> hoursVec;//将小时队列转换为vector容器
while (!hoursQue.empty()) {
hoursVec.push_back(hoursQue.front());
hoursQue.pop();
}
vector<int> minsVec;//将分钟队列转换为vector容器
while (!minsQue.empty()) {
minsVec.push_back(minsQue.front());
minsQue.pop();
}
int hoursVecSize = hoursVec.size(), minsVecSize = minsVec.size();
//进行组合,每次去一个小时元素,一个分钟元素
for (int i = 0; i < hoursVecSize; ++i) {
for (int j = 0; j < minsVecSize; ++j) {
//拼接字符串
string tempRes = to_string(hoursVec[i]) + ":";
if (minsVec[j] < 10) {//当分钟数为个位数,需要添加“0”,形如"0:08"
tempRes += "0";
}
tempRes += to_string(minsVec[j]);
result.push_back(tempRes);
}
}
}
return result;
}
};
代码虽然有些长,但是思路非常清晰。