Skip to content

Latest commit

 

History

History
159 lines (122 loc) · 5.58 KB

2224.md

File metadata and controls

159 lines (122 loc) · 5.58 KB
title description keywords
2224. 转化时间需要的最少操作数
LeetCode 2224. 转化时间需要的最少操作数题解，Minimum Number of Operations to Convert Time，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
2224. 转化时间需要的最少操作数
转化时间需要的最少操作数
Minimum Number of Operations to Convert Time
解题思路
贪心
字符串

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

🟢 Easy  🔖  贪心 字符串  🔗 力扣 LeetCode

题目

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return _theminimum number of operations needed to convert _current tocorrect.

Example 1:

Input: current = "02:30", correct = "04:35"

Output: 3

Explanation: We can convert current to correct in 3 operations as follows:

  • Add 60 minutes to current. current becomes "03:30".
  • Add 60 minutes to current. current becomes "04:30".
  • Add 5 minutes to current. current becomes "04:35".

It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Example 2:

Input: current = "11:00", correct = "11:01"

Output: 1

Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.

Constraints:

  • current and correct are in the format "HH:MM"
  • current <= correct

题目大意

给你两个字符串 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. 计算时间差：

    • 将 current 和 correct 转换为分钟数表示，方便计算时间差 diff： diff = correct_hour * 60 + correct_minute - (current_hour * 60 + current_minute)

  2. 贪心算法：

    • 使用贪心法，从大到小尝试减少时间差：
      • 如果剩余的时间差大于等于 60 分钟，则优先使用 60 分钟操作。
      • 如果剩余的时间差小于 60 分钟但大于等于 15 分钟，则使用 15 分钟操作。
      • 如果剩余的时间差小于 15 分钟但大于等于 5 分钟，则使用 5 分钟操作。
      • 如果剩余的时间差小于 5 分钟，则使用 1 分钟操作。
    • 每次操作后，将操作次数加一 res++。

复杂度分析

  • 时间复杂度：O(1)，每次操作减少 diff 的值，常数次操作。
  • 空间复杂度：O(1)，仅使用常量空间存储变量。

代码

/**
 * @param {string} current
 * @param {string} correct
 * @return {number}
 */
var convertTime = function (current, correct) {
	// 计算时间差（以分钟为单位）
	let diff =
		(Number(correct.slice(0, 2)) - Number(current.slice(0, 2))) * 60 +
		(Number(correct.slice(3)) - Number(current.slice(3)));

	let res = 0;

	// 使用贪心法减小时间差
	while (diff > 0) {
		if (diff >= 60) {
			diff -= 60;
		} else if (diff >= 15) {
			diff -= 15;
		} else if (diff >= 5) {
			diff -= 5;
		} else {
			diff -= 1;
		}
		res++;
	}

	return res;
};

相关题目

题号 标题 题解 标签 难度 力扣
322 零钱兑换 [✓] 广度优先搜索 数组 动态规划 🟠 🀄️ 🔗
2241 设计一个 ATM 机器 贪心 设计 数组 🟠 🀄️ 🔗
2409 统计共同度过的日子数 数学 字符串 🟢 🀄️ 🔗