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

题目

给你两个字符串 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-operations-to-convert-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目保证了，因此先算比多的分钟数，然后贪心地使用大的分钟数进行增加操作，即依次使用增加。

猜测一下，这里可以贪心的原因是四个数可以互相除尽，如果把换成就不行了，例如代码中如果为，贪心会得到，而答案是。这时就需要使用零钱兑换的解法了。

代码

class Solution {
    public int convertTime(String current, String correct) {
        int h1 = Integer.parseInt(current.substring(0, 2));
        int h2 = Integer.parseInt(correct.substring(0, 2));
        int m1 = Integer.parseInt(current.substring(3, 5));
        int m2 = Integer.parseInt(correct.substring(3, 5));
        int k = (h2 - h1) * 60 + m2 - m1;
        int ans = 0;
        ans += k / 60;
        k %= 60;
        ans += k / 15;
        k %= 15;
        ans += k / 5;
        k %= 5;
        ans += k;
        return ans;
    }
}