二进制手表
题目
二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n代表当前 LED 亮着的数量，返回所有可能的时间。
案例:
image
输入: 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”。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
- 思路一
- 可以将小时和分钟重复遍历,找出当前时间点对应的二进制位有多少个1,此时就是符合条件的,输出即可.
- 思路二
- 领扣上看到的,将上下两个表盘的所有可能性列出.然后根据传入的num来依次判断,最后输出
代码
class Solution {
public List<String> readBinaryWatch(int num) {
//要计算所有的可能性,可以将小时和分钟的所有可能做循环,然后将当前点数的二进制值相加看有几个1,如果符合num,则对应输出时间
List<String> result = new ArrayList<>();
for(int i = 0;i < 12;i++){
for(int h = 0;h < 60;h++){
if((getNumForOne(i) + getNumForOne(h)) == num){
String hString = h<10?"0"+h:h+"";
result.add(i+":"+hString);
}
}
}
return result;
}
private int getNumForOne(int n){
int sum = 0;
for(int i = 0;i < 32;i++){
if((1&(n>>i)) == 1){
sum++;
}
}
return sum;
}
}
枚举法
class Solution {
public List<String> readBinaryWatch(int num) {
if (num > 8) {
return new ArrayList<>();
}
String[] topZero = new String[]{"0"};
String[] topOne = new String[]{"1", "2", "4", "8"};
String[] topTwo = new String[]{"3", "5", "9", "6", "10"};
String[] topThree = new String[]{"7","11"};
String[] endZero = new String[]{":00"};
String[] endOne = new String[]{":01", ":02", ":04", ":08", ":16", ":32"};
String[] endTwo = new String[]{
":03", ":05", ":09", ":17", ":33",
":06", ":10", ":18", ":34",
":12", ":20", ":36",
":24", ":40",
":48"};
String[] endThree = new String[]{
":07", ":11", ":19", ":35",
":13", ":21", ":37",
":25", ":41",
":49",
":14", ":22", ":38",
":26", ":42",
":50",
":28", ":44",
":52",
":56"};
String[] endFour = new String[]{
":58", ":54", ":46", ":30",
":57", ":53", ":45", ":29",
":51", ":43", ":27",
":39", ":23",
":15"};
String[] endFive = new String[]{":59", ":55", ":47", ":31"};
List<String> result = new ArrayList<>();
int hour = 0, minute = num - hour;
while (hour < 4 && minute >= 0) {
if (minute > 5) {
hour++;
minute = num - hour;
continue;
}
String[] hourStr, minuteStr;
switch (hour) {
case 0: hourStr = topZero;break;
case 1: hourStr = topOne;break;
case 2: hourStr = topTwo;break;
case 3: hourStr = topThree;break;
default: hourStr = topZero;break;
}
switch (minute) {
case 0: minuteStr = endZero;break;
case 1: minuteStr = endOne;break;
case 2: minuteStr = endTwo;break;
case 3: minuteStr = endThree;break;
case 4: minuteStr = endFour;break;
case 5: minuteStr = endFive;break;
default: minuteStr = endZero;break;
}
sum(result,hourStr,minuteStr);
hour++;
minute = num - hour;
}
return result;
}
private static void sum(List<String> result, String[] hour, String[] minute) {
for (String h : hour) {
for (String m : minute) {
result.add(h+m);
}
}
}
}
网友评论