539. 最小时间差

https://leetcode-cn.com/problems/minimum-time-difference/

给定一个 24 小时制（小时:分钟）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入: ["23:59","00:00"]
输出: 1

备注:

列表中时间数在 2~20000 之间。
每个时间取值在 00:00~23:59 之间。

通过次数6,481 | 提交次数11,710

Second Try

2020-07-02

从题解了解到的思路，不用提前对每个时间加上一天，而是从一个环的角度来考虑。需要考虑第二天凌晨减去前一天晚上的这种情况，仅仅属于在列表中的最早和最晚的元素（第一个和最后一个），其他元素只要排好序然后一路计算间隔就好了。

本来觉得算是很高效的算法了，其实也只排到了25%。重点是如果出现相同元素，直接返回0，也就是len(set(arr)) != len(arr)的操作，有了这个检查直接就双百了。

# 前后一个环的版本

class Solution(object):
    def findMinDifference(self, timePoints):
        """
        :type timePoints: List[str]
        :rtype: int
        """
        # 这一步写在前面就是双百版本
        if len(set(timePoints)) != len(timePoints):
            return 0

        day = 24 * 60
        tomin = lambda x: int(x[:2]) * 60 + int(x[-2:])
        timePoints = sorted([tomin(x) for x in timePoints])
        mint = float('inf')
        for i in range(1, len(timePoints)):
            mint = min(mint, timePoints[i] - timePoints[i-1])
        # 继续考虑一个环
        mint = min(mint, timePoints[0] + day - timePoints[len(timePoints)-1]) 
        return mint    

执行用时：36 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：15.9 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-02

从比较朴素的角度来考虑的，每个时间都可以当作是今天，或者是第二天的时间，然后与其他时间进行比较。比较的过程中需要注意相邻的时间不是同一个时间衍生出来的，因此需要带上原时间标记。除此之外，一切都很正常。

列表里允许出现重复元素是没有想到的，考虑到这个判断之后，成功提交并且双百版本。说起来想到了每个时间提前加上24小时来处理之外，没看出这个题目到底要考什么。

class Solution(object):
    def findMinDifference(self, timePoints):
        """
        :type timePoints: List[str]
        :rtype: int
        """
        # 没想到还允许出现相等的时间，没想到啊没想到 ["00:00","23:59","00:00"]
        if len(set(timePoints)) != len(timePoints):
            return 0
        day = 24 * 60 
        to_min = lambda x: int(x[:2]) * 60 + int(x[-2:])
        seq = []
        for t in timePoints:
            seq.extend([[to_min(t), t],[to_min(t) + day, t]])
        seq = sorted(seq)
        gap = []
        for i in range(1, len(seq)):
            if seq[i][1] == seq[i-1][1]:
                continue
            gap.append((seq[i][0] - seq[i-1][0], [seq[i][1], seq[i-1][1]]))
        gap = sorted(gap)
        rv = gap[0][0]
        return rv    

执行用时：40 ms, 在所有 Python 提交中击败了100.00%的用户
内存消耗：16 MB, 在所有 Python 提交中击败了100.00%

539. 最小时间差​

Second Try​

First Try​

539. 最小时间差

Second Try

First Try