Algorithms to Compute the Largest Time for Given Digits

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

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

推荐阅读:
6 Remote Jobs For Supplemental Income  5 Tips When Preparing for a Business Conference  Customizing WordPress with Branda by WPMU DEV  How to Blog Like Shakespeare  Depth First Search Algorithm to Delete Insufficient Nodes in Roo  C/C++ Program to Compute the Angle Between Hands of a Clock  What Should Your Anti Virus Software Have in Order to Be Effecti  The Importance of SEO and How They Improve the Number of Your Cl  Learn The Basics Of Google My Business  Iterative and Recursion Algorithms to Compute the Number of Step 
评论列表
添加评论