Easy

题目描述

给你一个字符串 time ，格式为 hh:mm，其中某些位的数字被隐藏（用 ? 表示）。

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

解题思路

解题思路

这是一个贪心算法问题，我们需要让每个位置的数字尽可能大，同时保证时间的有效性。

主要思路

  1. 贪心策略：从左到右逐位填充，每个位置选择能够使整体时间最大的数字
  2. 小时部分处理：
    • 第一位（十位）：如果第二位是0-3或?，则可以填2；否则只能填1或0
    • 第二位（个位）：如果第一位是2，最大只能填3；如果第一位是0或1，最大能填9
  3. 分钟部分处理：
    • 第一位（十位）：最大只能填5（因为分钟最大59）
    • 第二位（个位）：最大能填9

具体算法步骤

  1. 将字符串转换为字符数组便于修改
  2. 按顺序处理每个问号位置：
    • 小时十位：根据小时个位的值决定填1还是2
    • 小时个位：根据小时十位的值决定最大值
    • 分钟十位：直接填5
    • 分钟个位：直接填9

这种贪心策略能保证得到最大的有效时间，因为我们总是在约束条件下选择最大的数字。

代码实现

class Solution {
public:
    string maximumTime(string time) {
        vector<char> t(time.begin(), time.end());
        
        // 处理小时十位
        if (t[0] == '?') {
            if (t[1] == '?' || t[1] <= '3') {
                t[0] = '2';
            } else {
                t[0] = '1';
            }
        }
        
        // 处理小时个位
        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.begin(), t.end());
    }
};

class Solution:
    def maximumTime(self, time: str) -> str:
        t = list(time)
        
        # 处理小时十位
        if t[0] == '?':
            if t[1] == '?' or t[1] <= '3':
                t[0] = '2'
            else:
                t[0] = '1'
        
        # 处理小时个位
        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 ''.join(t)

public class Solution {
    public string MaximumTime(string time) {
        char[] t = time.ToCharArray();
        
        // 处理小时十位
        if (t[0] == '?') {
            if (t[1] == '?' || t[1] <= '3') {
                t[0] = '2';
            } else {
                t[0] = '1';
            }
        }
        
        // 处理小时个位
        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 new string(t);
    }
}

/**
 * @param {string} time
 * @return {string}
 */
var maximumTime = function(time) {
    let t = time.split('');
    
    // 处理小时十位
    if (t[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(1)只需要检查固定的4个位置
空间复杂度O(1)只使用常量额外空间（字符数组）

相关题目