原文链接: https://leetcode-cn.com/problems/largest-time-for-given-digits

英文原文

Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

Return the latest 24-hour time in "HH:MM" format.  If no valid time can be made, return an empty string.

 

Example 1:

Input: arr = [1,2,3,4]
Output: "23:41"
Explanation: The valid 24-hour times are "12:34", "12:43", "13:24", "13:42", "14:23", "14:32", "21:34", "21:43", "23:14", and "23:41". Of these times, "23:41" is the latest.

Example 2:

Input: arr = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.

Example 3:

Input: arr = [0,0,0,0]
Output: "00:00"

Example 4:

Input: arr = [0,0,1,0]
Output: "10:00"

 

Constraints:

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

中文题目

给定一个由 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

通过代码

官方题解

方法一： 暴力

思路

遍历所有可能的时间，找到最大的那个。

算法

用 (i, j, k, l) 表示 (0, 1, 2, 3)，之后做全排列，对于每个排列，会有 A[i]A[j] : A[k]A[l]。

检查每个排列对应的时间是否合法，例如检查 10*A[i] + A[j] 是不是小于 24 10*A[k] + A[l] 是不是小于 60。

最后把最大的有效时间输出就可以了。

算法

遍历这四个数字所有排列的可能，判断是不是一个合法的时间，如果合法且比目前存在的最大时间更大，就更新这个最大时间。

[solution1-Java]
// Solution inspired by @rock
class Solution {
    public String largestTimeFromDigits(int[] A) {
        int ans = -1;

        // Choose different indices i, j, k, l as a permutation of 0, 1, 2, 3
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j) if (j != i)
                for (int k = 0; k < 4; ++k) if (k != i && k != j) {
                    int l = 6 - i - j - k;

                    // For each permutation of A[i], read out the time and
                    // record the largest legal time.
                    int hours = 10 * A[i] + A[j];
                    int mins = 10 * A[k] + A[l];
                    if (hours < 24 && mins < 60)
                        ans = Math.max(ans, hours * 60 + mins);
                }

        return ans >= 0 ? String.format("%02d:%02d", ans / 60, ans % 60) : "";
    }
}

[solution1-Python]
class Solution(object):
    def largestTimeFromDigits(self, A):
        ans = -1
        for h1, h2, m1, m2 in itertools.permutations(A):
            hours = 10 * h1 + h2
            mins = 10 * m1 + m2
            time = 60 * hours + mins
            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:
                ans = time

        return "{:02}:{:02}".format(*divmod(ans, 60)) if ans >= 0 else ""

复杂度分析

• 时间复杂度： $O(1)$。

• 空间复杂度： $O(1)$。

统计信息

通过次数	提交次数	AC比率
8641	23216	37.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言