Algorithms to Compute the Largest Time for Given Digits

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

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

推荐阅读：
Algorithms to Determine a Palindrome Number　 Algorithm to Compute the Fraction to Recurring Decimal of the Tw　 Algorithms to Check if Array Contains Duplicate Elements　 Recursive Depth First Search Algorithm to Compute the Sum of Nod　 How to Convert Integer to the Sum of Two No-Zero Integers?　 Algorithm to Generate the Spiral Matrix in Clock-wise Order　 How to Remove the Duplicates from Sorted List (Leaving Only Dist　 How to Sort a Linked List by Converting to Array/Vector?　 Know The Effective and Smart SEO Reporting Tool You Must Use　 Pro Content Marketing Tips You Can Implement NOW　
评论列表
添加评论