每日一题(2022-01-18):最小时间差

每日一题(2022-01-18):最小时间差

来源:力扣
难度:中等
题目:539. 最小时间差

题目详情

原题截图.png

题解思路

虽然标注为中等难度,但是感觉上也就只有简单题目的难度,思路很常规,排序作差比较,如果真要说的话,有一个技巧和一个坑:

  • 一个技巧,鸽巢原理:在24小时中,如果以分钟为最小计时单位,那么一共有24 * 40 = 1440种不同的时间点,所以如果给出的时间列表的长度大于1440,那么列表中必然会有重复的时间点,那么最小时间差就是0;
  • 一个坑,排序后的首尾时间差:举个例子,在题目的设置中,00:0023:59之间的时间差是1分钟,但是如果仅仅是比较排序后数组中相邻的两个时间点,就可能遗漏首尾时间差是最小的这种情况;
  • 除此之外,还有几个值得注意的地方:由于表示的时间的字符串格式一致,所以在将时间点字符串转数字时间的时候,可以直接按位置索引取对应位置字符作差得到具体值;并且,对时间点排序时可以直接对原始字符串列表排序,排序的结果和转换为数值时间后的排序结果一致;

代码结果

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 1440) return 0;

        sort(timePoints.begin(), timePoints.end());
        int iMinDiff = 1440 + _ConvertToMinutes(timePoints[0])
            - _ConvertToMinutes(timePoints[timePoints.size() - 1]);
        if (iMinDiff == 0) return 0;

        int iPreTime = _ConvertToMinutes(timePoints[0]);
        for (int i = 1; i < timePoints.size(); ++i)
        {
            int iCurrTime = _ConvertToMinutes(timePoints[i]);
            iMinDiff = min(iMinDiff, iCurrTime - iPreTime);
            iPreTime = iCurrTime;
        }
        return iMinDiff;
    }

private:
    int _ConvertToMinutes(const string& timePoint)
    {
        return (int(timePoint[0] - '0') * 10 + int(timePoint[1] - '0')) * 60
            + int(timePoint[3] - '0') * 10 + int(timePoint[4] - '0');
    }
};

运行结果.png