Easy

题目描述

给你两个字符串 current 和 correct，表示两个 24 小时制的时间。

24 小时制时间按 "HH:MM" 格式表示，其中 HH 在 00 和 23 之间，MM 在 00 和 59 之间。最早的 24 小时制时间为 00:00，最晚的为 23:59。

在一次操作中，你可以将 current 这个时间增加 1、5、15 或 60 分钟。你可以执行这一操作 任意 次数。

返回将 current 转换为 correct 需要的 最少操作数。

示例 1：

输入：current = "02:30", correct = "04:35"
输出：3
解释：
可以按下述 3 步操作将 current 转换为 correct：
- 为 current 加 60 分钟，current 变为 "03:30"。
- 为 current 加 60 分钟，current 变为 "04:30"。  
- 为 current 加 5 分钟，current 变为 "04:35"。
可以证明，无法用少于 3 步操作将 current 转换为 correct。

示例 2：

输入：current = "11:00", correct = "11:01"
输出：1
解释：只需要为 current 加一分钟，所以最小操作数是 1。

提示：

  • current 和 correct 都符合 "HH:MM" 格式
  • current <= correct

解题思路

这是一个经典的贪心算法问题。核心思路是优先使用最大面额的操作，这样能保证操作次数最少。

算法步骤：

  1. 时间转换：将字符串格式的时间转换为总分钟数，便于计算差值
  2. 计算差值：得到目标时间与当前时间的分钟差
  3. 贪心选择：按照 60、15、5、1 的顺序，优先使用最大的操作值

贪心策略的正确性：

  • 由于我们要最小化操作次数，应该优先使用最大面额
  • 60、15、5、1 这四个数值之间有整除关系，使用贪心策略是最优的
  • 类似于找零钱问题，当硬币面额有倍数关系时，贪心策略可以得到最优解

时间复杂度分析：

  • 字符串解析：O(1)
  • 贪心计算：最多4次除法操作，O(1)
  • 总体复杂度：O(1)

这种方法简单高效，代码实现清晰，是处理此类问题的标准解法。

代码实现

class Solution {
public:
    int convertTime(string current, string correct) {
        // 将时间字符串转换为分钟数
        auto timeToMinutes = [](const string& time) {
            int hours = stoi(time.substr(0, 2));
            int minutes = stoi(time.substr(3, 2));
            return hours * 60 + minutes;
        };
        
        int currentMinutes = timeToMinutes(current);
        int correctMinutes = timeToMinutes(correct);
        int diff = correctMinutes - currentMinutes;
        
        // 贪心策略：优先使用最大的操作值
        int operations = 0;
        vector<int> increments = {60, 15, 5, 1};
        
        for (int increment : increments) {
            operations += diff / increment;
            diff %= increment;
        }
        
        return operations;
    }
};

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        # 将时间字符串转换为分钟数
        def time_to_minutes(time):
            hours, minutes = map(int, time.split(':'))
            return hours * 60 + minutes
        
        current_minutes = time_to_minutes(current)
        correct_minutes = time_to_minutes(correct)
        diff = correct_minutes - current_minutes
        
        # 贪心策略：优先使用最大的操作值
        operations = 0
        increments = [60, 15, 5, 1]
        
        for increment in increments:
            operations += diff // increment
            diff %= increment
            
        return operations

public class Solution {
    public int ConvertTime(string current, string correct) {
        // 将时间字符串转换为分钟数
        int TimeToMinutes(string time) {
            string[] parts = time.Split(':');
            int hours = int.Parse(parts[0]);
            int minutes = int.Parse(parts[1]);
            return hours * 60 + minutes;
        }
        
        int currentMinutes = TimeToMinutes(current);
        int correctMinutes = TimeToMinutes(correct);
        int diff = correctMinutes - currentMinutes;
        
        // 贪心策略：优先使用最大的操作值
        int operations = 0;
        int[] increments = {60, 15, 5, 1};
        
        foreach (int increment in increments) {
            operations += diff / increment;
            diff %= increment;
        }
        
        return operations;
    }
}

var convertTime = function(current, correct) {
    // 将时间字符串转换为分钟数
    const timeToMinutes = (time) => {
        const [hours, minutes] = time.split(':').map(Number);
        return hours * 60 + minutes;
    };
    
    const currentMinutes = timeToMinutes(current);
    const correctMinutes = timeToMinutes(correct);
    let diff = correctMinutes - currentMinutes;
    
    // 贪心策略：优先使用最大的操作值
    let operations = 0;
    const increments = [60, 15, 5, 1];
    
    for (const increment of increments) {
        operations += Math.floor(diff / increment);
        diff %= increment;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)字符串解析和贪心计算都是常数时间操作
空间复杂度O(1)只使用了常数个额外变量

相关题目