转化时间需要的最少操作数

难度: 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

Submission

运行时间: 22 ms

内存: 16.2 MB

def minutes(current):
    return reduce(lambda x, y: int(x) * 60 + int(y), current.split(':'))

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        if (m := minutes(correct) - minutes(current)) < 0:
            m += 24 * 60
        return sum(p[0] for p in accumulate([60, 15, 5, 1], lambda p, u: divmod(p[1], u), initial=(0, m)))

Explain

此题解采用贪心算法的思路。首先，将当前时间和正确时间转换为分钟数，然后计算它们之间的时间差。接着，从最大的时间单位（60分钟）开始，尽可能多地使用该时间单位进行转换，直到剩余时间小于该时间单位。然后，切换到下一个较小的时间单位（15分钟、5分钟、1分钟），重复上述过程，直到剩余时间为0。这样可以保证操作次数最少。

时间复杂度: O(1)

空间复杂度: O(1)

from itertools import accumulate
from functools import reduce

def minutes(current):
    # 将时间字符串转换为分钟数
    return reduce(lambda x, y: int(x) * 60 + int(y), current.split(':'))

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        # 计算时间差（以分钟为单位）
        m = minutes(correct) - minutes(current)
        if m < 0:
            m += 24 * 60  # 如果时间差为负，说明跨天了，需要加上一天的分钟数
        # 使用accumulate计算各时间单位所需的操作次数，并求和
        return sum(p[0] for p in accumulate([60, 15, 5, 1], lambda p, u: divmod(p[1], u), initial=(0, m)))