python3__leecode/1736.替換隐藏數字得到的最晚時間

1736. latest time by replacing hidden digits替換隐藏數字得到的最晚時間

• 一、刷題内容
• • 原題連結
  • 内容描述
• 二、解題方法
• • 1.方法一：貪心
  • 2.方法二

一、刷題内容

原題連結

https://leetcode-cn.com/problems/latest-time-by-replacing-hidden-digits/

内容描述

給你一個字元串 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

題目資料保證你可以由輸入的字元串生成有效的時間

二、解題方法

1.方法一：貪心

為了得到最晚有效時間，我們可以從高位向低位枚舉，在保證時間有效的情況下，使得每一位盡可能取最大值。

因為本題中時間的位數較少，我們依次考慮每一位的規則即可。

第一位：若第二位的值已經确定，且值落在區間 [4,9][4,9] 中時，第一位的值最大隻能為 11，否則最大可以為 22；

第二位：若第一位的值已經确定，且值為 22 時，第二位的值最大為 33，否則為 99；

第三位：第三位的值的選取與其它位無關，最大為 55；

第四位：第四位的值的選取與其它位無關，最大為 99。

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)
           

2.方法二

class Solution:
    def maximumTime(self, time: str) -> str:
        time = list(time)
        if time[0] == '?':
            time[0] = '2' if time[1] in ('0','1','2','3','?') else '1'
        if time[1] == '?':
            time[1] = '9' if time[0] in ('0','1') else '3'
        if time[3] == '?': time[3] = '5'
        if time[4] == '?': time[4] = '9'
        return "".join(time)