401. 二进制手表

àì夳堔傛蜴生んèń 2022-10-08 13:29 266阅读 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