[LeetCode] 949. Largest Time for Given Digits

[grandyang]

Given an array of 4 digits, return the largest 24 hour time that can be made.

The smallest 24 hour time is 00:00, and the largest is 23:59.  Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5.  If no valid time can be made, return an empty string.

Example 1:

Input: [1,2,3,4]
Output: "23:41"

Example 2:

Input: [5,5,5,5]
Output: ""

Note:

1. A.length == 4
2. 0 <= A[i] <= 9

这道题给了我们四个数字，让组成 24 小时制能表示的最大时间，并且数字可以重复。注意并不是任意给四个数字都能组成时间，因为小时的第一个数字只能是 0，1，2 三个数字，并且若第一个数字是2，第二个数字只能是 0，1，2，3 这四个数。且分钟的第一个数字必须小于6，这些都是表示时间的一些规则，毕竟一天只有 24 个小时，一个小时只有 60 分钟。最简单暴力的方法就是遍历所有的排列情况，然后去验证当前顺序是否可以正确的表示 24 小时制的时间。想偷懒的话可以使用 STL 内置的 next_permutation 方法来快速返回下一个排列，但是注意要先给数组排个序，使数组变为升序的，不然若直接给个降序数组，该函数没法返回下一个排列。给数组排序还有个好处就是让小的数字到前面，因为表示小时的数字比较小。得到一个排列后，看组成小时的两个数字是否小于等于 23，且表示分钟的两个数字是否小于等于 59，若都满足的话，则更新结果 res 为当前的排列即可，参见代码如下：

解法一：

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        string res;
        sort(A.begin(), A.end());
        do {
            string hour = {char(A[0] + '0'), char(A[1] + '0')}, minute = {char(A[2] + '0'), char(A[3] + '0')};
            res = (hour <= "23" && minute <= "59") ? (hour + ":" + minute) : res;
        } while(next_permutation(A.begin(), A.end()));
        return res;
    }
};

你可能不屑于用 STL 内置函数来做，觉得简直是在耍赖，不能忍。那么下面就用一般的写法吧，反正只有四个数字，使用三个 for 循环就搞定了，分别用 i，j，k，6-i-j-k，来表示某个排列四个数字在原数组中的坐标，得到了排列顺序后，就可以分别组成小时和分钟的字符串表示了，但是需要注意的时候，由于此时是无序的，所以更新结果 res 的时候，要多加一个条件，当新的排序时间大于 res 时，才能更新，参见代码如下：

解法二：

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        string res;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                for (int k = 0; k < 4; ++k) {
                    if (i == j || i == k || j == k) continue;
                    string hour = {char(A[i] + '0'), char(A[j] + '0')}, minute = {char(A[k] + '0'), char(A[6 - i - j - k] + '0')}, t = hour + ":" + minute;
                    if (hour <= "23" && minute <= "59" && res < t) res = t;
                }
            }
        }
        return res;
    }
};

之前的方法都是各种捣鼓数组A，下面来看一种遍历所有时间组合的解法。因为小时只有 24 个数组，分钟只有 60 个数字，可以用两个 for 循环遍历所有的时间组合，然后反向去验证这四个数字是否和A中的数字相同，为了快速验证，使用一个数组来记录每个数字的出现次数。由于小时和分钟都是两位数，只能用除以 10 或者对 10 取余来分别取出十位和个位上的数字。这里可以进行一个小优化，因为小于 10 的话，十位上的数字就是0，可以省去除法操作。等统计好了数字后，遍历数组A，每次减去对应位置的数字，当次数变成负数的时候，说明A中没有足够的该数字，使用一个布尔型变量来标记当前排列不行，并 break 掉。若某个排列可以由A组成的话，就要开始拼接时间字符串，如果是 Java 的话，那就非常的简单方便了，直接用 String.format("%02d:%02d", h, m) 就可以了，但是 C++ 比较麻烦，还得手动判断并加首位0，这简直就是把人往 Java 阵营推啊，参见代码如下：

解法三：

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        for (int h = 23; h >= 0; --h) {
            for (int m = 59; m >= 0; --m) {
                vector<int> cnt(10);
                bool valid = true;
                ++cnt[h < 10 ? 0 : h / 10];
                ++cnt[h < 10 ? h : h % 10];
                ++cnt[m < 10 ? 0 : m / 10];
                ++cnt[m < 10 ? m : m % 10];
                for (int num : A) {
                    if (--cnt[num] < 0) {
                        valid = false;
                        break;
                    }
                }
                string hour = to_string(h), minute = to_string(m);
                if (valid) return (h < 10 ? "0" + hour : hour) + ":" + (m < 10 ? "0" + minute : minute);
            }
        }
        return "";
    }
};

Github 同步地址:

#949

参考资料：

https://leetcode.com/problems/largest-time-for-given-digits/submissions/

https://leetcode.com/problems/largest-time-for-given-digits/discuss/207126/Elegant-C%2B%2B-solution!)

https://leetcode.com/problems/largest-time-for-given-digits/discuss/202234/Java-Super-Short-Solution-!!!

https://leetcode.com/problems/largest-time-for-given-digits/discuss/200693/JavaPython-3-11-liner-O(64)-w-comment-6-ms.

LeetCode All in One 题目讲解汇总(持续更新中...)