3114. 替换字符可以得到的最晚时间

题目描述

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

12 小时制时间格式为 "HH:MM" ，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 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\times 60\) 种。从大到小枚举小时与分钟，检查与模式串在非 ? 位是否一致，第一次命中即最大合法时间。

状态空间为常数，无需回溯或逐位推最优。按 \(11{:}59\) 到 \(00{:}00\) 的顺序保证字典序最大。

因此双重循环生成 HH:MM，用逐位比较过滤 ?，返回第一个匹配的串。

我们可以从大到小枚举所有的时间，其中小时 \(h\) 从 \(11\) 到 \(0\)，分钟 \(m\) 从 \(59\) 到 \(0\)。对于每一个时间 \(t\)，我们检查是否满足 \(t\) 的每一位字符都与 \(s\) 的对应位置字符相等（如果 \(s\) 的对应位置字符不是 "?" 的话）。如果满足，那么我们就找到了答案，返回 \(t\)。

时间复杂度 \(O(h \times m)\)，其中 \(h = 12\), \(m = 60\)。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def findLatestTime(self, s: str) -> str:
        for h in range(11, -1, -1):
            for m in range(59, -1, -1):
                t = f"{h:02d}:{m:02d}"
                if all(a == b for a, b in zip(s, t) if a != "?"):
                    return t

class Solution {
    public String findLatestTime(String s) {
        for (int h = 11;; h--) {
            for (int m = 59; m >= 0; m--) {
                String t = String.format("%02d:%02d", h, m);
                boolean ok = true;
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) != '?' && s.charAt(i) != t.charAt(i)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    return t;
                }
            }
        }
    }
}

class Solution {
public:
    string findLatestTime(string s) {
        for (int h = 11;; h--) {
            for (int m = 59; m >= 0; m--) {
                char t[6];
                sprintf(t, "%02d:%02d", h, m);
                bool ok = true;
                for (int i = 0; i < s.length(); i++) {
                    if (s[i] != '?' && s[i] != t[i]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    return t;
                }
            }
        }
    }
};

func findLatestTime(s string) string {
    for h := 11; ; h-- {
        for m := 59; m >= 0; m-- {
            t := fmt.Sprintf("%02d:%02d", h, m)
            ok := true
            for i := 0; i < len(s); i++ {
                if s[i] != '?' && s[i] != t[i] {
                    ok = false
                    break
                }
            }
            if ok {
                return t
            }
        }
    }
}

function findLatestTime(s: string): string {
    for (let h = 11; ; h--) {
        for (let m = 59; m >= 0; m--) {
            const t: string = `${h.toString().padStart(2, '0')}:${m.toString().padStart(2, '0')}`;
            let ok: boolean = true;
            for (let i = 0; i < s.length; i++) {
                if (s[i] !== '?' && s[i] !== t[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return t;
            }
        }
    }
}

方法二：逐个判断

思考

方法一枚举全部时刻，虽为常数但仍做了数百次格式化与比较。每位的取值范围由 12 小时制独立确定，可以直接写下。

小时十位只能是 \(0\) 或 \(1\)，个位在十位为 \(1\) 时至多为 \(1\)；分钟十位至多为 \(5\)，个位可取 \(9\)。

为此按从左到右把每个 ? 换成仍合法的最大数字：先定 \(s[0]\) 再定 \(s[1]\)，分钟两位分别填 \(5\) 与 \(9\)。一次扫描即可。

我们可以逐个判断 \(s\) 的每一位字符，如果是 "?" 的话，我们就根据前后的字符来确定这一位字符的值。具体地，我们有以下规则：

如果 \(s[0]\) 是 "?"，那么 \(s[0]\) 的值应该是 "1" 或 "0"，具体取决于 \(s[1]\) 的值。如果 \(s[1]\) 是 "?" 或者 \(s[1]\) 小于 "2"，那么 \(s[0]\) 的值应该是 "1"，否则 \(s[0]\) 的值应该是 "0"。
如果 \(s[1]\) 是 "?"，那么 \(s[1]\) 的值应该是 "1" 或 "9"，具体取决于 \(s[0]\) 的值。如果 \(s[0]\) 是 "1"，那么 \(s[1]\) 的值应该是 "1"，否则 \(s[1]\) 的值应该是 "9"。
如果 \(s[3]\) 是 "?"，那么 \(s[3]\) 的值应该是 "5"。
如果 \(s[4]\) 是 "?"，那么 \(s[4]\) 的值应该是 "9"。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def findLatestTime(self, s: str) -> str:
        s = list(s)
        if s[0] == "?":
            s[0] = "1" if s[1] == "?" or s[1] < "2" else "0"
        if s[1] == "?":
            s[1] = "1" if s[0] == "1" else "9"
        if s[3] == "?":
            s[3] = "5"
        if s[4] == "?":
            s[4] = "9"
        return "".join(s)

class Solution {
    public String findLatestTime(String s) {
        char[] cs = s.toCharArray();
        if (cs[0] == '?') {
            cs[0] = cs[1] == '?' || cs[1] < '2' ? '1' : '0';
        }
        if (cs[1] == '?') {
            cs[1] = cs[0] == '1' ? '1' : '9';
        }
        if (cs[3] == '?') {
            cs[3] = '5';
        }
        if (cs[4] == '?') {
            cs[4] = '9';
        }
        return new String(cs);
    }
}

class Solution {
public:
    string findLatestTime(string s) {
        if (s[0] == '?') {
            s[0] = s[1] == '?' || s[1] < '2' ? '1' : '0';
        }
        if (s[1] == '?') {
            s[1] = s[0] == '1' ? '1' : '9';
        }
        if (s[3] == '?') {
            s[3] = '5';
        }
        if (s[4] == '?') {
            s[4] = '9';
        }
        return s;
    }
};

func findLatestTime(s string) string {
    cs := []byte(s)
    if cs[0] == '?' {
        if cs[1] == '?' || cs[1] < '2' {
            cs[0] = '1'
        } else {
            cs[0] = '0'
        }
    }
    if cs[1] == '?' {
        if cs[0] == '1' {
            cs[1] = '1'
        } else {
            cs[1] = '9'
        }
    }
    if cs[3] == '?' {
        cs[3] = '5'
    }
    if cs[4] == '?' {
        cs[4] = '9'
    }
    return string(cs)
}

function findLatestTime(s: string): string {
    const cs = s.split('');
    if (cs[0] === '?') {
        cs[0] = cs[1] === '?' || cs[1] < '2' ? '1' : '0';
    }
    if (cs[1] === '?') {
        cs[1] = cs[0] === '1' ? '1' : '9';
    }
    if (cs[3] === '?') {
        cs[3] = '5';
    }
    if (cs[4] === '?') {
        cs[4] = '9';
    }
    return cs.join('');
}

3114. 替换字符可以得到的最晚时间

题目描述

解法

方法一：枚举

方法二：逐个判断

评论