Easy

题目描述

给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 “?” 替换了。

12 小时制时间的格式为 “HH:MM”，其中 HH 在 00 到 11 之间，MM 在 00 到 59 之间。最早的 12 小时制时间是 00:00，最晚的是 11:59。

你需要将 s 中的所有 “?” 字符替换为数字，使得替换后的字符串表示一个有效的 12 小时制时间，并且是可能的最晚时间。

返回替换后的字符串。

示例 1：

输入：s = "1?:?4"
输出："11:54"
解释：通过替换 "?" 字符能得到的最晚 12 小时制时间是 "11:54"。

示例 2：

输入：s = "0?:5?"
输出："09:59"
解释：通过替换 "?" 字符能得到的最晚 12 小时制时间是 "09:59"。

提示：

  • s.length == 5
  • s[2] 等于字符 “:”
  • 除了 s[2] 之外的所有字符都是数字或 “?” 字符
  • 输入保证在替换 “?” 字符后，你可以得到一个在 “00:00” 和 “11:59” 之间的时间

解题思路

这道题要求我们将时间字符串中的 “?” 替换为数字，使得结果是有效的 12 小时制时间中最晚的。

解题思路：

由于时间格式固定为 “HH:MM”，我们可以从左到右贪心地处理每个位置的 “?"：

  1. 小时十位（位置0）：如果是 “?"，要使时间最晚，应该尽可能取大值。但要考虑小时个位的限制：

    • 如果小时个位是 0-1 或 “?"，十位可以取 1
    • 否则十位只能取 0（因为 12 小时制最大是 11:59）

  2. 小时个位（位置1）：如果是 “?"，在十位确定后选择最大可能值：

    • 如果十位是 1，个位最大是 1
    • 如果十位是 0，个位最大是 9

  3. 分钟十位（位置3）：如果是 “?"，最大取 5（因为分钟最大是 59）

  4. 分钟个位（位置4）：如果是 “?"，最大取 9

这种贪心策略能保证得到最晚的有效时间。

代码实现

class Solution {
public:
    string findLatestTime(string s) {
        // 处理小时十位
        if (s[0] == '?') {
            if (s[1] == '?' || s[1] <= '1') {
                s[0] = '1';
            } else {
                s[0] = '0';
            }
        }
        
        // 处理小时个位
        if (s[1] == '?') {
            if (s[0] == '1') {
                s[1] = '1';
            } else {
                s[1] = '9';
            }
        }
        
        // 处理分钟十位
        if (s[3] == '?') {
            s[3] = '5';
        }
        
        // 处理分钟个位
        if (s[4] == '?') {
            s[4] = '9';
        }
        
        return s;
    }
};

class Solution:
    def findLatestTime(self, s: str) -> str:
        s = list(s)
        
        # 处理小时十位
        if s[0] == '?':
            if s[1] == '?' or s[1] <= '1':
                s[0] = '1'
            else:
                s[0] = '0'
        
        # 处理小时个位
        if s[1] == '?':
            if s[0] == '1':
                s[1] = '1'
            else:
                s[1] = '9'
        
        # 处理分钟十位
        if s[3] == '?':
            s[3] = '5'
        
        # 处理分钟个位
        if s[4] == '?':
            s[4] = '9'
        
        return ''.join(s)

public class Solution {
    public string FindLatestTime(string s) {
        char[] chars = s.ToCharArray();
        
        // 处理小时十位
        if (chars[0] == '?') {
            if (chars[1] == '?' || chars[1] <= '1') {
                chars[0] = '1';
            } else {
                chars[0] = '0';
            }
        }
        
        // 处理小时个位
        if (chars[1] == '?') {
            if (chars[0] == '1') {
                chars[1] = '1';
            } else {
                chars[1] = '9';
            }
        }
        
        // 处理分钟十位
        if (chars[3] == '?') {
            chars[3] = '5';
        }
        
        // 处理分钟个位
        if (chars[4] == '?') {
            chars[4] = '9';
        }
        
        return new string(chars);
    }
}

var findLatestTime = function(s) {
    let chars = s.split('');
    
    // 处理小时十位
    if (chars[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(1) - 只需要检查和替换固定的 4 个位置
空间复杂度O(1) - 除了输入输出，只使用常数额外空间

相关题目