题目描述

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

最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。

以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。

样例

输入：[1,2,3,4]
输出："23:41"

输入：[5,5,5,5]
输出：""

注意

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

算法

(暴力枚举) $O(4!)$

1. 枚举所有可能的数字排列，然后判断哪些是合法的时间，最后输出最大的时间即可。

时间复杂度

• 枚举排列的时间复杂度，为 4!。

C++ 代码

class Solution {
public:

    bool check(int t) {
        int hh = t / 100, mm = t % 100;
        return 0 <= hh && hh < 24 && 0 <= mm && mm < 60;
    }

    string largestTimeFromDigits(vector<int>& A) {
        vector<int> p(4);
        p[0] = 0; p[1] = 1; p[2] = 2; p[3] = 3;

        int ans = -1;
        do {
            int cur = 0;
            for (int i = 0; i < 4; i++)
                cur = cur * 10 + A[p[i]];

            if (check(cur)) {
                if (cur > ans)
                    ans = cur;
            }
        } while (next_permutation(p.begin(), p.end()));

        if (ans == -1)
            return "";

        char anss[10];
        sprintf(anss, "%02d:%02d", ans / 100, ans % 100);

        return anss;
    }
};