本文主要是介绍949. Largest Time for Given Digits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
949. 给定数字能组成的最大时间
给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。
最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。
以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。
示例 1：
输入：[1,2,3,4] 输出："23:41"示例 2：
输入：[5,5,5,5] 输出：""
提示：
A.length == 40 <= A[i] <= 9
解法一
//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:bool match(int hour, int minute, vector<int>& A) {vector<int> B = {hour / 10, hour % 10, minute / 10, minute % 10};sort(B.begin(), B.end());return B == A;}string largestTimeFromDigits(vector<int>& A) {sort(A.begin(), A.end());int hour = 23, minute = 59;while(hour >= 0) {if(match(hour, minute, A))return to_string(hour / 10) + to_string(hour % 10) + ':' +to_string(minute / 10) + to_string(minute % 10);if(minute-- < 0) {minute = 59;hour--;}}return "";}
};解法二
//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:bool check(vector<int>& A) {if(A[0] > 2 ||A[0] == 2 && A[1] > 3 ||A[2] > 5) return false;return true;}string largestTimeFromDigits(vector<int>& A) {int hour = -1, minute = -1;sort(A.begin(), A.end());do {if(!check(A)) continue;int hour1 = A[0] * 10 + A[1];int minute1 = A[2] * 10 + A[3];if(hour < hour1 || hour == hour1 && minute < minute1) {hour = hour1;minute = minute1;}} while(next_permutation(A.begin(), A.end()));return hour == -1 ? "" : to_string(hour / 10) + to_string(hour % 10) + ':' +to_string(minute / 10) + to_string(minute % 10);}
};思路：
解法一（略低效）
穷举法，对所有合法的时间进行遍历，尝试匹配给定数组A。从23:59开始向下遍历，直到找到第一个与A包含元素一样的时间，若到00:00没有找到，就返回空串。
解法二
不对所有时间遍历，而是对给定数组A求全排列，对于每一个排列，先check其合法性，若合法且时间大于hour:minute，就更新hour:minute，最后返回hour:minute的字符串形式。
这里全排列使用了标准库的next_permutation()，也可以自已实现全排列算法，代码稍长，待日后整理一下。
2019/08/18 00:42
这篇关于949. Largest Time for Given Digits的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
