Largest Time for Given Digits
More deceiving than it looks: https://leetcode.com/problems/largest-time-for-given-digits/description/
One way is to use backtracking, here is the gist of it:
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: ""
One way is to use backtracking, here is the gist of it:
- First sort the array in descending order. This will guarantee that the first solution found is the optimal
- Backtrack it
- For each index from 0..3, you'll need to use different rules based on the time structure. For example, for position 0, it is only allowed to have digits 2..0. And so on
- As you backtrack, if you find a solution return
- Given the small size of the input (4), even the exponential should do it (think about 4^4, or 2^8, that's 256....)
Code is down below, cheers, Marcelo.
public class Solution
{
public string LargestTimeFromDigits(int[] A)
{
Array.Sort(A);
int[] nums = new int[A.Length];
for (int i = 0; i < nums.Length; i++) nums[i] = A[A.Length - i - 1];
Hashtable used = new Hashtable();
string retVal = "";
if (LargestTimeFromDigits(nums, 0, used, "", ref retVal)) return retVal;
return "";
}
private bool LargestTimeFromDigits(int[] nums,
int currentIndex,
Hashtable used,
string current,
ref string retVal)
{
if (currentIndex >= nums.Length)
{
retVal = current;
return true;
}
switch (currentIndex)
{
case 0:
for (int i = 0; i < nums.Length; i++)
{
if (!used.ContainsKey(i) && nums[i] >= 0 && nums[i] <= 2)
{
used.Add(i, true);
if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString(), ref retVal)) return true;
used.Remove(i);
}
}
break;
case 1:
for (int i = 0; i < nums.Length; i++)
{
if (!used.ContainsKey(i))
{
if (current.StartsWith("2"))
{
if (nums[i] >= 0 && nums[i] <= 3)
{
used.Add(i, true);
if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString() + ":", ref retVal)) return true;
used.Remove(i);
}
}
else
{
used.Add(i, true);
if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString() + ":", ref retVal)) return true;
used.Remove(i);
}
}
}
break;
case 2:
for (int i = 0; i < nums.Length; i++)
{
if (!used.ContainsKey(i) && nums[i] >= 0 && nums[i] <= 5)
{
used.Add(i, true);
if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString(), ref retVal)) return true;
used.Remove(i);
}
}
break;
case 3:
for (int i = 0; i < nums.Length; i++)
{
if (!used.ContainsKey(i))
{
used.Add(i, true);
if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString(), ref retVal)) return true;
used.Remove(i);
}
}
break;
}
return false;
}
}
Comments
Wow, at moments like this I really appreciate Python having itertools module :)
Reply Deleteimport itertools
class Solution:
def largestTimeFromDigits(self, A):
return max(("%d%d:%d%d" % time for time in itertools.permutations(A) if time[:2] < (2, 4) and time[2] < 6), default="")
😮
Reply DeletePost a Comment
[フレーム]