You are given a string time
in the form of hh:mm
, where some of the digits in the string are hidden (represented by ?
).
The valid times are those inclusively between 00:00
and 23:59
.
Return the latest valid time you can get from time
by replacing the hidden digits.
Example 1:
Input: time = "2?:?0" Output: "23:50" Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.
Example 2:
Input: time = "0?:3?" Output: "09:39"
Example 3:
Input: time = "1?:22" Output: "19:22"
Constraints:
time
is in the formathh:mm
.- It is guaranteed that you can produce a valid time from the given string.
Solution 1: Brute Force
Enumerate all possible clock in reverse order and find the first matching one.
Time complexity: O(1)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: string maximumTime(string time) { for (int m = 60 * 24 - 1; m >= 0; --m) { int hh = m / 60; int mm = m % 60; if (time[0] != '?' && time[0] - '0' != hh / 10) continue; if (time[1] != '?' && time[1] - '0' != hh % 10) continue; if (time[3] != '?' && time[3] - '0' != mm / 10) continue; if (time[4] != '?' && time[4] - '0' != mm % 10) continue; time[0] = (hh / 10) + '0'; time[1] = (hh % 10) + '0'; time[3] = (mm / 10) + '0'; time[4] = (mm % 10) + '0'; break; } return time; } }; |
Solution 2: Rules
Using rules, fill from left to right.
Time complexity: O(1)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: string maximumTime(string time) { if (time[0] == '?') time[0] = time[1] >= '4' && time[1] <= '9' ? '1' : '2'; if (time[1] == '?') time[1] = time[0] == '2' ? '3' : '9'; if (time[3] == '?') time[3] = '5'; if (time[4] == '?') time[4] = '9'; return time; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment