Largest Time for Given Digits (E)
題目
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 == 40 <= A[i] <= 9
題意
用給定的4個數字組成最大的24時制的時間，
思路
可以直接回溯法解決，每一位上都有一個值的范圍，從最大值往前遍歷尋找可能的組合，
或者直接對小時23-0和對分鐘59-0進行二重回圈遍歷，
代碼實作
Java
回溯法
class Solution {
public String largestTimeFromDigits(int[] A) {
int[] digits = new int[10];
for (int num : A) {
digits[num]++;
}
return generate(digits, 0, "");
}
private String generate(int[] digits, int index, String s) {
if (index == 5) {
return s;
}
if (index == 2) {
return generate(digits, index + 1, s + ":");
}
int max = index == 0 ? 2 : index == 1 ? (s.charAt(0) == '2' ? 3 : 9) : index == 3 ? 5 : 9;
for (int i = max; i >= 0; i--) {
if (digits[i] > 0) {
digits[i]--;
String t = generate(digits, index + 1, s + i);
if (!t.isEmpty()) {
return t;
} else {
digits[i]++;
}
}
}
return "";
}
}
二重回圈
class Solution {
public String largestTimeFromDigits(int[] A) {
Arrays.sort(A);
for (int i = 23; i >= 0; i--) {
for (int j = 59; j >= 0; j--) {
int a = i < 10 ? 0 : i / 10;
int b = i % 10;
int c = j < 10 ? 0 : j / 10;
int d = j % 10;
int[] B = { a, b, c, d };
Arrays.sort(B);
boolean valid = true;
for (int k = 0; k < 4; k++) {
if (A[k] != B[k]) {
valid = false;
break;
}
}
if (valid) {
return "" + a + b + ":" + c + d;
}
}
}
return "";
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144294.html
標籤：其他
上一篇：D. New Year Santa Network 決議(思維、DFS、組合、樹狀DP)
下一篇：完全二叉樹與滿二叉樹的區別