Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.
Example 1:
Input: [“23:59”,”00:00”] Output: 1
Note:
The number of time points in the given list is at least 2 and won’t exceed 20000.The input time is legal and ranges from 00:00 to 23:59.题目内容： 题目给出一个时间的数组，每个时间的格式是”Hour:Minutes”，包括小时和分钟数，我们要求出每两个时间之间最小的分钟间隔。例如”23:59”和”00:00”之间只差了1一分钟，所以返回1。
解题思路： 因为对于所有可能的时间，总共有24 * 60=1440种可能，所以其实可以直接用一个数组来表示某个时间是否存在于给出的数组当中。 首先创建一个1440维的bool型数组，并初始化每一个元素的初始值为false。而每个时间对应的下表也很容易算出来，可以用以下的公式算出：
index=Hour∗60+Minutes 接着，遍历数组，求出每个时间元素对应的下标，将bool数组这个下标的元素设为true， 如果这个元素在这之前已经被设为true，表明数组中至少有2个相同的时间，那么最小的时间间隔就是0，可以直接返回。 接下来，我们已经知道了存在哪些时间，可以遍历一下数组，计算每2个设为true的元素下标之间的差，但是我们不能直接相减， 因为其实这个数组可以看做是循环的。例如题目给出的例子中，”23:59”和”00:00”不是差 23∗60+59 分钟，而是差了1分钟。所以，对于每个时间，我们还必须计算这个时间与第一个时间的差。假如当前为true的时间下标为 current，上一个时间为true的时间下标为 last，第一个时间的下标为 first，数组名为 times，当前最小时间间隔为 min，那么 min=MIN(current−last,24∗60−current+first) 通过这个公式，遍历一次times数组，采用贪心算法就可以得到最后的结果。代码：
class Solution { public: int findMinDifference(vector<string>& timePoints) { bool* times = new bool[24 * 60]; for (int i = 0; i < 24 * 60; i++) times[i] = false; for (int i = 0; i < timePoints.size(); i++) { int index = str2Index(timePoints[i]); if (times[index] == true) return 0; times[index] = true; } int min = INT_MAX; int first = -1; for (int i = 0; i < 24 * 60; i++) { if (times[i] == true && first == -1) first = i; } int last = -1; int current = -1; for (int i = 0; i < 24 * 60; i++) { if (times[i] == false) continue; if (last == -1) { last = i; continue; } else if (current == -1) { current = i; } else { last = current; current = i; } if (min > 24 * 60 - current + first) min = 24 * 60 - current + first; if (min > current - last) min = current - last; } delete[] times; return min; } int str2Index(string str) { int splitPos = str.find(":"); int hour = str2Int(str.substr(0, splitPos)); int min = str2Int(str.substr(splitPos + 1)); return hour * 60 + min; } int str2Int(string str) { int re; stringstream stream(str); stream >> re; return re; } };