欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。
@[toc]
题目描述
[1736] 替换隐藏数字得到的最晚时间
给你一个字符串 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
题目数据保证你可以由输入的字符串生成有效的时间
Related Topics
题目剖析&信息挖掘
此题主要用枚举思想，再利用贪心思想求解。
也可以根据给出time里的问题情况进行判断，然后直接给出最优解。
解题思路
方法一 枚举+贪心
分析
答案肯定在00：00 - 23：59中，直接枚举所有可能，判断哪个可以由初始字符串转化来。
思路
// 判断是否可以由原来的串转化而来
func isMatch(s1, s2 string) bool {
}
func maximumTime(time string) string {
best := "00:00"
// 直接枚举小时和分钟
for h:=0;h<24;h++ {
for m:=0;m<60;m++ {
timeStr := fmt.Sprintf("%02d:%02d", h, m)
if isMatch(time, timeStr) {
best = timeStr
}
}
}
return best
}
注意
- 小时和分钟要前面补0
知识点
- 枚举
- 贪心
复杂度
- 时间复杂度：O(1)
- 空间复杂度：O(1)
代码实现
// 判断是否可以由原来的串转化而来
func isMatch(s1, s2 string) bool {
for i, c := range s1 {
if c == int32(s2[i]) {continue}
if c=='?'{continue}
return false
}
return true
}
func maximumTime(time string) string {
best := "00:00"
// 直接枚举小时和分钟
for h:=0;h<24;h++ {
for m:=0;m<60;m++ {
timeStr := fmt.Sprintf("%02d:%02d", h, m)
if isMatch(time, timeStr) {
best = timeStr
}
}
}
return best
}
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
