C++中的最小时间差
假设我们有一列24小时制的时间点,格式为“小时:分钟”,我们需要找到列表中任意两个时间点之间的最小分钟差。例如,如果输入为[“12:30”,“15:17”],则返回167。
为了解决这个问题,我们将遵循以下步骤:
- 定义一个大小为24*60+1的数组ok,初始值都为false。
- n := tp的大小
- 对于i从0到n-1
- hr := 时间的小时部分
- min := 字符串的分钟部分
- time := hr * 60 + min
- 如果ok[time]为true,则返回0,否则将ok[time]设置为true。
- last := 0, first := inf, ret := inf, prev := -inf
- 对于i从0到24*60
- 如果ok[i]为true,则
- last := i和last的最大值
- first := i和first的最小值
- 如果prev不为–inf,则ret := ret和last – prev的最小值
- prev := i
- 如果ok[i]为true,则
- 返回ret和24*60+first-last的最小值。
让我们看看下面的实现来更好地理解;
示例
#include <bits/stdc++.h> using namespace std; class Solution { public: int findMinDifference(vector<string>& tp) { vector <bool> ok(24 * 60 + 1, false); int n = tp.size(); for(int i = 0; i < n; i++){ int hr = stoi(tp[i].substr(0, 2)); int min = stoi(tp[i].substr(3, 2)); int time = hr * 60 + min; if(ok[time]) return 0; ok[time] = true; } int last = 0; int first = INT_MAX; int ret = INT_MAX; int prev = INT_MIN; for(int i = 0; i <= 24 * 60; i++){ if(ok[i]){ last = max(i, last); first = min(i, first); if(prev != INT_MIN) ret = min(ret, last - prev); prev = i; } } return min(ret, 24 * 60 + first - last); } }; main(){ vector<string> v = {"12:30","15:17"}; Solution ob; cout << (ob.findMinDifference(v)); }
输入
["12:30","15:17"]
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
167
广告