bfs beat 96%


  • 0
    F
     // 4 ,6 
        public List<String> readBinaryWatch(int num) {
            List<String> res = new ArrayList<>();
            if (num > 10) return res; 
            for (int i = Math.max(0, num-6); i <= Math.min(num, 4); i++) {
                List<String> resh = new ArrayList<>();
                List<String> resm = new ArrayList<>();
                dfs(0, i, 4, 0, resh, 1);
                dfs(0, num-i, 6, 0, resm, 1);
                for (String sh: resh) {
                    for (String sm: resm) {
                        if(sm.length() < 2) sm = "0"+sm;
                        res.add(sh+":"+sm);
                    }
                }
            }
            return res;
        }
        void dfs(int pos, int step, int total, int val, List<String> res, int base) {
            if (step == 0) {
                if (total == 4 && val >= 12 || total == 6 && val >= 60) return;
                res.add(Integer.toString(val));
                return;
            }
            for (int i = pos; i+step <= total; i++) {
                dfs(i+1, step-1, total, val+base, res, base*2);
                base *= 2;
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.