401. Binary Watch
发布时间：2020-12-14 04:25:50 所属栏目：大数据 来源：网络整理
导读：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 wa
|
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 ? Note:
? Approach #1: DFS + backtracking. [C++] class Solution {
public:
vector<string> readBinaryWatch(int num) {
init();
vector<string> ans;
for (int i = 0; i <= num; ++i) {
set<int> h;
set<int> m;
hours(i,h,0);
minutes(num-i,m,0);
string temp;
for (int i : h) {
for (int j : m) {
//cout << i << ‘ ‘ << j << endl;
if (i >= 12 || j >= 60) continue;
temp = to_string(i);
temp += ":";
if (j < 10) temp += "0" + to_string(j);
else temp += to_string(j);
ans.push_back(temp);
}
}
}
//sort(ans.begin(),ans.end());
return ans;
}
private:
vector<pair<int,bool>> hour;
vector<pair<int,bool>> minute;
void init() {
for (int i = 0; i < 4; ++i)
hour.push_back({pow(2,i),true});
for (int i = 0; i < 6; ++i)
minute.push_back({pow(2,true});
}
void hours(int n,set<int>& h,int h_) {
if (n == 0) {
h.insert(h_);
return;
}
for (auto &i : hour) {
if (i.second) {
i.second = false;
hours(n-1,h_+i.first);
i.second = true;
}
}
}
void minutes(int n,set<int>& m,int m_) {
//cout << "m_ = " << m_ << " ";
if (n == 0) {
m.insert(m_);
return;
}
for (auto &j : minute) {
if (j.second) {
j.second = false;
minutes(n-1,m_+j.first);
j.second = true;
}
}
}
};
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
