Algorithms to Compute the Largest Time for Given Digits

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

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

推荐阅读：
5 Simple Steps to Create Great Video Content for a Blog　 Best Practices for Blogging Securely　 5 Tips to Make Sure Your Blogs Works on Every Browser　 Learn from Business Entrepreneurs Who Take the Time to Train Oth　 The Story Of Aaron Swartz And How His Death Could Change Compute　 Smart Finance Tips for Bloggers　 8 Ways to Build Up Seed Money to Turn Your Blog into a Business　 Apple Reveals ARKit At WWDC　 Blogging From the Road: Japan Edition　 How to Redesign Your Blog for Improved User Experience　
评论列表
添加评论