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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！