文章目录
- 题目
- 思路一、枚举
- 思路二、回溯
题目
链接: link
思路一、枚举
这题的可以简单的看成 h1 h2 : m1 m2 的情况,其中 h1 和 h2 有关, m1 和 m2 有关,数目不多可以直接暴力枚举解决
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;
}
由于时钟的最大值为 24,分钟的最大值为 60,在此题解中分别枚举所可能的时钟,以及所有可能分钟,时间复杂度为 O(24+60)=O(1)。
只要理清楚还是很好做的
思路二、回溯
由于当出现 ‘?’ 时,我们可以填入 0 - 9 任意一个数字,然后再返回去看是否合法就行。
即 00<= h1h2 <=23 、 00<= m1m2 <=59
bool check(const char *time) {
//atoi提取数字,遇到非数字时停止
int h1h2 = atoi(time);
int m1m2 = atoi(time + 3);
if (h1h2 < 24 && m1m2 < 60) {//正常读取时不会出现负号,所以无所谓>=0
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;
}