Backtracking + Bit Manipulate Java Solution


  • 1
    J
    public class Solution {
        private void rec(int ret, List<Integer> ans, int cnt, int limit, int start) {
            int hh = (ret & 15);
            int mm = (ret >> 4);
            if(hh >= 12 || mm >= 60) {
                return;
            }
            if(cnt == 0) {
                //System.out.println(ret);
                ans.add(ret);
                return;
            }
            
            for(int i = start; i < limit; i ++) {
                if((ret & (1 << i)) == 0) {
                    rec(ret | (1 << i), ans, cnt-1, limit, i + 1);
                }
            }
        }
        
        private String convert(int input) {
            String h = String.valueOf(input & 15);
            String m = String.valueOf(input >> 4);
            return h + ":" + (m.length() == 1 ? ("0" + m) : m);
        }
        
        private List<String> convert(List<Integer> input) {
            List<String> ret = new ArrayList<>();
            for(int n : input) {
                ret.add(convert(n));
            }
            return ret;
        }
        
        public List<String> readBinaryWatch(int num) {
            List<Integer> ans = new ArrayList<>();
            rec(0, ans, num, 10, 0);
            //System.out.println(ans);
            return convert(ans);
        }
    }
    

    Use the first 10 bit of an integer to represent the watch.
    The first 4 bits are the hour
    The second 6 bits are minutes

    Then feed the number to a very standard backtracking recursion.

    Several things to notice:

    1. You have to make sure the generated number is a valid time in watch 16:61 is not acceptable.
    2. Make sure the backtracking will not generate duplicated number. I use a start var to de-dup.

    Problem Solved.


Log in to reply
 

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