Slow Java sloution, 141ms, DFS


  • 0
    S

    I found this solution slower than expected, Might caused by the List copying. I think if I can represent the lists of bits locations in a integer might make it faster. This improvement may need to count bits, or deliver the bits count in another parameter.

        public List<String> readBinaryWatch(int num) {
            Set<String> rts = new HashSet<>();
            search(rts, new ArrayList<>(), num, 0);
            return new ArrayList<>(rts);
        }
    
        public void search(Set<String> rts, List<Integer> idxs, int num, int id) {
            if (idxs.size() == num) {
                int h = 0;
                int m = 0;
                for (int i : idxs) {
                    if (i < 4) {
                        h |= 1 << i;
                    } else {
                        m |= 1 << i - 4;
                    }
                }
                if (h < 12 && m < 60) rts.add(h + ":" + String.format("%02d", m));
                return;
            }
            if (id >= 10) return;
            List<Integer> idxsClone1 = new ArrayList<>(idxs);
            List<Integer> idxsClone2 = new ArrayList<>(idxs);
            idxsClone2.add(id);
            id++;
            search(rts, idxsClone1, num, id);
            search(rts, idxsClone2, num, id);
        }

Log in to reply
 

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