JZX轻语：简
LeetCode 949- 给定数字能组成的最大时间
发表于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