LeetCode算法题-Binary Watch(Java实现)
这是悦乐书的第216次更新,第229篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第84题(顺位题号是401)。二进制手表顶部有4个LED,代表小时(0-11),底部的6个LED代表分钟(0-59)。每个LED代表一个零或一个,右侧的最低有效位。给定非负整数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”。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
代表小时的有四个灯,代表分钟的有六个灯,传入的参数num就是小时加分钟所代表的亮灯数之和,所以只要小时加分钟的亮灯数等于num,就代表可能的一种时间。可以联想到使用位操作,亮就表示1,不亮就表示0,因为只要计算1的位数等于num即可。使用两层循环,外层循环是小时,从0到11,内层循环是分钟,从0到59,如果小时加分钟的二进制1位计数之和等于num,就将其添加进list中。
public List<String> readBinaryWatch(int num) {
List<String> list = new ArrayList<String>();
for (int i=0; i<12; i++) {
for (int j=0; j<60; j++) {
if (Integer.bitCount(i)+Integer.bitCount(j) == num) {
String answer = "";
if (j < 10) {
answer = i + ":0" + j;
} else {
answer = i + ":" + j;
}
list.add(answer);
}
}
}
return list;
}
03 第二种解法
此题也可以理解为从n个数中取出k个数的问题,小时有四个数,分钟有六个数,要从这10个数中取出num个数来,组合成满足条件的时间。比如,num等于2,那么从小时中就可以取1次,剩下的1次在分钟里取,也可以全部在小时里取,也可以全部在分钟中取,只要次数不超过num即可。同时,要先将两种特殊情况排除出去。
public List<String> readBinaryWatch2(int num) {
List<String> list = new ArrayList<String>();
if (num == 0) {
list.add("0:00");
return list;
}
if (num > 8) {
return list;
}
int[] temp = {8,4,2,1,32,16,8,4,2,1};
boolean[] index = new boolean[10];
helperFun(list, temp, index, num, 0);
return list;
}
void helperFun(List<String> list, int[] temp, boolean[] index, int num, int start){
if (num == 0) {
int hour = 0;
int minute = 0;
for (int k = 0; k < 10; k++) {
if (index[k] == true && k <= 3) {
hour += temp[k];
}
if (index[k] == true && k > 3) {
minute += temp[k];
}
}
if (hour >= 12 || minute >= 60) {
return;
} else {
String answer = "";
if (minute < 10) {
answer = hour + ":0" + minute;
} else {
answer = hour + ":" + minute;
}
list.add(answer);
return;
}
}
for (int i = start; i < temp.length; i++) {
index[i] = true;
helperFun(list, temp, index, num - 1, i + 1);
index[i] = false;
}
}
04 第三种解法
思路和第二种解法类似,但是要比第二种解法精简些。我们将表示小时和分钟的数组设置为全局变量,这样就不必在递归的方法里面每次都传入,并且还要判断使用过没有,使用一个指针来帮助我们判断即可,当指针小于4的时候,都是在小时中取,所以小时需要加上数组中新的小时数,而分钟不变,当指针大于等于4的时候,就是在分钟里取,所以分钟要加上数组中新的分钟数,而小时不变。而num是一直在递减的。当小时大于11或者分钟大于59时,直接return,这是递归的结束条件。
private int[] all = {1,2,4,8,1,2,4,8,16,32};
public List<String> readBinaryWatch3(int num) {
List<String> list = new ArrayList<String>();
helperFun(list, num, 0, 0, 0);
return list;
}
void helperFun(List<String> list, int num, int hour, int minute, int index) {
if (hour > 11 || minute > 59) {
return;
}
if (num == 0) {
String answer = "";
if (minute < 10) {
answer = hour + ":0" + minute;
} else {
answer = hour + ":" + minute;
}
list.add(answer);
}
for (int i=index; i<10; i++) {
if (i < 4) {
helperFun(list, num-1, hour+all[i], minute, i+1);
} else {
helperFun(list, num-1, hour, minute+all[i], i+1);
}
}
}
05 小结
算法专题目前已连续日更超过两个月,算法题文章84+篇,