LeetCode 401 二进制手表
二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)。
每个 LED 代表一个 0 或 1,最低位在右侧。
例如,上面的二进制手表读取 “3:25”。
给定一个非负整数 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”。
public class Solution {
List<Time> listTime = null;
private static class Time {
int type;
int time;
Time(int type, int time) {
this.type = type;
this.time = time;
}
}
public Solution() {
listTime = new ArrayList<>();
//1、初始化小时
listTime.add(new Time(1, 1));
listTime.add(new Time(1, 2));
listTime.add(new Time(1, 4));
listTime.add(new Time(1, 8));
//2、初始化分钟
listTime.add(new Time(2, 1));
listTime.add(new Time(2, 2));
listTime.add(new Time(2, 4));
listTime.add(new Time(2, 8));
listTime.add(new Time(2, 16));
listTime.add(new Time(2, 32));
}
public List<String> readBinaryWatch(int num) {
//1、建立返回链表
List<String> list = new LinkedList<>();
//2、dfs
dfs(list, 0, num, new LinkedList<Time>());
return list;
}
private void dfs(List<String> list, int index, int end, LinkedList<Time> dempList) {
//1、结束
if (dempList.size() == end) {
String s = makeTime(dempList);
if (s != null) {
list.add(s);
}
return;
}
//2、dfs
for (int i = index; i < listTime.size(); i++) {
dempList.addLast(listTime.get(i));
dfs(list, i + 1, end, dempList);
dempList.removeLast();
}
}
/**
* 功能描述 制作时间
*/
private static String makeTime(LinkedList<Time> dempList) {
//1、初始化时间
int hour = 0;
int minute = 0;
Iterator<Time> iterator = dempList.iterator();
//2、遍历时间链表
while (iterator.hasNext()) {
Time time = iterator.next();
if (time.type == 1) {
hour = hour + time.time;
} else if (time.type == 2) {
minute = minute + time.time;
}
}
//3、统计
if (hour > 11 || minute > 59) {
return null;
} else {
String str = null;
if (minute == 0 && hour != 0) {
str = hour + ":00";
} else if (hour == 0 && minute != 0) {
if (minute >= 10) {
str = "0:" + minute;
} else {
str = "0:0" + minute;
}
} else {
if (minute >= 10) {
str = hour + ":" + minute;
} else {
str = hour + ":0" + minute;
}
}
return str;
}
}
}