1736. 替换隐藏数字得到的最晚时间

• 标签：贪心、字符串
• 难度：简单

题目链接

• 1736. 替换隐藏数字得到的最晚时间 - 力扣

题目大意

描述：给定一个字符串 $time$，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。

要求：替换 $time$ 中隐藏的数字，返回你可以得到的最晚有效时间。

说明：

• 有效时间： 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59。
• $time$ 的格式为 hh:mm。
• 题目数据保证你可以由输入的字符串生成有效的时间。

示例：

• 示例 1：

输入：time = "2?:?0"
输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50。

• 示例 2：

输入：time = "0?:3?"
输出："09:39"

解题思路

思路 1：贪心算法

为了使有效时间尽可能晚，我们可以从高位到低位依次枚举所有符号为 ? 的字符。在保证时间有效的前提下，每一位上取最大值，并进行保存。具体步骤如下：

• 如果第 $1$ 位为 ?：
  • 如果第 $2$ 位已经确定，并且范围在 $[4, 9]$ 中间，则第 $1$ 位最大为 $1$；
  • 否则第 $1$ 位最大为 $2$。
• 如果第 $2$ 位为 ?：
  • 如果第 $1$ 位上值为 $2$，则第 $2$ 位最大可以为 $3$；
  • 否则第 $2$ 位最大为 $9$。
• 如果第 $3$ 位为 ?：
  • 第 $3$ 位最大可以为 $5$。
• 如果第 $4$ 位为 ?：
  • 第 $4$ 位最大可以为 $9$。

思路 1：代码

class Solution:
    def maximumTime(self, time: str) -> str:
        time_list = list(time)
        if time_list[0] == '?':
            if '4' <= time_list[1] <= '9':
                time_list[0] = '1'
            else:
                time_list[0] = '2'

        if time_list[1] == '?':
            if time_list[0] == '2':
                time_list[1] = '3'
            else:
                time_list[1] = '9'

        if time_list[3] == '?':
            time_list[3] = '5'
        
        if time_list[4] == '?':
            time_list[4] = '9'
            
        return "".join(time_list)

思路 1：复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。