2437-有效时间的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你一个长度为 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 之间的数字替换。

方法一：回溯

思路与算法

由于字符串 time 中的 ?' 可以被 0’ 到 9' 中的任意字符替换，则依次尝试将字符串中的每个 ?’ 替换为 0' 到 9’ 后，并检测该时间的合法性即可，此时合法的时间需要满足如下:

  • “00”} \le \text{hh} \le \text{“23”；
  • “00”} \le \text{mm} \le \text{“59”；
    统计合法的时间数目并返回即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool check(const string &time) {
        int hh = stoi(time);
        int mm = stoi(time.substr(3));
        if (hh < 24 && mm < 60) {
            return true;
        } else {
            return false;
        }
    }

    int countTime(string time) {
        int res = 0;
        function<void(int)> dfs = [&](int pos) {
            if (pos == time.size()) {
                if (check(time)) {
                    res++;
                }
                return;
            }
            if (time[pos] == '?') {
                for (int i = 0; i <= 9; i++) {
                    time[pos] = '0' + i;
                    dfs(pos + 1);
                    time[pos] = '?';
                }
            } else {
                dfs(pos + 1);
            }
        };
        dfs(0);
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    int res = 0;

    public int countTime(String time) {
        char[] arr = time.toCharArray();
        dfs(arr, 0);
        return res;
    }

    public void dfs(char[] arr, int pos) {
        if (pos == arr.length) {
            if (check(arr)) {
                res++;
            }
            return;
        }
        if (arr[pos] == '?') {
            for (int i = 0; i <= 9; i++) {
                arr[pos] = (char) ('0' + i);
                dfs(arr, pos + 1);
                arr[pos] = '?';
            }
        } else {
            dfs(arr, pos + 1);
        }
    }

    public boolean check(char[] arr) {
        int hh = (arr[0] - '0') * 10 + arr[1] - '0';
        int mm = (arr[3] - '0') * 10 + arr[4] - '0';
        return hh < 24 && mm < 60;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    int res = 0;

    public int CountTime(string time) {
        char[] arr = time.ToCharArray();
        DFS(arr, 0);
        return res;
    }

    public void DFS(char[] arr, int pos) {
        if (pos == arr.Length) {
            if (Check(arr)) {
                res++;
            }
            return;
        }
        if (arr[pos] == '?') {
            for (int i = 0; i <= 9; i++) {
                arr[pos] = (char) ('0' + i);
                DFS(arr, pos + 1);
                arr[pos] = '?';
            }
        } else {
            DFS(arr, pos + 1);
        }
    }

    public bool Check(char[] arr) {
        int hh = (arr[0] - '0') * 10 + arr[1] - '0';
        int mm = (arr[3] - '0') * 10 + arr[4] - '0';
        return hh < 24 && mm < 60;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool check(const char *time) {
    int hh = atoi(time);
    int mm = atoi(time + 3);
    if (hh < 24 && mm < 60) {
        return true;
    } else {
        return false;
    }
}

void dfs(char *time, int pos, int *res) {
    if (time[pos] == '\0') {
        if (check(time)) {
            (*res)++;
        }
        return;
    }
    if (time[pos] == '?') {
        for (int i = 0; i <= 9; i++) {
            time[pos] = '0' + i;
            dfs(time, pos + 1, res);
            time[pos] = '?';
        }
    } else {
        dfs(time, pos + 1, res);
    }
}

int countTime(char * time){
    int res = 0;
    dfs(time, 0, &res);
    return res;
}

复杂度分析

  • 时间复杂度：O(|\Sigma|^4)，其中 |\Sigma| 表示字符集的大小，在此字符 |\Sigma| = 10。我们依次枚举 ?' 所有替换数字的方案，最多替换替换 4 个 ?’，因此时间复杂度为 O(|\Sigma|^4)。

  • 空间复杂度：O(1)。由于题目给定数目的现在，递归深度最多为 4，因此空间复杂度为 O(1)。

方法二：分开枚举

思路与算法

由于题目中小时和分钟的限制不同，因此没有必要枚举所有可能的数字，由于小时和分钟限制如下：

  • “00”} \le \text{hh} \le \text{“23”；
  • “00”} \le \text{mm} \le \text{“59”；

我们检测所有符合当前字符串 time 匹配的小时 hh 的数目为 countHour，同时检测检测所有符合当前字符串 time 匹配的分钟 hh 的数目为 countMinute，则合法有效的时间数目为 countHour} \times \textit{countMinute。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int countTime(string time) {
        int countHour = 0;
        int countMinute = 0;
        for (int i = 0; i < 24; i++) {
            int hiHour = i / 10;
            int loHour = i % 10;
            if ((time[0] == '?' || time[0] == hiHour + '0') && 
                (time[1] == '?' || time[1] == loHour + '0')) {
                countHour++;
            }
        } 
        for (int i = 0; i < 60; i++) {
            int hiMinute = i / 10;
            int loMinute = i % 10;
            if ((time[3] == '?' || time[3] == hiMinute + '0') && 
                (time[4] == '?' || time[4] == loMinute + '0')) {
                countMinute++;
            }
        }
        return countHour * countMinute;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int countTime(String time) {
        int countHour = 0;
        int countMinute = 0;
        for (int i = 0; i < 24; i++) {
            int hiHour = i / 10;
            int loHour = i % 10;
            if ((time.charAt(0) == '?' || time.charAt(0) == hiHour + '0') && 
                (time.charAt(1) == '?' || time.charAt(1) == loHour + '0')) {
                countHour++;
            }
        } 
        for (int i = 0; i < 60; i++) {
            int hiMinute = i / 10;
            int loMinute = i % 10;
            if ((time.charAt(3) == '?' || time.charAt(3) == hiMinute + '0') && 
                (time.charAt(4) == '?' || time.charAt(4) == loMinute + '0')) {
                countMinute++;
            }
        }
        return countHour * countMinute;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int CountTime(string time) {
        int countHour = 0;
        int countMinute = 0;
        for (int i = 0; i < 24; i++) {
            int hiHour = i / 10;
            int loHour = i % 10;
            if ((time[0] == '?' || time[0] == hiHour + '0') && 
                (time[1] == '?' || time[1] == loHour + '0')) {
                countHour++;
            }
        } 
        for (int i = 0; i < 60; i++) {
            int hiMinute = i / 10;
            int loMinute = i % 10;
            if ((time[3] == '?' || time[3] == hiMinute + '0') && 
                (time[4] == '?' || time[4] == loMinute + '0')) {
                countMinute++;
            }
        }
        return countHour * countMinute;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int countTime(char * time) {
    int countHour = 0;
    int countMinute = 0;
    for (int i = 0; i < 24; i++) {
        int hiHour = i / 10;
        int loHour = i % 10;
        if ((time[0] == '?' || time[0] == hiHour + '0') && 
            (time[1] == '?' || time[1] == loHour + '0')) {
            countHour++;
        }
    } 
    for (int i = 0; i < 60; i++) {
        int hiMinute = i / 10;
        int loMinute = i % 10;
        if ((time[3] == '?' || time[3] == hiMinute + '0') && 
            (time[4] == '?' || time[4] == loMinute + '0')) {
            countMinute++;
        }
    }
    return countHour * countMinute;
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def countTime(self, time: str) -> int:
        countHour = 0
        countMinute = 0
        for i in range(24):
            hiHour = i // 10
            loHour = i % 10
            if ((time[0] == '?' or int(time[0]) == hiHour) and
                    (time[1] == '?' or int(time[1]) == loHour)):
                countHour += 1

        for i in range(60):
            hiMinute = i // 10
            loMinute = i % 10
            if ((time[3] == '?' or int(time[3]) == hiMinute) and
                    (time[4] == '?' or int(time[4]) == loMinute)):
                countMinute += 1

        return countHour * countMinute
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var countTime = function(time) {
    let res = 0;
        const dfs = (arr, pos) => {
        if (pos === arr.length) {
            if (check(arr)) {
                res++;
            }
            return;
        }
        if (arr[pos] === '?') {
            for (let i = 0; i <= 9; i++) {
                arr[pos] = String.fromCharCode('0'.charCodeAt() + i);
                dfs(arr, pos + 1);
                arr[pos] = '?';
            }
        } else {
            dfs(arr, pos + 1);
        }
    }

    const check = (arr) => {
        const hh = (arr[0].charCodeAt() - '0'.charCodeAt()) * 10 + arr[1].charCodeAt() - '0'.charCodeAt();
        const mm = (arr[3].charCodeAt() - '0'.charCodeAt()) * 10 + arr[4].charCodeAt() - '0'.charCodeAt();
        return hh < 24 && mm < 60;
    };
    const arr = [...time];
    dfs(arr, 0);
    return res;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func countTime(time string) int {
    countHour := 0
    countMinute := 0
    for i := 0; i < 24; i++ {
        hiHour := byte(i / 10)
        loHour := byte(i % 10)
        if (time[0] == '?' || time[0] == hiHour+'0') &&
            (time[1] == '?' || time[1] == loHour+'0') {
            countHour++
        }
    }
    for i := 0; i < 60; i++ {
        hiMinute := byte(i / 10)
        loMinute := byte(i % 10)
        if (time[3] == '?' || time[3] == hiMinute+'0') &&
            (time[4] == '?' || time[4] == loMinute+'0') {
            countMinute++
        }
    }
    return countHour * countMinute
}

复杂度分析

  • 时间复杂度：O(1)。由于时钟的最大值为 24，分钟的最大值为 60，在此题解中分别枚举所可能的时钟，以及所有可能分钟，时间复杂度为 O(24 + 60) = O(1)。

  • 空间复杂度：O(1)。

 Comments
On this page
2437-有效时间的数目