每日算法中的简单贪心问题，在 LeeCode 上是否容易掌握？

本文共计1329个文字，预计阅读时间需要6分钟。

题目描述：这是 LeetCode 上的 1736. 替换隐藏数字得到的最晚时间，难度为简单。Tag：贪心给你一个字符串 time，其中包含一个时钟的时针和分针的当前时间，格式为 hh:mm（其中 hh 在 00 到 12 之间，mm 在 00 到 59 之间）。有效的 24 小时制时间按以下规则计算：

小时 hh 可以是两位数字，也可能是单数字，但表示的是 24 小时制时间。例如，01 是有效的，9 也是有效的，但 12 是无效的。分钟 mm 必须是两位数字。一些数字（例如 00、01、10 和 20）表示特定的时间。这些时间可以表示为：00:00 - midnight01:00 - one minute past midnight10:00 - ten o'clock20:00 - twenty o'clock00:01 - one minute past midnight00:10 - ten minutes past midnight00:20 - twenty minutes past midnight01:00 - one o'clock09:00 - nine o'clock10:00 - ten o'clock20:00 - twenty o'clock21:00 - twenty-one o'clock21:20 - twenty minutes past nine o'clock23:59 - the last minute before midnight

你需要将这个时间转换为最晚可能的时间，并且按照 hh:mm 格式返回。如果不存在可能的时间，则返回一个空字符串。

示例 1：输入：time=01:00输出：23:59

示例 2：输入：time=00:00输出：23:59

示例 3：输入：time=01:20输出：23:59

示例 4：输入：time=00:10输出：23:59

示例 5：输入：time=12:00输出：23:59

示例 6：输入：time=12:01输出：23:59

示例 7：输入：time=12:10输出：23:59

示例 8：输入：time=12:20输出：23:59

示例 9：输入：time=12:21输出：23:59

示例 10：输入：time=12:22输出：23:59

题目描述

这是 LeetCode 上的 ​​1736. 替换隐藏数字得到的最晚时间​​ ，难度为 简单。

Tag : 「贪心」

给你一个字符串 ​​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​​
• 题目数据保证你可以由输入的字符串生成有效的时间

贪心 + 模拟

规则十分简单，对每一位进行分情况讨论即可：

• 第一位：如果需要被替换，优先替换为​​2​​​，当然前提是第二位不能超过​​4​​​。否则会出现​​24:xx​​​、​​25:xx​​ 等；
• 第二位：如果需要被替换，根据第一位是什么，决定替换为​​9​​​ 还是​​3​​；
• 第三位：固定为​​:​​；
• 第四位：如果需要被替换，替换为​​5​​；
• 第五位：如果需要被替换，替换为​​9​​。

Java 代码：

class Solution {
public String maximumTime(String time) {
StringBuilder sb = new StringBuilder();
sb.append(time.charAt(0) == '?' ? (time.charAt(1) == '?' || time.charAt(1) < '4') ? '2' : '1' : time.charAt(0));
sb.append(time.charAt(1) == '?' ? sb.charAt(0) == '2' ? '3' : '9' : time.charAt(1));
sb.append(':');
sb.append(time.charAt(3) == '?' ? '5' : time.charAt(3));
sb.append(time.charAt(4) == '?' ? '9' : time.charAt(4));
return sb.toString();
}
}

Python 3 代码：

class Solution:
def maximumTime(self, time: str) -> str:
time = list(time)
for i in range(len(time)):
if i==0 and time[i]=='?':
if time[i+1] == '?' or int(time[i+1])<=3:
time[i] = '2'
else:
time[i] = '1'
if i==1 and time[i]=='?':
if time[i-1]=='0' or time[i-1]=='1':
time[i] = '9'
else:
time[i] = '3'
if i==3 and time[i]=='?':
time[i] = '5'
if i==4 and time[i]=='?':
time[i] = '9'
return ''.join(time)

• 时间复杂度：
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.1736​​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​ 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。