{"id":403,"date":"2017-09-24T21:01:14","date_gmt":"2017-09-25T04:01:14","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=403"},"modified":"2018-08-30T13:53:41","modified_gmt":"2018-08-30T20:53:41","slug":"leetcode-681-next-closest-time","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-681-next-closest-time\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 681. Next Closest Time"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 681. Next Closest Time - \u5237\u9898\u627e\u5de5\u4f5c EP70\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/IAet94C1FCc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem:<\/strong><\/h1>\n<p><a href=\"https:\/\/leetcode.com\/problems\/next-closest-time\/description\/\">https:\/\/leetcode.com\/problems\/next-closest-time\/description\/<\/a><br \/>\nno limit on how many times a digit can be reused.<\/p>\n<p>You may assume the given input string is always valid. For example, &#8220;01:34&#8221;, &#8220;12:09&#8221; are all valid. &#8220;1:34&#8221;, &#8220;12:9&#8221; are all invalid.<\/p>\n<h2><b>Example 1:<\/b><\/h2>\n<pre class=\"crayon:false\">Input: \"19:34\"\r\nOutput: \"19:39\"\r\nExplanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, \r\nwhich occurs 5 minutes later.  \r\nIt is not 19:33, because this occurs 23 hours and 59 minutes later.\r\n<\/pre>\n<h2><b>Example 2:<\/b><\/h2>\n<pre class=\"crayon:false\">Input: \"23:59\"\r\nOutput: \"22:22\"\r\nExplanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. \r\nIt may be assumed that the returned time is next day's time since it is smaller \r\nthan the input time numerically.<\/pre>\n<p>Ads<br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><\/p>\n<h1><strong>Solution1:\u00a0Brute force<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 3 ms\r\nclass Solution {\r\npublic:\r\n    string nextClosestTime(string time) {\r\n        set&lt;char&gt; s(time.begin(), time.end());\r\n        int hour = stoi(time.substr(0, 2));\r\n        int min = stoi(time.substr(3, 2));\r\n        while (true) {\r\n            if (++min == 60) {\r\n                min = 0;\r\n                (++hour) %= 24;                \r\n            }\r\n            char buffer[5];\r\n            sprintf(buffer, \"%02d:%02d\", hour, min);\r\n            set&lt;char&gt; s2(buffer, buffer + sizeof(buffer));\r\n            if (includes(s.begin(), s.end(), s2.begin(), s2.end()))\r\n                return string(buffer);\r\n        }\r\n        return time;\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 85 ms\r\nclass Solution {\r\n    public String nextClosestTime(String time) {\r\n        int hour = Integer.parseInt(time.substring(0, 2));\r\n        int min = Integer.parseInt(time.substring(3, 5));\r\n        while (true) {            \r\n            if (++min == 60) {\r\n                min = 0;\r\n                ++hour;\r\n                hour %= 24;\r\n            }\r\n            String curr = String.format(\"%02d:%02d\", hour, min);\r\n            Boolean valid = true;\r\n            for (int i = 0; i &lt; curr.length(); ++i)\r\n                if (time.indexOf(curr.charAt(i)) &lt; 0) {\r\n                    valid = false;\r\n                    break;\r\n                }\r\n            if (valid) return curr;\r\n        }\r\n    }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 65 ms\r\n\"\"\"\r\nclass Solution:\r\n    def nextClosestTime(self, time):        \r\n        s = set(time)\r\n        hour = int(time[0:2])\r\n        minute = int(time[3:5])\r\n        while True:\r\n            minute += 1\r\n            if minute == 60:\r\n                minute = 0\r\n                hour = 0 if hour == 23 else hour + 1\r\n            \r\n            time = \"%02d:%02d\" % (hour, minute)\r\n            if set(time) &lt;= s:\r\n                return time\r\n        return time\r\n<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: DFS<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua \r\n\/\/ Running time: 3 ms\r\nclass Solution {\r\npublic:\r\n    string nextClosestTime(string time) {\r\n        vector&lt;int&gt; d = {\r\n            time[0] - '0', time[1] - '0', time[3] - '0', time[4] - '0' };\r\n        \r\n        int h = d[0] * 10 + d[1];\r\n        int m = d[2] * 10 + d[3];\r\n        vector&lt;int&gt; curr(4, 0);\r\n        int now = toTime(h, m);\r\n        int best = now;\r\n        \r\n        dfs(0, d, curr, now, best);\r\n        char buff[5];\r\n        sprintf(buff, \"%02d:%02d\", best \/ 60, best % 60);\r\n        return string(buff);\r\n    }\r\nprivate:\r\n    void dfs(int dep, const vector&lt;int&gt;&amp; digits, vector&lt;int&gt;&amp; curr, int time, int&amp; best) {\r\n        if (dep == 4) {\r\n            int curr_h = curr[0] * 10 + curr[1];\r\n            int curr_m = curr[2] * 10 + curr[3];\r\n            if (curr_h &gt; 23 || curr_m &gt; 59) return;\r\n            int curr_time = toTime(curr_h, curr_m);\r\n            if (timeDiff(time, curr_time) &lt; timeDiff(time, best))\r\n                best = curr_time;\r\n            return;\r\n        }            \r\n        \r\n        for (int digit : digits) {\r\n            curr[dep] = digit;\r\n            dfs(dep + 1, digits, curr, time, best);\r\n        }        \r\n    }\r\n    \r\n    int toTime(int h, int m) {\r\n        return h * 60 + m;\r\n    }\r\n    \r\n    int timeDiff(int t1, int t2) {\r\n        if (t1 == t2) return INT_MAX;\r\n        return ((t2 - t1) + 24 * 60) % (24 * 60);\r\n    }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 3: Brute force + Time library<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 292 ms\r\n\"\"\"\r\nfrom datetime import *\r\nclass Solution:\r\n    def nextClosestTime(self, time):        \r\n        s = set(time)        \r\n        while True:\r\n            time = (datetime.strptime(time, '%H:%M') + \r\n                    timedelta(minutes=1)).strftime('%H:%M')\r\n            if set(time) &lt;= s: \r\n                return time\r\n        return time\r\n<\/pre>\n<\/div><\/div>\n<h1>Related Problems:<\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-401-binary-watch\/\">\u82b1\u82b1\u9171 LeetCode 401. Binary Watch<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: https:\/\/leetcode.com\/problems\/next-closest-time\/description\/ no limit on how many times a digit can be reused. You may assume the given input string is always valid. For example,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[106,108,33,222,107],"class_list":["post-403","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-brute-force","tag-clock","tag-dfs","tag-easy","tag-time","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=403"}],"version-history":[{"count":16,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/403\/revisions"}],"predecessor-version":[{"id":3777,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/403\/revisions\/3777"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}