2437.有效时间的数目

【LetMeFly】2437.有效时间的数目

力扣题目链接：https://leetcode.cn/problems/number-of-valid-clock-times/

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

方法一：特判

写两个函数，分别计算时间有多少种，分钟有多少种。

对于时间：

• 如果两个位置都是’?’，那么一共有24种
• 若只第一个位置是’?’，那么第二个位置是’0’-‘3’的话有3种，否则有2种（没有25点）
• 若只第二个位置是’?’，那么第一个位置是’0’-‘1’的话有10种，否则有4种
• 若两个位置都不是’?’，则返回1

同理，对于分钟：

• 如果两个位置都是’?’，那么一共有60种
• 若只第一个位置是’?’，那么一共有6种
• 若只第二个位置是’?’，那么一共有10种
• 若两个位置都不是’?’，则返回1

最终$小时种类数\times 分钟种类数$即为答案

• 时间复杂度$O(1)$，全部由if-else组成
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
private:
    int getHour(char a, char b) {
        if (a == '?' && b == '?') {
            return 24;
        }
        if (a == '?') {
            return '0' <= b && b <= '3' ? 3 : 2;
        }
        if (b == '?') {
            return a == '0' || a == '1' ? 10 : 4;
        }
        return 1;
    }

    int getMin(char a, char b) {
        if (a == '?' && b == '?') {
            return 60;
        }
        if (a == '?') {
            return 6;
        }
        if (b == '?') {
            return 10;
        }
        return 1;
    }
public:
    int countTime(string time) {
        return getHour(time[0], time[1]) * getMin(time[3], time[4]);
    }
};

方法二：枚举

我们只需要枚举每一个合法的时间，然后判断给定时间能否替换’?’成为枚举的时间即可。

枚举合法时间：

for (int h = 0; h < 24; h++) {
    for (int m = 0; m < 60; m++) {
        // ...
    }
}

判断能否由oldTime变成newTime：

bool canChangeTo(string oldTime, string newTime) {
    for (int i = 0; i < 5; i++) {
        if (oldTime[i] != newTime[i] && oldTime[i] != '?') {  // 两字符串此数不同，且oldTime这个数不是?
            return false;
        }
    }
    return true;
}

• 时间复杂度$O(H\times M\times C)$，其中$H=24$，$M=60$，$C$是时间字符串的长度$5$
• 空间复杂度$O(C)$

AC代码

C++

class Solution {
private:
    bool canChangeTo(string oldTime, string newTime) {
        for (int i = 0; i < 5; i++) {
            if (oldTime[i] != newTime[i] && oldTime[i] != '?') {
                return false;
            }
        }
        return true;
    }
public:
    int countTime(string time) {
        int ans = 0;
        for (int h = 0; h < 24; h++) {
            for (int m = 0; m < 60; m++) {
                string thisTime = string("") + (char)('0' + h / 10) + (char)('0' + h % 10) + ':' + (char)('0' + m / 10) + (char)('0' + m % 10);
                ans += canChangeTo(time, thisTime);
            }
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130573965