Easy Understand JAVA Solution with Extra WatchItem Class


  • 1
    M

    I created a class to get clear thought when solve the problem. The binary watch is actually a array consists of several WatchItem, which contains two attribute: count (int), and type (char).

    Then I just use DFS to pick up k items from the watch, and take them out to calculate the total time and transform to a string.

    There are several corner you need to consider in this problem:

    1. any hour and min greater than 11 and 59 is invalid
    2. min should contains 2 digits
        public static class WatchItem{
    	int count;
    	char type;
    	public WatchItem(int c, char t){
    		this.count = c;
    		this.type = t;
    	}
    }
    
    public static List<String> readBinaryWatch(int num) {
        WatchItem[] watch = new WatchItem[10];
        watch[0] = new WatchItem(1, 'h');
        watch[1] = new WatchItem(2, 'h');
        watch[2] = new WatchItem(4, 'h');
        watch[3] = new WatchItem(8, 'h');
        
        watch[4] = new WatchItem(1, 'm');
        watch[5] = new WatchItem(2, 'm');
        watch[6] = new WatchItem(4, 'm');
        watch[7] = new WatchItem(8, 'm');
        watch[8] = new WatchItem(16, 'm');
        watch[9] = new WatchItem(32, 'm');
    	
        
        List<String> res = new LinkedList<String>();
        List<WatchItem> tmpRes = new LinkedList<WatchItem>();
        pickNumsOptions(num, watch, res,tmpRes);
        
        return res;
    }
    
    private static void pickNumsOptions(int num, WatchItem[] watch, List<String> res,
    		List<WatchItem> tmpRes) {
    	
    	if(tmpRes.size() == num){
    		//transform and add to res
    		String time = transformTime(tmpRes);
    		if(time!=null && !res.contains(time))
    			res.add(time);
    		return;
    	}
    	
    	for(int i=0;i<watch.length;i++){
    		if(tmpRes.contains(watch[i])){
    			continue;
    		}
    		tmpRes.add(watch[i]);
    		pickNumsOptions(num, watch, res, tmpRes);
    		tmpRes.remove(tmpRes.size()-1);
    	}
    	
    	return;
    }
    
    public static String transformTime(List<WatchItem> items){
    	int hour = 0;
    	int min = 0;
    	String resMin = "";
    	for(WatchItem item : items){
    		if(item.type == 'h'){
    			hour += item.count;
    		}
    		else if(item.type == 'm'){
    			min += item.count;
    		}
    	}
    	
    	if(hour>=12 || min>=60){
    		return null;
    	}
    	
    	if(min/10 == 0){
    		resMin = "0"+String.valueOf(min);
    	}
    	else{
    		resMin = String.valueOf(min);
    	}
    	return String.valueOf(hour) +":"+resMin;
    	
    }

Log in to reply
 

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