Bruteforce Algorithm to Find the Next Closet Time Reusing the Cu

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

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

推荐阅读:
免费的午餐  肇事汽车的牌号  报数的阴谋  互相拍卖得汽车  苹果和筐子平均分配  角谷猜想是怎么回事  斐波那契问题  用字母表示数要注意哪些问题?  到哪个商店购买省钱?  数学中的比与比赛计分牌上的比有什么不同? 
评论列表
添加评论