Bruteforce Algorithm to Find the Next Closet Time Reusing the Cu

  • 时间:2020-09-20 13:49:13
  • 分类:网络文摘
  • 阅读:97 次

Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused. You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:
Input: “19:34”
Output: “19:39”
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:
Input: “23:59”
Output: “22:22”
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day’s time since it is smaller than the input time numerically.

How to Find the Next Closet Time Reusing the Current Digits?

The first step is to parse the given time string and this should allow us extracting the four digit values. Starting from the current time, we can increment the time at each step one minute forward, and check if all digits are re-used.

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
class Solution {
public:
    string nextClosestTime(string time) {
        int h1 = time[0] - '0';
        int h2 = time[1] - '0';
        int m1 = time[3] - '0';
        int m2 = time[4] - '0';
        int h = h1 * 10 + h2;
        int m = m1 * 10 + m2;
        unordered_set<int> digits({h1, h2, m1, m2});
        for (;;) {
            m ++;
            if (m == 60) {
                m = 0;
                h = (h + 1) % 24;
            }            
            if ((digits.count(m % 10)) && 
                (digits.count(h % 10)) && 
                (digits.count(m / 10)) && 
                (digits.count(h / 10))) {
                return std::to_string(h/10) + 
                    std::to_string(h%10) + ":" +
                    std::to_string(m/10) + 
                    std::to_string(m%10);
            }
        }        
        return ""; // make compiler happy
    }
};
class Solution {
public:
    string nextClosestTime(string time) {
        int h1 = time[0] - '0';
        int h2 = time[1] - '0';
        int m1 = time[3] - '0';
        int m2 = time[4] - '0';
        int h = h1 * 10 + h2;
        int m = m1 * 10 + m2;
        unordered_set<int> digits({h1, h2, m1, m2});
        for (;;) {
            m ++;
            if (m == 60) {
                m = 0;
                h = (h + 1) % 24;
            }            
            if ((digits.count(m % 10)) && 
                (digits.count(h % 10)) && 
                (digits.count(m / 10)) && 
                (digits.count(h / 10))) {
                return std::to_string(h/10) + 
                    std::to_string(h%10) + ":" +
                    std::to_string(m/10) + 
                    std::to_string(m%10);
            }
        }        
        return ""; // make compiler happy
    }
};

when minute goes to 60, we should wrap it to zero and increment the hour – and when hour goes to 24, we should rewind it to zero. The complexity for this particular bruteforce algorithm is O(1) as we will at most iterate 24*60 and the time complexity is O(1) as well, as we use a set to store at most 4 values.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
2020 Design Trends [Infographic]  8 Content Marketing Plugins You Need For Your WordPress Blog  Tips to Make Money from the Comfort of Your Own Home  5 Tips for Protecting Your Freelance Business from Liabilities  5 Easy Ways On How To Build An Authority Website  How to Protect Your WordPress Site From Hackers  Top 10 Relationship Blogs With the Best Pieces of Advice in 2020  How to Construct Binary Search Tree from Preorder Traversal in P  Dynamic Programming Algorithm to Compute the Block Sum in a Matr  Smallest Multiple Algorithm using Bruteforce or GCD/LCM 
评论列表
添加评论