假设我们有一个“小时:分钟”格式的24小时制时钟点列表,我们必须找到列表中任何两个时间点之间的最小分钟差。因此,如果输入类似于[“ 12:30”,“ 15:17”],则返回167。
为了解决这个问题,我们将遵循以下步骤-
定义一个大小为24 * 60 + 1的名为ok的数组,并且最初都为假。
n:= tp的大小
对于i,范围为0至n – 1
hr:=从时间开始的小时部分
min:=字符串的分钟部分
时间:=小时* 60 +分钟
如果ok [time]为true,则返回0,否则将ok [time]设置为true。
最后一个:= 0,第一个:= inf,ret:= inf,上一个:= -inf
适用于0到24 * 60范围内的i
最后:=我的最大值,最后
第一:=我的第一和第二
如果prev不是–inf,则ret:= ret的最小值,最后一次– prev
上一个:=我
如果ok [i]为真,则
返回最小的ret和24 * 60 + first-last。
让我们看下面的实现,以更好地了解&mnus;
#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"]
输出结果
167