题目如下:
LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.
You are given a list of strings
keyName
andkeyTime
where[keyName[i], keyTime[i]]
corresponds to a person's name and the time when their key-card was used in a single day.Access times are given in the 24-hour time format "HH:MM", such as
"23:51"
and"09:49"
.Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.
Notice that
"10:00"
-"11:00"
is considered to be within a one-hour period, while"22:51"
-"23:52"
is not considered to be within a one-hour period.Example 1:
Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"] Output: ["daniel"] Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").Example 2:
Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"] Output: ["bob"] Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").Constraints:
1 <= keyName.length, keyTime.length <= 105
keyName.length == keyTime.length
keyTime[i]
is in the format "HH:MM".[keyName[i], keyTime[i]]
is unique.1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.
解题思路:使用字典,以名字作为key,时间用list的方式有序存储,依次把时间存入list中,如果一个时间的插入位置是i,判断 i-2~i,i-1~i+1,i ~ i+2三个区间的间隔是否小于一小时。
代码如下:
class Solution(object): def alertNames(self, keyName, keyTime): """ :type keyName: List[str] :type keyTime: List[str] :rtype: List[str] """ res = set() def convert(time): hour,min = time.split(':') return int(hour) * 60 + int(min) import bisect dic = {} for name,time in zip(keyName,keyTime): if name not in dic: dic[name] = [convert(time)] else: converted_time = convert(time) bisect.insort_left(dic[name],converted_time) inx = bisect.bisect_left(dic[name],converted_time) if inx - 2 >= 0 and dic[name][inx] - dic[name][inx-2] <= 60: res.add(name) elif inx + 2 < len(dic[name]) and dic[name][inx+2] - dic[name][inx] <= 60: res.add(name) elif inx -1 >= 0 and inx + 1 < len(dic[name]) and dic[name][inx+1] - dic[name][inx-1] <= 60: res.add(name) return sorted(list(res))