原题链接:Leecode 401. 二进制手表
糙到不行的DFS(效率感人):
class Solution {
public:
vector<string> res;
int l1[4],l2[6];
void dfs(int n,int now,int h,int m)
{
if(n==now)
{
if(!(h>11 || m>59))
{
string s;
s+=to_string(h);
s+=':';
if(m/10==0) s+='0';
s+=to_string(m);
res.push_back(s);
}
return ;
}
if(h>11 || m>59) return ;
for(int i=0;i<4;i++)
{
if(!l1[i])
{
l1[i]=1;
dfs(n,now+1,h+(1<<i),m);
l1[i]=0;
}
}
for(int i=0;i<6;i++)
{
if(!l2[i])
{
l2[i]=1;
dfs(n,now+1,h,m+(1<<i));
l2[i]=0;
}
}
}
vector<string> readBinaryWatch(int turnedOn) {
dfs(turnedOn,0,0,0);
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
return res;
}
};
美丽而优雅的写法~
class Solution {
public:
//计算二进制中1的个数
int Count(int n)
{
int r=0;
while(n)
{
n=n&(n-1);
r++;
}
return r;
}
vector<string> readBinaryWatch(int turnedOn) {
vector<string> res;
for(int i=0;i<12;i++)
{
for(int j=0;j<60;j++)
{
if(Count(i)+Count(j)==turnedOn)
{
string s;
s+=to_string(i);
s+=':';
if(j/10==0) s+='0';
s+=to_string(j);
res.push_back(s);
}
}
}
return res;
}
};