首页 > 代码库 > 401. Binary Watch

401. Binary Watch

其实不太懂为什么这道题会标成easy…………感觉分明是combination的升级版嘛

思路就是因为最多会形成6个灯的,所以从0-6生成所有可能的binary组合然后分开组合

 

 1     public List<String> readBinaryWatch(int num) {
 2         List<String> res = new ArrayList<>();
 3         if(num < 0) {
 4             return res;
 5         }
 6         Map<Integer, List<String>> map = new HashMap<>();
 7         for(int i = 0; i <= num; i++) {
 8             char[] cur = new char[6];
 9             Arrays.fill(cur, ‘0‘);
10             List<String> curRes = new ArrayList<>();
11             generate(curRes, 0, 0, i, cur);
12             map.put(i, curRes);
13         }
14         for(int i = 0; i <= num && i <= 4; i++) {
15             List<String> hour = map.get(i);
16             List<String> min = map.get(num - i);
17             for(String h: hour) {
18                 int hourInt = Integer.parseInt(h, 2);
19                 if(hourInt >= 12) {
20                     continue;
21                 }
22                 for(String m: min) {
23                     int minInt = Integer.parseInt(m, 2);
24                     if(minInt >= 60) {
25                         continue;
26                     }
27                     StringBuilder sb = new StringBuilder();
28                     sb.append(hourInt);
29                     sb.append(‘:‘);
30                     if(minInt <= 9) {
31                         sb.append(‘0‘);
32                     }
33                     sb.append(minInt);
34                     res.add(sb.toString());
35                 }
36             }
37         }
38         return res;
39     }
40     
41     private void generate(List<String> res, int index, int cnt, int n, char[] cur) {
42         if(cnt == n) {
43             res.add(new String(cur));
44             return;
45         }
46         for(int i = index; i < 6; i++) {
47             cur[i] = ‘1‘;
48             generate(res, i + 1, cnt + 1, n, cur);
49             cur[i]  = ‘0‘;
50         }
51     }

 

401. Binary Watch