(G) Binary Watch

http://www.1point3acres.com/bbs/thread-141438-1-1.html

题目是binary watch：上边是小时，下边是分钟，最左边最significant，最右边为1。给你数字n，return所有可能的时间，以string为表达形式.

E.G. 给你1,那return:{0:00,1:00,2:00,4:00,8:00,0:01.........}

这题挺简单的，就是一个简单位运算和 mask + dfs 枚举。

• 0x12345678 的 hex-decimal 表示方式中，一个数代表 4 bit，0-9 a-f 总共代表 16 个数；

• 位数不到 8 个的说明前面默认都是 0；

• 0x0000003f = 0000 0000 ...0011 1111，最后一个位段是 1111 = f，前面那个 0011 = 3;

• 为了避免重复，进一步剪枝，这题要像 combination 一样传一个 index ，单调往后扫。

    public static List<String> binaryWatch(int n) {
        List<String> list = new ArrayList<>();
        dfs(list, n, 0, 0);
        return list;
    }

    public static void dfs(List<String> rst, int n, int num, int index){
        if(n == 0){
            int minutes = num & (0x0000003f);
            int hours = num >> 6;

            if(hours < 24 && minutes < 60) rst.add("" + hours + ":" + minutes);

            return;
        }

        for(int i = index; i < 10; i++){
            if((num & (1 << i)) == 0){
                dfs(rst, n - 1, num + (1 << i), index + 1);
            }
        }
    }

    public static void main(String[] args){
        List<String> list = binaryWatch(1);

        for(String str : list){
            System.out.println(str);
        }
        System.out.println(list.size() + " Answers.");
    }