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

🟢   🔖  贪心 字符串  🔗 力扣 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 _currenttocorrect.

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	统计共同度过的日子数		数学 字符串	🟢	🀄️ 🔗