给定数字能组成的最大时间

难度: Medium

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。

24 小时格式为 "HH:MM" ，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00 ，而最大的是 23:59 。从 00:00 （午夜）开始算起，过得越久，时间越大。

以长度为 5 的字符串，按 "HH:MM" 格式返回答案。如果不能确定有效时间，则返回空字符串。

示例 1：

输入：arr = [1,2,3,4]
输出："23:41"
解释：有效的 24 小时制时间是 "12:34"，"12:43"，"13:24"，"13:42"，"14:23"，"14:32"，"21:34"，"21:43"，"23:14" 和 "23:41" 。这些时间中，"23:41" 是最大时间。

示例 2：

输入：arr = [5,5,5,5]
输出：""
解释：不存在有效的 24 小时制时间，因为 "55:55" 无效。

示例 3：

输入：arr = [0,0,0,0]
输出："00:00"

示例 4：

输入：arr = [0,0,1,0]
输出："10:00"

提示：

arr.length == 4
0 <= arr[i] <= 9

Submission

运行时间: 20 ms

内存: 16.0 MB

from itertools import permutations
from typing import List

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        max_time = ""
        
        # 生成所有可能的排列组合
        for perm in permutations(arr):
            hour = perm[0] * 10 + perm[1]
            minute = perm[2] * 10 + perm[3]
            
            # 检查时间是否有效
            if hour < 24 and minute < 60:
                # 将时间格式化为字符串，并更新最大时间
                time_str = f"{hour:02d}:{minute:02d}"
                if time_str > max_time:
                    max_time = time_str
        
        return max_time

Explain

该题解的思路是使用Python的itertools.permutations来生成数组arr的所有可能的排列组合。每一个排列代表一个时间的尝试，其中排列的前两位数字组合成小时，后两位组合成分钟。然后，这个解决方案会检查每个生成的时间是否符合24小时制的有效时间（即小时数小于24，分钟数小于60）。如果是有效时间，就将其转换成HH:MM的格式，并与之前保存的最大时间进行比较。最后返回最大的有效时间字符串。如果没有找到任何有效的时间，则返回空字符串。

时间复杂度: O(1)

空间复杂度: O(1)

from itertools import permutations
from typing import List

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        max_time = ''  # 用于存储最大的有效时间
        
        # 生成所有可能的排列组合
        for perm in permutations(arr):
            hour = perm[0] * 10 + perm[1]  # 计算小时数
            minute = perm[2] * 10 + perm[3]  # 计算分钟数
            
            # 检查时间是否有效
            if hour < 24 and minute < 60:
                # 将时间格式化为字符串，并更新最大时间
                time_str = f'{hour:02d}:{minute:02d}'
                if time_str > max_time:
                    max_time = time_str
        
        return max_time  # 返回最大有效时间，如果没有有效时间则返回空字符串

Explore

当输入数组中包含重复数字时，itertools.permutations会生成一些重复的时间组合。这不会改变算法找到最大时间的能力，但会降低算法的性能，因为它需要检查更多的（重复的）时间组合。尽管重复的组合对最终输出的结果没有影响，因为最大时间仍然会被正确地计算出来，但这些重复计算增加了不必要的计算量，导致效率下降。

是的，当所有数字均大于5时，不可能组成一个有效的时间，因为小时数的第一位最大为2，分钟数的第一位最大为5。算法会检查所有排列的小时数是否小于24，分钟数是否小于60，而所有数字均大于5的情况下生成的任何时间都不会满足这些条件。因此，这种情况下算法返回空字符串是正确的处理方式，有效地表示没有可能的有效时间可以被生成。