401. 二进制手表 àì夳堔傛蜴生んèń 2022-10-08 13:29 119阅读 0赞 #### 2021-06-21 LeetCode每日一题 #### 链接:[https://leetcode-cn.com/problems/binary-watch/][https_leetcode-cn.com_problems_binary-watch] 标签:**位运算、回溯** > 题目 二进制手表顶部有 4 个 LED 代表 小时(0-11),底部的 6 个 LED 代表 分钟(0-59)。每个 LED 代表一个 0 或 1,最低位在右侧。 例如,下面的二进制手表读取 “3:25” 。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70] (图源:WikiMedia - Binary clock samui moon.jpg ,许可协议:Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) ) 给你一个整数 turnedOn ,表示当前亮着的 LED 的数量,返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。 小时不会以零开头: * 例如,“01:00” 是无效的时间,正确的写法应该是 “1:00” 。 分钟必须由两位数组成,可能会以零开头: * 例如,“10:2” 是无效的时间,正确的写法应该是 “10:02” 。 输入:turnedOn = 1 输出:["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"] 输入:turnedOn = 9 输出:[] **提示:** * `0 <= turnedOn <= 10` > 分析 此题既然标为简单题,tag却是回溯,十分不合理,连官方题解都没有提及回溯算法。 ![在这里插入图片描述][20210621220831262.jpg] 这里可以换个思路,那就是计算时和分加起来总共有几个灯亮(即有几个1),如果个数等于turnedOn,那就是一个结果。因为数字不是很大,所以可以暴力。 对于一个数n,n & (n - 1),会让n最低位的1变成0。比如n = 10(1010),n - 1 = 9(1001),那么n & (n - 1)就等于8(1000)。而8 & 7 = 1000 & 0111 = 0000,所以利用此特性,可以快速得到n表示的二进制有几个1。 Java有现成的API可以调用Integer.bitCount(),这里只是讲一下过程。 > 编码 class Solution { public List<String> readBinaryWatch(int turnedOn) { List<String> list = new ArrayList<>(); for (int i = 0; i < 12; i++) { for (int j = 0; j < 60; j++) { if (countBit(i) + countBit(j) == turnedOn) { list.add(i + ":" + (j < 10 ? ("0" + j) : j)); } } } return list; } /** * 计算num表示的二进制有几个1 */ private int countBit(int num) { int count = 0; while (num != 0) { num = num & (num - 1); count++; } return count; } } ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70 1] [https_leetcode-cn.com_problems_binary-watch]: https://leetcode-cn.com/problems/binary-watch/ [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]: /images/20221005/cb1028d9901a48c1aff3e484f213eb0e.png [20210621220831262.jpg]: /images/20221005/e17f95702d2b46f4b331db0073499767.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70 1]: /images/20221005/c126a91241434816b6105fccd0cc906f.png
还没有评论,来说两句吧...