Binary Watch

对这种问题总有恐惧感, 几个注意点点

• 开始的时候想到了要divede&concur, 分别求出对应的小时和分钟时间

• 求时间的时候卡住了, 忘记怎么从K个数里选n个组成数字, 这类问题就是 递归+permutation 问题

• 犯错1: 枚举小时bit从1开始, 应该从0开始

• 犯错2: 小时和时间求出来的list需要collection.sort

• 犯错3: 格式 String.format("%d:%02d", h, s)

• 特殊情况: n==0时，"0:00"

• public class Solution {
      public List<String> readBinaryWatch(int num) {
          List<String> list = new ArrayList<String>();
          if(num==0){
              list.add("0:00");
              return list;
          }
          int[] hlist = {1,2,4,8};
          int[] minlist = {1,2,4,8,16,32};
          for(int i=0;i<=4;i++){
              if(num-i>6) continue;
              List<Integer> hours = new ArrayList<Integer>();
              List<Integer> mins = new ArrayList<Integer>();
              gettime(hlist,i,0, 0, hours);
              gettime(minlist,num-i,0, 0, mins);
              Collections.sort(hours);
              Collections.sort(mins);
              for(Integer h : hours)
                  for(Integer s : mins)
                      list.add(String.format("%d:%02d", h, s));
          }
          return list;
      }
  
      public void gettime(int[] hlist, int remain, int idx, int cur, List<Integer> list){
          if(idx>hlist.length||remain<0) return;
          if(remain==0){
              list.add(cur);
              return;
          }
  
          for(int i=idx;i<hlist.length;i++){
              gettime(hlist, remain-1, i+1, cur+hlist[i], list); 
          }
      }
  
  }
  

LC论坛大神解法, 10行内搞定, 面试这么用太生硬.