Java Back Track and Bit Shift Operation Solution


  • 0
    E

    Java Back Track and Bit Shift Operation Solution.

    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> res = new ArrayList();
            if(num>10){  // 4 (hours leds) + 6 (minute leds)
                return res;
            }
            
            for (int i=0; i<=4; i++){
                int hL = i;
                int mL = num-i;
                
                if(mL>6){
                    continue;
                }else if(mL<0){
                    break; //no longer valid, so break here
                }
                
                //generate all possible digis
                ArrayList<Integer> hours = new ArrayList();
                ArrayList<Integer> minutes = new ArrayList();
                
                getValue(4, 0, hL, 0, hours, 11);
                getValue(6, 0, mL, 0, minutes, 59);
                
                for(int hour: hours){
                    for(int minute: minutes){
                        if(minute<10){
                            res.add(hour+":0"+ minute);
                        }else{
                            res.add(hour+":"+ minute);
                        }
                    }
                }
            }
            return res;
        }
        
        /**
         * Use back track and bit shifting to generate digis 
         *
         * when curIndex ==0, it means the right most digi
         * the LED light can be on at any digi from 0 to 3 (which means 1 at the digi)
         * 
         * When curIndex = 1, it means the second right most digi
         * the LED light can be on at any digi from 1 to 3 
         * 
         * 
         * **/
         
        private void getValue(int digis, int curIndex, int leds, int curValue, List<Integer> res, int max){
            if(leds==0){
                //add the result
                if(curValue<=max){
                    res.add(curValue);
                }
                return;
            }else if(curIndex>=digis){
                return; // not valid any more
            }
            
            int backup = curValue;
            //backtrack
            for(int i=curIndex; i<digis; i++){
                curValue = curValue | (1<<i); //turn on led at index 'i' and shift to left
                getValue(digis, i+1, leds-1, curValue, res, max);
                curValue = backup; //backtrack
            }
        }
    }
    

Log in to reply
 

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