{"id":2154,"date":"2018-03-17T10:31:55","date_gmt":"2018-03-17T17:31:55","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2154"},"modified":"2018-03-17T12:29:03","modified_gmt":"2018-03-17T19:29:03","slug":"leetcode-401-binary-watch","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-401-binary-watch\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 401. Binary Watch"},"content":{"rendered":"

Problem:<\/h1>\n

A binary watch has 4 LEDs on the top which represent the\u00a0hours<\/b>\u00a0(0-11<\/b>), and the 6 LEDs on the bottom represent the\u00a0minutes<\/b>\u00a0(0-59<\/b>).<\/p>\n

Each LED represents a zero or one, with the least significant bit on the right.<\/p>\n

<\/h1>\n

For example, the above binary watch reads “3:25”.<\/p>\n

Given a non-negative integer\u00a0n<\/i>\u00a0which represents the number of LEDs that are currently on, return all possible times the watch could represent.<\/p>\n

Example:<\/b><\/p>\n

Input: n = 1\r\nReturn: [\"1:00\", \"2:00\", \"4:00\", \"8:00\", \"0:01\", \"0:02\", \"0:04\", \"0:08\", \"0:16\", \"0:32\"]<\/pre>\n
Note:<\/b><\/p>\n
    \n
  • The order of output does not matter.<\/li>\n
  • The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.<\/li>\n
  • The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.<\/li>\n<\/ul>\n
    Solution 1:<\/h1>\n
    Time complexity: O(11*59*n)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 2 ms (beats 100%)\r\nclass Solution {\r\npublic:\r\n  vector<string> readBinaryWatch(int num) {\r\n    vector<string> ans;\r\n    for (int i = 0; i <= num; ++i)\r\n      for (int h : nums(i, 12))\r\n        for (int m : nums(num - i, 60))\r\n          ans.push_back(to_string(h) + (m < 10 ? \":0\" : \":\") + to_string(m));\r\n    return ans;\r\n  }\r\nprivate:\r\n  \/\/ Return numbers in [0,r) that has b 1s in their binary format.\r\n  vector<int> nums(int b, int r) {    \r\n    vector<int> ans;\r\n    for (int n = 0; n < r; ++n)\r\n      if (__builtin_popcount(n) == b) ans.push_back(n);\r\n    return ans;\r\n  }  \r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem: A binary watch has 4 LEDs on the top which represent the\u00a0hours\u00a0(0-11), and the 6 LEDs on the bottom represent the\u00a0minutes\u00a0(0-59). Each LED represents…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[16,108,122,222],"class_list":["post-2154","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-clock","tag-combination","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2154","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=2154"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2154\/revisions"}],"predecessor-version":[{"id":2163,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2154\/revisions\/2163"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2154"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}