Java DFS bottom-up solution


  • 0
    D
    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> ret = new ArrayList<>();
            assert num >= 0;
            for (int hourLEDs = 0; hourLEDs <= num; hourLEDs++) {
                List<Integer> hourList = dfs(11, 8, 0, 0, hourLEDs, 4);
                List<Integer> minuteList = dfs(59, 32, 0, 0, num - hourLEDs, 6);
                for (int hourNum : hourList) {
                    for (int minuteNum : minuteList) {
                        ret.add(String.format("%d:%02d", hourNum, minuteNum));
                    }
                }
            }
            return ret;
        }
    
        private List<Integer> dfs(int uplim, int nowVal, int level, int chosenleds, int activeleds, int allleds) {
            List<Integer> ret = new ArrayList<>();
            if (activeleds == 0 || chosenleds == activeleds) {
                ret.add(0);
                return ret;
            }
            if (allleds - level < activeleds - chosenleds) {
                return ret;
            }
            List<Integer> possible1 = dfs(uplim, nowVal / 2, level + 1, chosenleds, activeleds, allleds);
            List<Integer> possible2 = dfs(uplim, nowVal / 2, level + 1, chosenleds + 1, activeleds, allleds);
            ret.addAll(possible1);
            for (int choice : possible2) {
                if (nowVal + choice <= uplim) {
                    ret.add(nowVal + choice);
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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