Java brute force


  • 0
    F

    Enumerate all possible times
    WA once for the corner case "00:00", "11:11"...

        List<int[]> getDigits(int[]digits){
            List<int[]>ans=new ArrayList<>();
            for (int i = 0;i<256;++i){
                int[] clone=new int[4];
                int n=i;
                for (int j=0;j<4;++j) {
                    clone[j] = digits[n%4];
                    n/=4;
                }
                ans.add(clone);
            }
            return ans;
        }
        int toMinutes(int[] digits){
            int hours=digits[0]*10+digits[1];
            if (hours>23)return -1;
            int minutes=digits[2]*10+digits[3];
            if (minutes>59)return -1;
            return hours*60+minutes;
        }
    
        public String nextClosestTime(String time) {
            int[] digits={time.charAt(0)-'0', time.charAt(1)-'0', time.charAt(3)-'0',time.charAt(4)-'0'};
            int minutes=toMinutes(digits);
            int min=Integer.MAX_VALUE;
            int[]best=null;
            for (int[] next: getDigits(digits)){
                int minutes2=toMinutes(next);
                if (minutes2==-1)continue;
                int delta=minutes2-minutes;
                // ** NOTE: must be <=, otherwise got null for case "00:00" **
                if (delta<=0)delta+=1440;
                if (delta<min){
                    min=delta;
                    best=next;
                }
            }
            return String.format("%d%d:%d%d", best[0],best[1],best[2],best[3]);
        }
    

  • 0
    B

    yeah I was thinking of changing least significant digit one by one solution but since there's only 4 * 4 * 4 * 4 possible outcome brute force makes sense to me.
    here is mine:

        public String nextClosestTime(String time) {
            
            int[] digits = {time.charAt(0) - '0', time.charAt(1) - '0', time.charAt(3) - '0', time.charAt(4) - '0'};
            
            int min = Integer.MAX_VALUE;
            
            int timeInMin = timeInMin(digits[0], digits[1], digits[2], digits[3]);
            String ret = "";
            
            for (int i : digits)
                for (int j : digits)
                    for (int k : digits)
                        for (int l : digits)
                            if ((i*10 + j) >= 0 && (i*10 + j) < 24 && (k * 10 + l) >= 0 && (k * 10 + l) < 60){//(i, j, k, l) forms valid time
                                
                                int temp = timeInMin(i, j, k, l);
                                
                                if (temp <= timeInMin)
                                    temp += 24*60;//going 1 day forward
                                
                                if (temp - timeInMin < min){
                                    min = temp - timeInMin;
                                    ret = "" + i + j + ":" + k + l;
                                }
                            }
                            
            return ret;
        }
        private int timeInMin(int d0, int d1, int d2, int d3){
            return (d0*10 + d1)*60 + (d2*10 + d3);
        }
    

Log in to reply
 

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