Trace
6.21 每日一题
传送门：https://leetcode-cn.com/problems/binary-watch/
Problem
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
小时不会以零开头：
- 例如，
"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
分钟必须由两位数组成，可能会以零开头：
- 例如，
"10:2" 是无效的时间，正确的写法应该是 "10:02" 。
示例 1：
1
2
| 输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
|
示例 2：
数据范围
思路
方法一：dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public:
int d[11];
map<int,bool> vis;
vector<int> hm={1,2,4,8,1,2,4,8,16,32};
vector<string> ans;
void dfs(int k,int turnedOn){
if(k==turnedOn){
int h=0;
int m=0;
for(int i=0;i<turnedOn;i++){
if(d[i]<4){
h=h+hm[d[i]];
}
else{
m=m+hm[d[i]];
}
if(h>11||m>59){
return;
}
}
string s="";
s+=to_string(h);
s+=":";
if(m<10){
s+="0";
}
s+=to_string(m);
ans.push_back(s);
return;
}
for(int i=0;i<=9;i++){
if(!vis[i]){
vis[i]=true;
d[k]=i;
dfs(k+1,turnedOn);
vis[i]=false;
}
}
}
vector<string> readBinaryWatch(int turnedOn) {
dfs(0,turnedOn);
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
return ans;
}
};
|
方法二：枚举+二进制判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
int calculateBin(int x){
int res=0;
while(x){
if(x&1){
res++;
}
x>>=1;
}
return res;
}
vector<string> readBinaryWatch(int turnedOn) {
vector<string> ans;
int sumOfBin;
for(int i=0;i<=11;i++){
for(int j=0;j<=59;j++){
sumOfBin=0;
sumOfBin=sumOfBin+calculateBin(i)+calculateBin(j);
if(sumOfBin==turnedOn){
string s="";
s+=to_string(i);
s+=":";
if(to_string(j).size()==1){
s+="0";
}
s+=to_string(j);
ans.push_back(s);
}
}
}
return ans;
}
};
|
