https://leetcode.com/problems/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:
A.length == 4
0 <= A[i] <= 9
Try all possible times, and remember the largest one.
Algorithm (Java)
Iterate over all permutations
(i, j, k, l)
of (0, 1, 2, 3)
. For each permutation, we can try the time A[i]A[j] : A[k]A[l]
.
This is a valid time if and only if the number of hours
10*A[i] + A[j]
is less than 24
; and the number of minutes 10*A[k] + A[l]
is less than 60
.
We will output the largest valid time.
// Solution inspired by @rock class Solution { public String largestTimeFromDigits(int[] A) { int ans = -1; // Choose different indices i, j, k, l as a permutation of 0, 1, 2, 3 for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) if (j != i) for (int k = 0; k < 4; ++k) if (k != i && k != j) { int l = 6 - i - j - k; // For each permutation of A[i], read out the time and // record the largest legal time. int hours = 10 * A[i] + A[j]; int mins = 10 * A[k] + A[l]; if (hours < 24 && mins < 60) ans = Math.max(ans, hours * 60 + mins); } return ans >= 0 ? String.format("%02d:%02d", ans / 60, ans % 60) : ""; } }
The inner most loop at most iterates 4 * 4 * 4 = 64 times.
A[i], A[j], A[k], & A[l] are the 4 elements of A, where i, j, k & l are the permutation of 0, 1, 2, & 3. Therefore, since i + j + k + l = 0 + 1 + 2 + 3 = 6, we have l = 6 - i - j - k.
A[i], A[j], A[k], & A[l] are the 4 elements of A, where i, j, k & l are the permutation of 0, 1, 2, & 3. Therefore, since i + j + k + l = 0 + 1 + 2 + 3 = 6, we have l = 6 - i - j - k.
public String largestTimeFromDigits(int[] A) {
String ans = "";
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; // avoid duplicate among i, j & k.
String h = "" + A[i] + A[j], m = "" + A[k] + A[6 - i - j - k], t = h + ":" + m; // hour, minutes, & time.
if (h.compareTo("24") < 0 && m.compareTo("60") < 0 && ans.compareTo(t) < 0) ans = t; // hour < 24; minute < 60; update result.
}
}
}
return ans;
}
https://leetcode.com/problems/largest-time-for-given-digits/discuss/200823/Java-Iterative-15-linespublic String largestTimeFromDigits(int[] a) {
LinkedList<String> q = new LinkedList<>();
q.add("");
for (int n : a)
for (int size = q.size(); size > 0; size--) {
String s = q.poll();
for (int i = 0; i <= s.length(); i++)
q.add(s.substring(0, i) + n + s.substring(i));
}
String largest = "";
for (String s : q) {
s = s.substring(0, 2) + ":" + s.substring(2);
if (s.charAt(3) < '6' && s.compareTo("24:00") < 0 && s.compareTo(largest) > 0)
largest = s;
}
return largest;
}
https://leetcode.com/problems/largest-time-for-given-digits/discuss/235388/topic /**
* 4个数字全排列总共有24种可能,判断每一种可能是否能组成合法时间值,如果能,再和当前保存的最大值进行比较;
* 最大值是一个int值,用来表示分钟数;
*/
public String largestTimeFromDigits(int[] array) {
int largestTime = -1;
// 暴力枚举出每种可能
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (j != i) {
for (int k = 0; k < 4; k++) {
if (k != i && k != j) {
// 0,1,2,3 总和为6,故剩下的index为6-
int l = 6 - i - j - k;
int result = largestTimeHelper(array[i], array[j], array[k], array[l]);
largestTime = Math.max(result, largestTime);
}
}
}
}
}
if (largestTime==-1){
return "";
}
return String.format("%2d:%2d",largestTime/60,largestTime%60);
}
/**
* 判断输入的四个数字按照输入顺序组成的时间是否合法,如果合法,返回分钟数;
*/
public int largestTimeHelper(int a, int b, int c, int d) {
int hours = a * 10 + b;
int min = c * 10 + d;
if (hours < 24 && min < 60) {
// 返回分钟数
return hours * 60 + min;
}
return -1;
}
https://www.acwing.com/solution/LeetCode/content/680/
给定一个由 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
算法
(暴力枚举)
- 枚举所有可能的数字排列,然后判断哪些是合法的时间,最后输出最大的时间即可。
时间复杂度
- 枚举排列的时间复杂度,为 4!。