题目描述
给定一个由 4 位数字组成的数组,返回可以设置的符合 24 小时制的最大时间。
24 小时格式为 “HH:MM” ,其中 HH 在 00 到 23 之间,MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00 ,而最大的是 23:59 。从 00:00 (午夜)开始算起,过得越久,时间越大。
以长度为 5 的字符串,按 “HH:MM” 格式返回答案。如果不能确定有效时间,则返回空字符串。
样例
输入:arr = [1,2,3,4]
输出:"23:41"
解释:有效的 24 小时制时间是 "12:34","12:43","13:24","13:42","14:23","14:32","21:34","21:43","23:14" 和 "23:41" 。这些时间中,"23:41" 是最大时间。
算法1
(暴力枚举) $O(4^3)$
暴力枚举所有的排列,用一个字符串来保存满足条件的最大时间,如果用来保存字符串未被改变,表示无解,输出空字符串。
时间复杂度
遍历数组三次 4 * 4 * 4
参考文献
C++ 代码
class Solution {
public:
bool check(string str)//检查是否满足条件
{
return str.substr(0, 2) < "24" && str.substr(2) < "60";
}
string largestTimeFromDigits(vector<int>& arr) {
string res = "0000";//初始化一个最小的数
bool changed = false;//判断是否无解
for(int i = 0; i < 4; i++)//i, j枚举小时数,其余数字为分钟数
for(int j = 0; j < 4; j++)
{
if(i != j)
{
string a = to_string(arr[i]) + to_string(arr[j]);
string c = to_string(arr[j]) + to_string(arr[i]);
string b;
for(int k = 0; k < 4; k++)
if(k != i && k != j)
b += to_string(arr[k]);
string d(b.rbegin(), b.rend());
if(check(a + b) && res <= a + b) res = a + b, changed = true;
if(check(a + d) && res <= a + d) res = a + d, changed = true;
if(check(c + b) && res <= c + b) res = c + b, changed = true;
if(check(c + d) && res <= c + d) res = c + d, changed = true;
}
}
if(!changed) return "";
return res.substr(0, 2) + ':' + res.substr(2);
}
};