資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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"]
輸出
167
更新於：2020年5月4日
376 次檢視
廣告