## 读二进制表的显示 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".

【注】

① 使用回溯的思想，分别在小时和分钟上做DFS（DFS可以看作是回溯的一种），给定几个灯亮，然后把这些亮的灯枚举分给小时和分钟．需要注意的是剪枝，即小时必须小于１２，分钟小于６０．然后将小时和分钟组合即可．还有一个需要注意的是如果分钟只有１位数，还要补０。

public class Solution { // 3ms
List<String> res = new ArrayList<>();
for (int i = Math.max(0,num - 6);i <= Math.min(4,num) ;i ++ ) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
DFS(4,i,0,0,list1);
DFS(6,num - i,0,0,list2);
for (int n1 : list1) {
for (int n2 : list2)
{
String str = (String.valueOf(n2).length() == 1 ? "0" : "") + String.valueOf(n2);
}
}
}
return res;
}
public void DFS(int len,int k,int curIndex,int val,List<Integer> list){
if(k == 0 && len == 4 && val < 12) list.add(val);
if(k == 0 && len == 6 && val < 60) list.add(val);
if(curIndex == len || k == 0) return; //停止条件
DFS(len,k,curIndex + 1,val,list);
val += Math.pow(2,curIndex);//计算第curIndex代表的值
k --;
curIndex ++;
DFS(len,k,curIndex,val,list); //
}
}

② 在discuss中看到，将所有的小时和分钟的可能性用数组列出来，以空间换时间，耗时少。

public class Solution { //2ms
String[][] hour = {{"0"},  // hours contains 0 1's
{"1", "2", "4", "8"},   // hours contains 1 1's
{"3", "5", "6", "9", "10"},  // hours contains 2 1's
{"7", "11"}};  // hours contains 3 1's
String[][] minute = {{"00"},  // mins contains 0 1's
{"01", "02", "04", "08", "16", "32"},  // mins contains 1 1's
{"03", "05", "06", "09", "10", "12", "17", "18", "20", "24", "33", "34", "36", "40", "48"},  // mins contains 2 1's
{"07", "11", "13", "14", "19", "21", "22", "25", "26", "28", "35", "37", "38", "41", "42", "44", "49", "50", "52", "56"},  // mins contains 3 1's
{"15", "23", "27", "29", "30", "39", "43", "45", "46", "51", "53", "54", "57", "58"},  // mins contains 4 1's
{"31", "47", "55", "59"}};  // mins contains 5 1's

List<String> res = new ArrayList();
// loop from 0 to 3 which is the max number of bits can be set in hours (4 bits)
for (int i = 0; i <= 3 && i <= num; i++) {
// this if condition is to make sure the index from minutes array would be valid
if (num - i <= 5) {
// if we have i 1's in hours, then we need num - i 1's in minutes, that's why the arrays were created by grouping the number of 1's bits
for (String str1 : hour[i]) {
for (String str2 : minute[num - i]) {
}
}
}
}
return res;
}
}

public class Solution { // 3ms
List<String> res = new ArrayList<>();
for (int h = 0;h < 12 ;h ++ ) {
for (int m = 0;m < 60 ;m ++ ) {
if(Integer.bitCount(h) + Integer.bitCount(m) == num){
String str1 = Integer.toString(h);
String str2 = Integer.toString(m);
res.add(str1 + ":" + (m < 10 ? "0" + str2 : str2));
}
}
}
return res;
}
}

### 叶枫啦啦

【LeetCode】401 Binary Watch （java实现）

BookShu
2016/10/21
405
0

2012/09/03
231
0

ikel
2016/07/07
29
0

2016/12/16
12
0

1.二进制就是逢二进一，只有0和1。 一个字节就是一个英文字母、阿拉伯数字或半个汉字所占的空间（一个汉字占2个字节）。 16进制就是逢16进一，只有0123456789abcdef这16个数字（或子母）。 ...

87305931
2014/12/04
0
0

FAT_mt

5
0

7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column，设type属性为selction即可； 2、@selection-change事件：选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing

6
0
【技术分享】TestFlight测试的流程文档

qtb999

10
0

2019年8月6日，Spring 官方在其博客宣布，Spring Boot 1.x 停止维护，Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号，Spring 官方就已经在博客进行过预告，Spring Boot 1.X 将维...

Java技术剑

18
0