Medium

题目描述

你正在参加一个在线国际象棋锦标赛。每 15 分钟开始一个国际象棋回合。一天的第一回合从 00:00 开始，之后每隔 15 分钟开始一个新回合。

例如，第二回合从 00:15 开始，第四回合从 00:45 开始，第七回合从 01:30 开始。

给你两个字符串 loginTime 和 logoutTime，其中：

  • loginTime 是你登录游戏的时间
  • logoutTime 是你退出游戏的时间

如果 logoutTime 早于 loginTime，这意味着你从 loginTime 玩到午夜，然后从午夜玩到 logoutTime。

返回你在锦标赛中玩了多少场完整的国际象棋回合。

注意：所有给定时间都遵循 24 小时制。这意味着一天的第一回合从 00:00 开始，一天的最后回合从 23:45 开始。

示例 1：

输入：loginTime = "09:31", logoutTime = "10:14"
输出：1
解释：你从 09:45 到 10:00 玩了一个完整回合。
你没有玩从 09:30 到 09:45 的完整回合，因为你在 09:31 登录，回合已经开始了。
你没有玩从 10:00 到 10:15 的完整回合，因为你在 10:14 退出，回合还没结束。

示例 2：

输入：loginTime = "21:30", logoutTime = "03:00"
输出：22
解释：你从 21:30 到 00:00 玩了 10 个完整回合，从 00:00 到 03:00 玩了 12 个完整回合。
10 + 12 = 22。

约束条件：

  • loginTime 和 logoutTime 的格式为 hh:mm
  • 00 <= hh <= 23
  • 00 <= mm <= 59
  • loginTime 和 logoutTime 不相等

解题思路

解题思路

这道题的核心是理解每 15 分钟为一个回合，以及处理跨午夜的情况。

主要思路：

  1. 时间转换：将时间字符串转换为分钟数，便于计算。一天有 1440 分钟。

  2. 处理跨午夜情况：如果 logoutTime 小于 loginTime，说明跨越了午夜，需要将 logoutTime 加上 1440 分钟（一天的分钟数）。

  3. 找到有效的游戏时间段：

    • 登录后的第一个可能完整回合开始时间：将登录时间向上取整到最近的 15 分钟倍数
    • 退出前的最后一个完整回合结束时间：将退出时间向下取整到最近的 15 分钟倍数

  4. 计算完整回合数：用结束时间减去开始时间，然后除以 15，就是完整回合数。

具体算法：

  • 将时间转换为分钟：时 * 60 + 分
  • 向上取整到 15 的倍数：(分钟数 + 14) / 15 * 15
  • 向下取整到 15 的倍数：分钟数 / 15 * 15
  • 如果开始时间不小于结束时间，则没有完整回合

这种方法时间复杂度为 O(1)，空间复杂度也为 O(1)，是最优解。

代码实现

class Solution {
public:
    int numberOfRounds(string loginTime, string logoutTime) {
        int login = timeToMinutes(loginTime);
        int logout = timeToMinutes(logoutTime);
        
        // 处理跨午夜的情况
        if (logout <= login) {
            logout += 1440; // 加一天的分钟数
        }
        
        // 找到登录后第一个可能的完整回合开始时间（向上取整到15的倍数）
        int start = ((login + 14) / 15) * 15;
        
        // 找到退出前最后一个完整回合结束时间（向下取整到15的倍数）
        int end = (logout / 15) * 15;
        
        // 计算完整回合数
        return max(0, (end - start) / 15);
    }
    
private:
    int timeToMinutes(const string& time) {
        int hour = stoi(time.substr(0, 2));
        int minute = stoi(time.substr(3, 2));
        return hour * 60 + minute;
    }
};

class Solution:
    def numberOfRounds(self, loginTime: str, logoutTime: str) -> int:
        def time_to_minutes(time_str):
            hour, minute = map(int, time_str.split(':'))
            return hour * 60 + minute
        
        login = time_to_minutes(loginTime)
        logout = time_to_minutes(logoutTime)
        
        # 处理跨午夜的情况
        if logout <= login:
            logout += 1440  # 加一天的分钟数
        
        # 找到登录后第一个可能的完整回合开始时间（向上取整到15的倍数）
        start = ((login + 14) // 15) * 15
        
        # 找到退出前最后一个完整回合结束时间（向下取整到15的倍数）
        end = (logout // 15) * 15
        
        # 计算完整回合数
        return max(0, (end - start) // 15)

public class Solution {
    public int NumberOfRounds(string loginTime, string logoutTime) {
        int login = TimeToMinutes(loginTime);
        int logout = TimeToMinutes(logoutTime);
        
        // 处理跨午夜的情况
        if (logout <= login) {
            logout += 1440; // 加一天的分钟数
        }
        
        // 找到登录后第一个可能的完整回合开始时间（向上取整到15的倍数）
        int start = ((login + 14) / 15) * 15;
        
        // 找到退出前最后一个完整回合结束时间（向下取整到15的倍数）
        int end = (logout / 15) * 15;
        
        // 计算完整回合数
        return Math.Max(0, (end - start) / 15);
    }
    
    private int TimeToMinutes(string time) {
        string[] parts = time.Split(':');
        int hour = int.Parse(parts[0]);
        int minute = int.Parse(parts[1]);
        return hour * 60 + minute;
    }
}

var numberOfRounds = function(loginTime, logoutTime) {
    function timeToMinutes(timeStr) {
        const [hour, minute] = timeStr.split(':').map(Number);
        return hour * 60 + minute;
    }
    
    let login = timeToMinutes(loginTime);
    let logout = timeToMinutes(logoutTime);
    
    // 处理跨午夜的情况
    if (logout <= login) {
        logout += 1440; // 加一天的分钟数
    }
    
    // 找到登录后第一个可能的完整回合开始时间（向上取整到15的倍数）
    const start = Math.floor((login + 14) / 15) * 15;
    
    // 找到退出前最后一个完整回合结束时间（向下取整到15的倍数）
    const end = Math.floor(logout / 15) * 15;
    
    // 计算完整回合数
    return Math.max(0, (end - start) / 15);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(1)
空间复杂度O(1)

复杂度分析：

  • 时间复杂度：O(1)，只进行常数次数的算术运算和字符串解析操作
  • 空间复杂度：O(1)，只使用了常数个额外变量