Easy Understand Java Code


  • 0
    R

    We divide n into two parts. One part is used for hour, the other part is used for minute.
    And we use backtracking to solve this problem.

    import java.util.ArrayList;
    import java.util.List;
    
    public class Solution {
        int[] minute = new int[]{1, 2, 4, 8, 16, 32};
        int[] hour = new int[]{1, 2, 4, 8};
        public List<String> readBinaryWatch(int num) {
            List<String> ret = new ArrayList<String>();
            if (num < 0) {
                return ret;
            }
            
            for (int i = 0; i <= 3 && i <= num; i++) {
                List<String> hours = helper(i, hour, true);
                List<String> minutes = helper(num - i, minute, false);
                for (String h : hours) {
                    for (String m : minutes) {
                        ret.add(h + ":" + m);
                    }
                }
            }
            
            return ret;
        }
        
        private List<String> helper(int n, int[] nums, boolean isHour) {
            List<String> ret = new ArrayList<String>();
            if (n <= 0) {
            	if (isHour) {
            		ret.add("0");
            	}
            	else {
            		ret.add("00");
            	}
            	return ret;
            }
            if (isHour) {
            	dfs(0, n, nums, 0, ret, 12);
            }
            else {
            	dfs(0, n, nums, 0, ret, 60);
            }
            return ret;
        }
        
        private void dfs(int begin, int n, int[] nums, int sum, List<String> ret, int max) {
            if (begin >= nums.length) {
                if (n == 0 && sum < max) {
                	String temp = String.valueOf(sum);
                	if (temp.length() == 1 && max == 60) {
                		temp = "0" + temp;
                	}
                    ret.add(temp);
                }
                return;
            }
            else {
                int curr = nums[begin];
                dfs(begin + 1, n - 1, nums, sum + curr, ret, max);
                dfs(begin + 1, n, nums, sum, ret, max);
            }
        }
    }
    

Log in to reply
 

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