Heuristic solution win.


  • 0
    H

    This is one of those problems should be solved in "heuristic" way.

    The key idea is that there is a maximum value for each position:

    1. if the first digit is 0 or 1: Max = 19:59
    2. if the first digit is 2: Max = 23:59

    When we get a time for example 14:39, sort it first -> [1,3,4,9],than just try to replace one digit by a greater value,ex: 14:39 -> 14:49, and fill the rest with the smallest digit, ex: 14:49 -> 14:41

            public String nextClosestTime(String time) {
                char[] charTime = time.toCharArray();   // [1, 9, :, 3, 4]
                char[] nums = Arrays.copyOf(charTime,charTime.length);
                Arrays.sort(nums);                      // [1, 3, 4, 9, :]
                /** the carry */
                int i = 0;
                outFor:
                for (i = 4; i >= 0; i--) {
                    if (i == 2) { continue; } // skip ":" in the middle
                    char c = charTime[i];
                    int next = 0;
                    while (next < 4 && nums[next] <= c) { next++; }
                    // maximum legal value
                    char max = '9';
                    switch (i) {
                        case 3: max = '5'; break;
                        case 1: if (charTime[0] == '2') { max = '4'; } break;
                        case 0: max = '2'; break;
                    }
                    if (next == 4 || nums[next] > max) { continue outFor; }
                    charTime[i] = nums[next];
                    break;
                }
                /** fill the remainder with smallest digit */
                for (int j = i + 1; j <= 4; j++) {
                    if (j == 2) { continue; }
                    charTime[j] = nums[0]; // at least one of [0,1,2]
                }
                return new String(charTime);
            }
    

Log in to reply
 

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