1904-你完成的完整对局数(The Number of Full Rounds You Have Played)

原文链接: https://leetcode-cn.com/problems/the-number-of-full-rounds-you-have-played

英文原文

A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

For example, if startTime = "05:20" and finishTime = "05:59" this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

Example 1:

Input: startTime = "12:01", finishTime = "12:44"
Output: 1
Explanation: You played one full round from 12:15 to 12:30.
You did not play the full round from 12:00 to 12:15 because you started playing at 12:01 after it began.
You did not play the full round from 12:30 to 12:45 because you stopped playing at 12:44 before it ended.

Example 2:

Input: startTime = "20:00", finishTime = "06:00"
Output: 40
Explanation: You played 16 full rounds from 20:00 to 00:00 and 24 full rounds from 00:00 to 06:00.
16 + 24 = 40.

Example 3:

Input: startTime = "00:00", finishTime = "23:59"
Output: 95
Explanation: You played 4 full rounds each hour except for the last hour where you played 3 full rounds.

Constraints:

startTime and finishTime are in the format HH:MM.
00 <= HH <= 23
00 <= MM <= 59
startTime and finishTime are not equal.

中文题目

一款新的在线电子游戏在近期发布，在该电子游戏中，以刻钟为周期规划若干时长为 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$ 为时间零点，同时将 $\textit{startTime}$ 和 $\textit{finishTime}$ 转化为距离时间零点的分钟数 $t_0$ 和 $t_1$。

此处要注意，如果转换后的 $t_1 < t_0$，这说明 $\textit{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++]
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]
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)$。

统计信息

通过次数	提交次数	AC比率
3768	13175	28.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途