-
发表于 2024.05.28
-
这道题没啥比较高效的做法，官方题解也是暴力枚举。因为时间的范围是固定的，所以可以直接暴力枚举所有可能的时间，然后找到最大的时间即可。为了尽可能减少枚举的次数，可以先对输入的数字进行排序，然后按照
HH:MM的格式，从大到小枚举所有可能的时间，找到第一个合法的时间即可。class Solution: def largestTimeFromDigits(self, arr: List[int]) -> str: arr.sort() visited = [False] * 4 ans = "" def traceback(cur: List[int]) -> bool: nonlocal ans pos = len(cur) if pos == 4: ans = f"{cur[0]}{cur[1]}:{cur[2]}{cur[3]}" return True for i in range(3, -1, -1): # 从大到小进行排序 if visited[i]: continue if pos == 0 and arr[i] > 2: # 第一个数字需要满足的条件: 不能大于2 continue if pos == 1 and cur[0] == 2 and arr[i] >= 4: # 第二个数字需满足的条件, 如果小时为20+，则不能大于24 continue if pos == 2 and arr[i] >= 6: # 第三个数字需满足的条件：不能大于等于6 continue visited[i] = True cur.append(arr[i]) if traceback(cur): # 找到第一个满足条件的构造即可 return True visited[i] = False cur.pop() return False traceback([]) return ans - LC 题目链接
-
