网站仿制公司,底部版权wordpress,代推广平台,金融公司网站建设模板题目
二进制手表顶部有 4 个 LED 代表 小时#xff08;0-11#xff09;#xff0c;底部的 6 个 LED 代表 分钟#xff08;0-59#xff09;。每个 LED 代表一个 0 或 1#xff0c;最低位在右侧。
例如#xff0c;下面的二进制手表读取 “3:25” 。 #xff08;图源0-11底部的 6 个 LED 代表 分钟0-59。每个 LED 代表一个 0 或 1最低位在右侧。
例如下面的二进制手表读取 “3:25” 。 图源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” 。
示例 1
输入turnedOn 1 输出[“0:01”,“0:02”,“0:04”,“0:08”,“0:16”,“0:32”,“1:00”,“2:00”,“4:00”,“8:00”] 示例 2
输入turnedOn 9 输出[]
提示
0 turnedOn 10
解题思路
时间由两个部分组成
小时0-11分钟0-59 手表当前亮着的 LED 的数量可以看成是二进制表示中1的个数 因此使用两个二进制数分别表示小时和分钟它们二进制表示中的1的个数等于turnedOn
遍历0-59使用map记录二进制中1的个数和对应分钟的映射遍历0-11计算当前小时对应的元素已经占用了多少个1记作cur那么分钟只能有turnedOn-cur个1使用map可以快速找出二进制表示中1的个数为turnedOn-cur的分钟数再进行组合。
代码
class Solution {public ListString readBinaryWatch(int turnedOn) {ListString resnew ArrayList();MapInteger,ListInteger minnew HashMap();for (int i0;i60;i){int curInteger.bitCount(i);if(!min.containsKey(cur))min.put(cur,new ArrayList());min.get(cur).add(i);}for (int i0;i11;i){int curInteger.bitCount(i);if(cur4||!min.containsKey(turnedOn-cur))continue;ListInteger mi min.get(turnedOn-cur);for (int k 0; k mi.size(); k) {res.add(String.format(%d:%02d,i,mi.get(k)));}}return res;}
}
