LeetCode算法题-Binary Watch(Java实现)

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+篇,