949. Largest Time for Given Digits

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation