1904-你完成的完整对局数

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    

一款新的在线电子游戏在近期发布，在该电子游戏中，以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着，在
HH:00、HH:15、HH:30 和 HH:45 ，将会开始一个新的对局，其中 HH 用一个从 00 到 23
的整数表示。游戏中使用 24 小时制的时钟 ，所以一天中最早的时间是 00:00 ，最晚的时间是 23:59 。

给你两个字符串 startTime 和 finishTime ，均符合 "HH:MM" 格式，分别表示你 进入 和 退出
游戏的确切时间，请计算在整个游戏会话期间，你完成的 完整对局的对局数 。

  • 例如，如果 startTime = "05:20" 且 finishTime = "05:59" ，这意味着你仅仅完成从 05:30 到 05:45 这一个完整对局。而你没有完成从 05:15 到 05:30 的完整对局，因为你是在对局开始后进入的游戏；同时，你也没有完成从 05:45 到 06:00 的完整对局，因为你是在对局结束前退出的游戏。

如果 finishTime 早于 startTime ，这表示你玩了个通宵（也就是从 startTime 到午夜，再从午夜到
finishTime）。

假设你是从 startTime 进入游戏，并在 finishTime 退出游戏，请计算并返回你完成的 完整对局的对局数 。

示例 1：

**输入：** startTime = "12:01", finishTime = "12:44"
**输出：** 1
**解释：** 你完成了从 12:15 到 12:30 的一个完整对局。
你没有完成从 12:00 到 12:15 的完整对局，因为你是在对局开始后的 12:01 进入的游戏。
你没有完成从 12:30 到 12:45 的完整对局，因为你是在对局结束前的 12:44 退出的游戏。

示例 2：

**输入：** startTime = "20:00", finishTime = "06:00"
**输出：** 40
**解释：** 你完成了从 20:00 到 00:00 的 16 个完整的对局，以及从 00:00 到 06:00 的 24 个完整的对局。
16 + 24 = 40

示例 3：

**输入：** startTime = "00:00", finishTime = "23:59"
**输出：** 95
**解释：** 除最后一个小时你只完成了 3 个完整对局外，其余每个小时均完成了 4 场完整对局。

提示：

  • startTime 和 finishTime 的格式为 HH:MM
  • 00 <= HH <= 23
  • 00 <= MM <= 59
  • startTime 和 finishTime 不相等

方法一：转化为分钟

思路与算法

为了方便计算，我们设第一天的 00:00 为时间零点，同时将 startTime 和 finishTime 转化为距离时间零点的分钟数 t_0 和 t_1。

此处要注意，如果转换后的 t_1 < t_0，这说明 finishTime 在第二天，此时我们需要将 t_1 加上一天对应的分钟数，即 1440。

在转化为分钟后，我们需要计算 [t_0, t_1] 闭区间内完整对局的个数。我们可以将 t_1 转化为 t_1 或之前时刻最后一场完整对局的结束时间 t_1’，或将 t_0 转化为 t_0 或之后时刻第一场完整对局的开始时间 t_0’ 即可。转化后闭区间内完整对局的个数不变。在本文中，我们仅将 t_1 转化为 t_1’。

进行转化后，此时由于 t_1’ 对应一场完整对局的结束时间，因此[t_0, t_1’] 闭区间的长度（由于 t_1’ \le t_1，可能存在 t_0 > t_1’ 的情况，此时区间长度视为 0）除以一场完整对局长度 15 的商数即为区间 [t_0, t_1] 内完整对局的个数。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numberOfRounds(string startTime, string finishTime) {
        // 转化为分钟
        int t0 = 60 * stoi(startTime.substr(0, 2)) + stoi(startTime.substr(3, 5));
        int t1 = 60 * stoi(finishTime.substr(0, 2)) + stoi(finishTime.substr(3, 5));
        if (t1 < t0){
            // 此时 finishTime 为第二天
            t1 += 1440;
        }
        // 第一个小于等于 finishTime 的完整对局的结束时间
        t1 = t1 / 15 * 15;
        return max(0, (t1 - t0)) / 15;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def numberOfRounds(self, startTime: str, finishTime: str) -> int:
        # 转化为分钟
        t0 = 60 * int(startTime[:2]) + int(startTime[3:])
        t1 = 60 * int(finishTime[:2]) + int(finishTime[3:])
        if t1 < t0:
            # 此时 finishTime 为第二天
            t1 += 1440
        # 第一个小于等于 finishTime 的完整对局的结束时间
        t1 = t1 // 15 * 15
        return max(0, (t1 - t0)) // 15

复杂度分析

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

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

 Comments
On this page
1904-你完成的完整对局数