題目

二進制手表頂部有 4 個 LED 代表 小時（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

1. 遍歷0-59，使用map記錄二進制中1的個數和對應分鐘的映射，
2. 遍歷0-11，計算當前小時對應的元素已經占用了多少個1，記作cur，那么分鐘只能有turnedOn-cur個1，使用map可以快速找出二進制表示中1的個數為turnedOn-cur的分鐘數，再進行組合。

代碼

class Solution {public List<String> readBinaryWatch(int turnedOn) {List<String> res=new ArrayList<>();Map<Integer,List<Integer>> min=new HashMap<>();for (int i=0;i<60;i++){int cur=Integer.bitCount(i);if(!min.containsKey(cur))min.put(cur,new ArrayList<>());min.get(cur).add(i);}for (int i=0;i<=11;i++){int cur=Integer.bitCount(i);if(cur>=4||!min.containsKey(turnedOn-cur))continue;List<Integer> 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;}
}