文档章节

读二进制表的显示 Binary Watch

叶枫啦啦
 叶枫啦啦
发布于 2017/08/16 14:57
字数 872
阅读 5
收藏 0

问题:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.(输入亮几个灯,输出可能的时间)

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
  • The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

解决:

【注】

关于回溯法https://segmentfault.com/a/1190000006121957#articleHeader0

① 使用回溯的思想,分别在小时和分钟上做DFS(DFS可以看作是回溯的一种),给定几个灯亮,然后把这些亮的灯枚举分给小时和分钟.需要注意的是剪枝,即小时必须小于12,分钟小于60.然后将小时和分钟组合即可.还有一个需要注意的是如果分钟只有1位数,还要补0。

public class Solution { // 3ms
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for (int i = Math.max(0,num - 6);i <= Math.min(4,num) ;i ++ ) {
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            DFS(4,i,0,0,list1);
            DFS(6,num - i,0,0,list2);
            for (int n1 : list1) {
                for (int n2 : list2)
{
                    String str = (String.valueOf(n2).length() == 1 ? "0" : "") + String.valueOf(n2);
                    res.add(String.valueOf(n1) + ":" + str);
                }
            }
        }
        return res;
    }
    public void DFS(int len,int k,int curIndex,int val,List<Integer> list){
        if(k == 0 && len == 4 && val < 12) list.add(val);
        if(k == 0 && len == 6 && val < 60) list.add(val);
        if(curIndex == len || k == 0) return; //停止条件
        DFS(len,k,curIndex + 1,val,list);
        val += Math.pow(2,curIndex);//计算第curIndex代表的值
        k --;
        curIndex ++;
        DFS(len,k,curIndex,val,list); //
    }
}

② 在discuss中看到,将所有的小时和分钟的可能性用数组列出来,以空间换时间,耗时少。

public class Solution { //2ms
        String[][] hour = {{"0"},  // hours contains 0 1's
                   {"1", "2", "4", "8"},   // hours contains 1 1's
                   {"3", "5", "6", "9", "10"},  // hours contains 2 1's
                   {"7", "11"}};  // hours contains 3 1's
        String[][] minute = {{"00"},  // mins contains 0 1's
                         {"01", "02", "04", "08", "16", "32"},  // mins contains 1 1's
                         {"03", "05", "06", "09", "10", "12", "17", "18", "20", "24", "33", "34", "36", "40", "48"},  // mins contains 2 1's
                         {"07", "11", "13", "14", "19", "21", "22", "25", "26", "28", "35", "37", "38", "41", "42", "44", "49", "50", "52", "56"},  // mins contains 3 1's
                         {"15", "23", "27", "29", "30", "39", "43", "45", "46", "51", "53", "54", "57", "58"},  // mins contains 4 1's
                         {"31", "47", "55", "59"}};  // mins contains 5 1's  
                     
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList();
         // loop from 0 to 3 which is the max number of bits can be set in hours (4 bits)
        for (int i = 0; i <= 3 && i <= num; i++) { 
            // this if condition is to make sure the index from minutes array would be valid
            if (num - i <= 5) {
                // if we have i 1's in hours, then we need num - i 1's in minutes, that's why the arrays were created by grouping the number of 1's bits
                for (String str1 : hour[i]) {
                    for (String str2 : minute[num - i]) {
                        res.add(str1 + ":" + str2);
                    }
                }
            }
        }
        return res;     
    }
}

使用Bit Manipulation来解决,1,2,4,8都是2的整数倍,它们的二进制都只包含一个1,所以搜索所有的解空间,看哪几个数的bit之和等于num。使用Integer.bitCount()来计算1的个数,这个方法既好理解,又好使用。

public class Solution { // 3ms                  
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for (int h = 0;h < 12 ;h ++ ) {
            for (int m = 0;m < 60 ;m ++ ) {
                if(Integer.bitCount(h) + Integer.bitCount(m) == num){
                    String str1 = Integer.toString(h);
                    String str2 = Integer.toString(m);
                    res.add(str1 + ":" + (m < 10 ? "0" + str2 : str2));
                }
            }
        } 
        return res;
    }
}

 

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 583
码字总数 400448
作品 0
海淀
私信 提问
【LeetCode】401 Binary Watch (java实现)

原题链接 https://leetcode.com/problems/binary-watch/ 原题 A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minu......

BookShu
2016/10/21
405
0
也谈文本文件与二进制文件

网上关于文本文件与二进制文件的文章很多,但遗憾的是,这些文章讲得都比较 散。下面我将结合所查到的资料,从多个角度谈谈文本文件与二进制文件。 一、文本文件与二进制文件的定义 大家都知...

长平狐
2012/09/03
231
0
那些年的坑--双精度数值转成整形

关于语言内置类型的转换,平时写代码都是直接强转,有显式的,有隐式,一般都是不会出现问题。但是,这次确是遇到了一个问题,具体原有还是跟浮点数使用二进制表示法有关,有些数很难直接表示...

ikel
2016/07/07
29
0
二进制加法

原题   Given two binary strings, return their sum (also a binary string).   For example,   a =   b =   Return 题目大意   给定两个二进制的字符串,返回它们的和,也是二...

一贱书生
2016/12/16
12
0
二进制、字节、16进制

1.二进制就是逢二进一,只有0和1。 一个字节就是一个英文字母、阿拉伯数字或半个汉字所占的空间(一个汉字占2个字节)。 16进制就是逢16进一,只有0123456789abcdef这16个数字(或子母)。 ...

87305931
2014/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部