Algorithms to Compute the Largest Time for Given Digits

  • 时间：2020-10-09 18:35:39
  • 分类：网络文摘
  • 阅读：104 次

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

Bruteforce Algorithm to Compute the Largest Time for Given Digits

Since there are only four digits, the easist algorithm would be to bruteforce with 3 loops – and calculate the fourth index by subtracting from 6 i.e. 0+1+2+3=6. Then we also need to check the validatity of each possible combination and find out the largest time which can be made.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        int ans = -1;  
        string time = "";
        for (int i = 0; i < 4; ++ i) {
            for (int j = 0; j < 4; ++ j) {
                if (i != j) {
                    for (int k = 0; k < 4; ++ k) {
                        if (k != i && k != j) {
                            int l = 6 - i - j - k;
                            int hours = 10 * A[i] + A[j];
                            int mins = 10 * A[k] + A[l];
                            if (hours < 24 && mins < 60) {
                                int curTime = hours * 60 + mins;
                                if (curTime > ans) {
                                    ans = curTime;
                                    time = std::to_string(A[i]) + 
                                           std::to_string(A[j]) + ":" +
                                           std::to_string(A[k]) + 
                                           std::to_string(A[l]);
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans >= 0 ? time : "";
    }
};
class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        int ans = -1;  
        string time = "";
        for (int i = 0; i < 4; ++ i) {
            for (int j = 0; j < 4; ++ j) {
                if (i != j) {
                    for (int k = 0; k < 4; ++ k) {
                        if (k != i && k != j) {
                            int l = 6 - i - j - k;
                            int hours = 10 * A[i] + A[j];
                            int mins = 10 * A[k] + A[l];
                            if (hours < 24 && mins < 60) {
                                int curTime = hours * 60 + mins;
                                if (curTime > ans) {
                                    ans = curTime;
                                    time = std::to_string(A[i]) + 
                                           std::to_string(A[j]) + ":" +
                                           std::to_string(A[k]) + 
                                           std::to_string(A[l]);
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans >= 0 ? time : "";
    }
};

The runtime complexity is O(1) constant as the constraints are already given and we only need to loop 64 times. The coding style isn’t great as too many code indent – but we may improve it slightly by inverting the if statement.

clock-3-30-150x150 Algorithms to Compute the Largest Time for Given Digits algorithms brute force c / c++

Clock 3:30

Enumerate Digits using next_permutation from C++ STL

There are a lot of nice routines from the STL::algorithms header. The next_permutation or prev_permutation is one of them. We can enumerate the digits easily thanks to the rich STL.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        sort(begin(A), end(A));
        string ans = getTime(A);        
        while (next_permutation(begin(A), end(A))) {
            auto time = getTime(A);
            if ((!time.empty()) && (time > ans)) {
                ans = time;
            }
        }
        return ans;
    }
private:
    string getTime(vector<int>& A) {
        int hour = A[0] * 10 + A[1];
        int minute = A[2] * 10 + A[3];
        if ((hour > 23) || (minute >= 60)) return "";        
        return std::to_string(A[0]) + 
            std::to_string(A[1]) + ":" + 
            std::to_string(A[2]) + 
            std::to_string(A[3]);
    }
};
class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        sort(begin(A), end(A));
        string ans = getTime(A);        
        while (next_permutation(begin(A), end(A))) {
            auto time = getTime(A);
            if ((!time.empty()) && (time > ans)) {
                ans = time;
            }
        }
        return ans;
    }
private:
    string getTime(vector<int>& A) {
        int hour = A[0] * 10 + A[1];
        int minute = A[2] * 10 + A[3];
        if ((hour > 23) || (minute >= 60)) return "";        
        return std::to_string(A[0]) + 
            std::to_string(A[1]) + ":" + 
            std::to_string(A[2]) + 
            std::to_string(A[3]);
    }
};

We can actually replace the if check in the while loop with the following:

1

ans = max(ans, time);
ans = max(ans, time);

In order to do a full permutation cycle – we have to sort the array. The complexity is also O(1) constant since the array size is fixed to four.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
Compute the Number of Ways to Paint the House via Dynamic Progra　 How to Paint The Houses using Minimal Costs via Dynamic Programm　 Relative Sort Array Algorithm: Sort Array Based on Predefined Se　 Classic Unlimited Knapsack Problem Variant: Coin Change via Dyna　 How to Remove Vowels from a String in C++?　 The Beginners’ Guide to Trie: How to Use the Trie in C++?　 5 Ways To Revamp Your 40 Hour Work Week　 Pros & Cons of Using a New TLD for Your Blog　 Facebook Apologizes After Deleting Blogger’s Post “By Accident”　 Want to Differentiate Your Content? Aim for Interaction　
评论列表
添加评论