给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。
有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。
替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。
示例 1：
**输入：** time = "2?:?0"
**输出：** "23:50"
**解释：** 以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。
示例 2：
**输入：** time = "0?:3?"
**输出：** "09:39"
示例 3：
**输入：** time = "1?:22"
**输出：** "19:22"
提示：
time 的格式为 hh:mm- 题目数据保证你可以由输入的字符串生成有效的时间
方法一：贪心
思路与算法
为了得到最晚有效时间，我们可以从高位向低位枚举，在保证时间有效的情况下，使得每一位尽可能取最大值。
因为本题中时间的位数较少，我们依次考虑每一位的规则即可。
- 第一位：若第二位的值已经确定，且值落在区间 [4,9] 中时，第一位的值最大只能为 1，否则最大可以为 2；
- 第二位：若第一位的值已经确定，且值为 2 时，第二位的值最大为 3，否则为 9；
- 第三位：第三位的值的选取与其它位无关，最大为 5；
- 第四位：第四位的值的选取与其它位无关，最大为 9。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
string maximumTime(string time) {
if (time[0] == '?') {
time[0] = ('4' <= time[1] && 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;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String maximumTime(String time) {
char[] arr = time.toCharArray();
if (arr[0] == '?') {
arr[0] = ('4' <= arr[1] && arr[1] <= '9') ? '1' : '2';
}
if (arr[1] == '?') {
arr[1] = (arr[0] == '2') ? '3' : '9';
}
if (arr[3] == '?') {
arr[3] = '5';
}
if (arr[4] == '?') {
arr[4] = '9';
}
return new String(arr);
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
public string MaximumTime(string time) {
char[] arr = time.ToCharArray();
if (arr[0] == '?') {
arr[0] = ('4' <= arr[1] && arr[1] <= '9') ? '1' : '2';
}
if (arr[1] == '?') {
arr[1] = (arr[0] == '2') ? '3' : '9';
}
if (arr[3] == '?') {
arr[3] = '5';
}
if (arr[4] == '?') {
arr[4] = '9';
}
return new string(arr);
}
}
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func maximumTime(time string) string {
t := []byte(time)
if t[0] == '?' {
if '4' <= t[1] && t[1] <= '9' {
t[0] = '1'
} else {
t[0] = '2'
}
}
if t[1] == '?' {
if t[0] == '2' {
t[1] = '3'
} else {
t[1] = '9'
}
}
if t[3] == '?' {
t[3] = '5'
}
if t[4] == '?' {
t[4] = '9'
}
return string(t)
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| char* maximumTime(char* time) {
if (time[0] == '?') {
time[0] = ('4' <= time[1] && 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;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var maximumTime = function(time) {
const arr = Array.from(time);
if (arr[0] === '?') {
arr[0] = ('4' <= arr[1] && arr[1] <= '9') ? '1' : '2';
}
if (arr[1] === '?') {
arr[1] = (arr[0] == '2') ? '3' : '9';
}
if (arr[3] === '?') {
arr[3] = '5';
}
if (arr[4] === '?') {
arr[4] = '9';
}
return arr.join('');
};
|
复杂度分析
