Algorithms to Compute the Largest Time for Given Digits

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

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) —

推荐阅读：
How to Remove Duplicate Elements from Vector in C++ using std::u　 Javascript’s HashSet Implementation using Hash Map　 Using the OpenSSL command to Test the SSL Certificate　 Algorithm to Shuffle String in Python3 According to Index　 Depth First Search Algorithm to Find the Strobogrammatic Number 　 Depth First Search Algorithm to Compute the Diameter of N-Ary Tr　 Remove the Temporary Files (including Windows.old) on Windows 10　 Simulation Algorithm to Compute the Number of Water Bottles　 Using CloudFlare Worker Serverless Technology to Deploy a Load B　 Algorithms to Compute the Math Power(a, n) in logarithm Complexi　
评论列表
添加评论