leetcode
leetcode 851 ~ 900
给定数字能组成的最大时间

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

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 16.0 MB


/*
 * 给定一个由 4 位数字组成的数组,返回可以设置的符合 24 小时制的最大时间。
 * 24 小时格式为 "HH:MM" ,其中 HH 在 00 到 23 之间,MM 在 00 到 59 之间。
 * 最小的 24 小时制时间是 00:00 ,而最大的是 23:59 。从 00:00 (午夜)开始算起,过得越久,时间越大。
 * 以长度为 5 的字符串,按 "HH:MM" 格式返回答案。如果不能确定有效时间,则返回空字符串。
 */
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String largestTimeFromDigits(int[] arr) {
        List<int[]> permutations = permute(arr);
        String maxTime = "";
        for (int[] perm : permutations) {
            String HH = "" + perm[0] + perm[1];
            String MM = "" + perm[2] + perm[3];
            if (HH.compareTo("24") < 0 && MM.compareTo("60") < 0) {
                String currentTime = HH + ":" + MM;
                if (maxTime.compareTo(currentTime) < 0) {
                    maxTime = currentTime;
                }
            }
        }
        return maxTime;
    }

    private List<int[]> permute(int[] arr) {
        return IntStream.range(0, arr.length)
            .boxed()
            .flatMap(i -> IntStream.range(0, arr.length)
                .filter(j -> j != i)
                .boxed()
                .flatMap(j -> IntStream.range(0, arr.length)
                    .filter(k -> k != i && k != j)
                    .boxed()
                    .flatMap(k -> IntStream.range(0, arr.length)
                        .filter(l -> l != i && l != j && l != k)
                        .mapToObj(l -> new int[] {arr[i], arr[j], arr[k], arr[l]}))))
            .collect(Collectors.toList());
    }
}

解释

方法:

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

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
如果输入数组中包含重复数字,这种情况下的排列结果会如何影响算法的性能和输出?
当输入数组中包含重复数字时,itertools.permutations会生成一些重复的时间组合。这不会改变算法找到最大时间的能力,但会降低算法的性能,因为它需要检查更多的(重复的)时间组合。尽管重复的组合对最终输出的结果没有影响,因为最大时间仍然会被正确地计算出来,但这些重复计算增加了不必要的计算量,导致效率下降。
🦆
在极端情况下(例如所有数字均大于5),此算法返回空字符串的处理是否有效?
是的,当所有数字均大于5时,不可能组成一个有效的时间,因为小时数的第一位最大为2,分钟数的第一位最大为5。算法会检查所有排列的小时数是否小于24,分钟数是否小于60,而所有数字均大于5的情况下生成的任何时间都不会满足这些条件。因此,这种情况下算法返回空字符串是正确的处理方式,有效地表示没有可能的有效时间可以被生成。

相关问题