LeetCode 2224. 转化时间需要的最少操作数（贪心）

Michael阿明

发布于 2022-11-27 17:11:18

2520

发布于 2022-11-27 17:11:18

文章被收录于专栏：Michael阿明学习之路

文章目录

1. 题目

给你两个字符串 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

贪心，优先使用大的数字

class Solution {
public:
    int convertTime(string current, string correct) {
        int diff = getminutes(correct)-getminutes(current);
        int ans = 0;
        operate(diff, ans, 60);
        operate(diff, ans, 15);
        operate(diff, ans, 5);
        operate(diff, ans, 1);
        return ans;
    }
    int getminutes(string s)
    {
        return ((s[0]-'0')*10+(s[1]-'0'))*60+(s[3]-'0')*10+(s[4]-'0');
    }
    void operate(int& diff, int& ans, int interval)
    {
        if(diff >= interval)
        {
            ans += diff/interval;
            diff -= diff/interval*interval;
        }
    }
};

0 ms 5.8 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-02，如有侵权请联系 cloudcommunity@tencent.com 删除

https