【问题描述】
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
【输入形式】
第一行输入一个不小于2，不大于1000的正整数n，之后输入n行，每行一个 HH:MM形式的字符串表示一个24小时制的时间
【输出形式】
只有一行，即最小时间差
public int findMinDifference(List<String> timePoints) {
int len = timePoints.size();
int[] a = new int[50000];
int j=0;
for(String i:timePoints) {
a[j++] = Integer.parseInt(i.substring(0, 2))*60+Integer.parseInt(i.substring(3, 5));
a[j++] = Integer.parseInt(i.substring(0, 2))*60+Integer.parseInt(i.substring(3, 5))+1440;
}
Arrays.sort(a,0,j);
int min=1440;
for(int i=1;i<j;i++) {
min=(a[i]-a[i-1])<=min?(a[i]-a[i-1]):min;
}
return min;
}
class Solution {
public int findMinDifference(List timePoints) {
int n=timePoints.size();
if(n>1440){
return 0;
}
int[] times=new int[n];
// 将时间全部转化为分钟
for(int i=0;i<n;i++){
String m=timePoints.get(i).substring(0,2);
String s=timePoints.get(i).substring(3,5);
times[i]=Integer.parseInt(m)*60+Integer.parseInt(s);
}
int result=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
// 两个时间最小时间
int time=Math.min(Math.abs(times[i]-times[j]),Math.abs(Math.abs(times[i]-times[j])-1440));
// 所有时间最小差
result=Math.min(time,result);
}
}
return result;
}
}
class Solution {
public int findMinDifference(List<String> timePoints) {
int n=timePoints.size();
if(n>1440){
return 0;
}
int[] times=new int[n];
// 将时间全部转化为分钟
for(int i=0;i<n;i++){
String m=timePoints.get(i).substring(0,2);
String s=timePoints.get(i).substring(3,5);
times[i]=Integer.parseInt(m)*60+Integer.parseInt(s);
}
int result=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
// 两个时间最小时间
int time=Math.min(Math.abs(times[i]-times[j]),Math.abs(Math.abs(times[i]-times[j])-1440));
// 所有时间最小差
result=Math.min(time,result);
}
}
return result;
}
}
class Solution
{
public:
int findMinDifference(vector& timePoints)
{
vector nums;
for (string t : timePoints)
{
int h = stoi(t.substr(0, 2));
int m = stoi(t.substr(3, 2));
int x = h * 60 + m;
nums.push_back(x);
nums.push_back(x + 1440);
}
sort(nums.begin(), nums.end());
int n = nums.size();
int res = INT_MAX;
for (int i = 1; i < n; i ++)
{
int x = nums[i - 1];
int y = nums[i];
res = min(res, y - x);
}
return res;
}
};
https://leetcode-cn.com/problems/minimum-time-difference/
这个题应该是Lecode上的题目，我去原网站上找了下原题，这样的解是没有问题的。
一天有 24小时，1440分钟，开一个1440长度的布尔数组模拟哈希表，把时间换算成0~1439之间的数值，将数值对应数组中的位置设置为true；
遍历数组，找离得最近的两个时间点。
class Solution {
private:
const int maxDiffTime = 1440;
public:
int findMinDifference(vector<string>& timePoints) {
//大于1440个时间，必有两个时间是重复的，即最小间隔为0
if (timePoints.size() > maxDiffTime) return 0;
bool minuteFlags[1440] = {0}; //不要用vector来存bool类型的值，因为不安全，取地址会报错
for (string& time : timePoints)
{
//将字符串表示的时间转换成总的分钟数
int minute = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
if (minuteFlags[minute]) return 0; //若该时间在数组中出现过，则最小时间间隔为0
minuteFlags[minute] = true;
}
//以上是一些优化操作，下面才开始遍历数组找最小间隔
return helper(minuteFlags);
}
int helper(bool minuteFlags[])
{
int minDiff = maxDiffTime - 1; //最小时间间隔初始化为最大
int prev = -1;
int first = maxDiffTime - 1; //first表示数组中最早的时间，last表示最晚的时间
int last = -1; //主要是为了计算00:00与23:59这类情况的
for (int cur = 0; cur < maxDiffTime; ++ cur)
{
if (minuteFlags[cur])
{
if (prev >= 0) minDiff = min(minDiff, cur - prev);
prev = cur; //更新上一节点，first和last节点
first = min(first, cur);
last = max(last, cur);
}
}
//计算00:00与23:59这类情况
minDiff = min(minDiff, first + maxDiffTime - last);
return minDiff;
}
};
public int findMinDifference(List<String> timePoints) {
int len = timePoints.size();
int[] a = new int[50000];
int j=0;
for(String i:timePoints) {
a[j++] = Integer.parseInt(i.substring(0, 2))*60+Integer.parseInt(i.substring(3, 5));
a[j++] = Integer.parseInt(i.substring(0, 2))*60+Integer.parseInt(i.substring(3, 5))+1440;
}
Arrays.sort(a,0,j);
int min=1440;
for(int i=1;i<j;i++) {
min=(a[i]-a[i-1])<=min?(a[i]-a[i-1]):min;
}
return min;
}