Medium

题目描述

给定一个由 4 位数字组成的数组 arr，找出可以组成的最晚的 24 小时制时间，每个数字恰好使用一次。

24 小时制时间格式为 “HH:MM”，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。最早的 24 小时制时间是 00:00，最晚的是 23:59。

返回最晚的 24 小时制时间，格式为 “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" 无效。

提示：

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

解题思路

解题思路

这道题需要从给定的 4 个数字中组成最大的有效时间。我们可以采用以下几种方法：

方法一：全排列枚举（推荐）

最直观的做法是生成所有可能的排列，然后检查每个排列是否能组成有效时间，记录最大的有效时间。

方法二：贪心策略

从高位到低位贪心选择最大的数字：

  1. 小时的十位数最大为 2
  2. 如果小时十位是 2，个位最大为 3；否则个位最大为 9
  3. 分钟的十位数最大为 5
  4. 分钟的个位数可以是 0-9

方法三：暴力枚举优化

从最大可能的时间 23:59 开始倒序枚举，检查能否用给定数字组成。

由于只有 4! = 24 种排列，数据规模很小，全排列方法简单且高效。我们采用全排列的方法，对于每个排列检查其是否构成有效时间，并维护最大值。

有效时间的条件：

  • 小时：00-23（十位数 ≤ 2，且当十位数为 2 时个位数 ≤ 3）
  • 分钟：00-59（十位数 ≤ 5）

代码实现

class Solution {
public:
    string largestTimeFromDigits(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        string result = "";
        
        do {
            int h1 = arr[0], h2 = arr[1], m1 = arr[2], m2 = arr[3];
            
            // 检查是否为有效时间
            if (h1 <= 2 && (h1 < 2 || h2 <= 3) && m1 <= 5) {
                string time = to_string(h1) + to_string(h2) + ":" + to_string(m1) + to_string(m2);
                if (time > result) {
                    result = time;
                }
            }
        } while (next_permutation(arr.begin(), arr.end()));
        
        return result;
    }
};

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        from itertools import permutations
        
        max_time = ""
        
        for perm in permutations(arr):
            h1, h2, m1, m2 = perm
            
            # 检查是否为有效时间
            if h1 <= 2 and (h1 < 2 or h2 <= 3) and m1 <= 5:
                time_str = f"{h1}{h2}:{m1}{m2}"
                if time_str > max_time:
                    max_time = time_str
        
        return max_time

public class Solution {
    public string LargestTimeFromDigits(int[] arr) {
        string result = "";
        
        // 生成所有排列
        var permutations = GetPermutations(arr);
        
        foreach (var perm in permutations) {
            int h1 = perm[0], h2 = perm[1], m1 = perm[2], m2 = perm[3];
            
            // 检查是否为有效时间
            if (h1 <= 2 && (h1 < 2 || h2 <= 3) && m1 <= 5) {
                string time = $"{h1}{h2}:{m1}{m2}";
                if (string.Compare(time, result) > 0) {
                    result = time;
                }
            }
        }
        
        return result;
    }
    
    private List<int[]> GetPermutations(int[] arr) {
        var result = new List<int[]>();
        GeneratePermutations(arr, 0, result);
        return result;
    }
    
    private void GeneratePermutations(int[] arr, int start, List<int[]> result) {
        if (start == arr.Length) {
            result.Add((int[])arr.Clone());
            return;
        }
        
        for (int i = start; i < arr.Length; i++) {
            Swap(arr, start, i);
            GeneratePermutations(arr, start + 1, result);
            Swap(arr, start, i);
        }
    }
    
    private void Swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

var largestTimeFromDigits = function(arr) {
    let maxTime = -1;
    
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            if (j === i) continue;
            for (let k = 0; k < 4; k++) {
                if (k === i || k === j) continue;
                for (let l = 0; l < 4; l++) {
                    if (l === i || l === j || l === k) continue;
                    
                    let h = arr[i] * 10 + arr[j];
                    let m = arr[k] * 10 + arr[l];
                    
                    if (h < 24 && m < 60) {
                        let time = h * 60 + m;
                        maxTime = Math.max(maxTime, time);
                    }
                }
            }
        }
    }
    
    if (maxTime === -1) return "";
    
    let h = Math.floor(maxTime / 60);
    let m = maxTime % 60;
    
    return (h < 10 ? "0" : "") + h + ":" + (m < 10 ? "0" : "") + m;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(1)因为数组长度固定为4，所以排列数量为4! = 24，为常数时间
空间复杂度O(1)只使用了常数个额外变量

相关题目