跳转至

2437. 有效时间的数目

题目描述

给你一个长度为 5 的字符串 time ,表示一个电子时钟当前的时间,格式为 "hh:mm" 。最早 可能的时间是 "00:00" ,最晚 可能的时间是 "23:59" 。

在字符串 time 中,被字符 ? 替换掉的数位是 未知的 ,被替换的数字可能是 0 到 9 中的任何一个。

请你返回一个整数 answer ,将每一个 ? 都用 0 到 9 中一个数字替换后,可以得到的有效时间的数目。

 

示例 1:

输入:time = "?5:00"
输出:2
解释:我们可以将 ? 替换成 0 或 1 ,得到 "05:00" 或者 "15:00" 。注意我们不能替换成 2 ,因为时间 "25:00" 是无效时间。所以我们有两个选择。

示例 2:

输入:time = "0?:0?"
输出:100
解释:两个 ? 都可以被 0 到 9 之间的任意数字替换,所以我们总共有 100 种选择。

示例 3:

输入:time = "??:??"
输出:1440
解释:小时总共有 24 种选择,分钟总共有 60 种选择。所以总共有 24 * 60 = 1440 种选择。

 

提示:

  • time 是一个长度为 5 的有效字符串,格式为 "hh:mm" 。
  • "00" <= hh <= "23"
  • "00" <= mm <= "59"
  • 字符串中有的数位是 '?' ,需要用 0 到 9 之间的数字替换。

解法

方法一:枚举

我们可以直接枚举从 $00:00$ 到 $23:59$ 的所有时间,然后判断每个时间是否有效,是则答案加一。

枚举结束后将答案返回即可。

时间复杂度 $O(24 \times 60)$,空间复杂度 $O(1)$。

1
2
3
4
5
6
7
8
class Solution:
    def countTime(self, time: str) -> int:
        def check(s: str, t: str) -> bool:
            return all(a == b or b == '?' for a, b in zip(s, t))

        return sum(
            check(f'{h:02d}:{m:02d}', time) for h in range(24) for m in range(60)
        )
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countTime(String time) {
        int ans = 0;
        for (int h = 0; h < 24; ++h) {
            for (int m = 0; m < 60; ++m) {
                String s = String.format("%02d:%02d", h, m);
                int ok = 1;
                for (int i = 0; i < 5; ++i) {
                    if (s.charAt(i) != time.charAt(i) && time.charAt(i) != '?') {
                        ok = 0;
                        break;
                    }
                }
                ans += ok;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countTime(string time) {
        int ans = 0;
        for (int h = 0; h < 24; ++h) {
            for (int m = 0; m < 60; ++m) {
                char s[20];
                sprintf(s, "%02d:%02d", h, m);
                int ok = 1;
                for (int i = 0; i < 5; ++i) {
                    if (s[i] != time[i] && time[i] != '?') {
                        ok = 0;
                        break;
                    }
                }
                ans += ok;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func countTime(time string) int {
    ans := 0
    for h := 0; h < 24; h++ {
        for m := 0; m < 60; m++ {
            s := fmt.Sprintf("%02d:%02d", h, m)
            ok := 1
            for i := 0; i < 5; i++ {
                if s[i] != time[i] && time[i] != '?' {
                    ok = 0
                    break
                }
            }
            ans += ok
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function countTime(time: string): number {
    let ans = 0;
    for (let h = 0; h < 24; ++h) {
        for (let m = 0; m < 60; ++m) {
            const s = `${h}`.padStart(2, '0') + ':' + `${m}`.padStart(2, '0');
            let ok = 1;
            for (let i = 0; i < 5; ++i) {
                if (s[i] !== time[i] && time[i] !== '?') {
                    ok = 0;
                    break;
                }
            }
            ans += ok;
        }
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn count_time(time: String) -> i32 {
        let mut ans = 0;

        for i in 0..24 {
            for j in 0..60 {
                let mut ok = true;
                let t = format!("{:02}:{:02}", i, j);

                for (k, ch) in time.chars().enumerate() {
                    if ch != '?' && ch != t.chars().nth(k).unwrap() {
                        ok = false;
                    }
                }

                if ok {
                    ans += 1;
                }
            }
        }

        ans
    }
}

方法二:枚举优化

我们可以分开枚举小时和分钟,统计有多少个小时和分钟满足条件,然后将二者相乘即可。

时间复杂度 $O(24 + 60)$,空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countTime(self, time: str) -> int:
        def f(s: str, m: int) -> int:
            cnt = 0
            for i in range(m):
                a = s[0] == '?' or (int(s[0]) == i // 10)
                b = s[1] == '?' or (int(s[1]) == i % 10)
                cnt += a and b
            return cnt

        return f(time[:2], 24) * f(time[3:], 60)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int countTime(String time) {
        return f(time.substring(0, 2), 24) * f(time.substring(3), 60);
    }

    private int f(String s, int m) {
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            boolean a = s.charAt(0) == '?' || s.charAt(0) - '0' == i / 10;
            boolean b = s.charAt(1) == '?' || s.charAt(1) - '0' == i % 10;
            cnt += a && b ? 1 : 0;
        }
        return cnt;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int countTime(string time) {
        auto f = [](string s, int m) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                bool a = s[0] == '?' || s[0] - '0' == i / 10;
                bool b = s[1] == '?' || s[1] - '0' == i % 10;
                cnt += a && b;
            }
            return cnt;
        };
        return f(time.substr(0, 2), 24) * f(time.substr(3, 2), 60);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func countTime(time string) int {
    f := func(s string, m int) (cnt int) {
        for i := 0; i < m; i++ {
            a := s[0] == '?' || int(s[0]-'0') == i/10
            b := s[1] == '?' || int(s[1]-'0') == i%10
            if a && b {
                cnt++
            }
        }
        return
    }
    return f(time[:2], 24) * f(time[3:], 60)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function countTime(time: string): number {
    const f = (s: string, m: number): number => {
        let cnt = 0;
        for (let i = 0; i < m; ++i) {
            const a = s[0] === '?' || s[0] === Math.floor(i / 10).toString();
            const b = s[1] === '?' || s[1] === (i % 10).toString();
            if (a && b) {
                ++cnt;
            }
        }
        return cnt;
    };
    return f(time.slice(0, 2), 24) * f(time.slice(3), 60);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn count_time(time: String) -> i32 {
        let f = |s: &str, m: usize| -> i32 {
            let mut cnt = 0;
            let first = s.chars().nth(0).unwrap();
            let second = s.chars().nth(1).unwrap();

            for i in 0..m {
                let a = first == '?' || (first.to_digit(10).unwrap() as usize) == i / 10;

                let b = second == '?' || (second.to_digit(10).unwrap() as usize) == i % 10;

                if a && b {
                    cnt += 1;
                }
            }

            cnt
        };

        f(&time[..2], 24) * f(&time[3..], 60)
    }
}

评论