Leetcode 401 - Binary Watch（Bit）

题意

有一个二进制手表，其中小时和分钟都是二进制表示的。 现在给一个数n，代表二进制表示中为1的那些位的总位数，求有哪些可表示的时间。

思路

二进制枚举状态或者枚举时间。

算法1

先枚举小时对应的二进制为1的位数i，那么分钟对应的二进制为1的位数就为n - i。 因为小时最大到12（ 24 ），分钟最大到60（ 26 ）。 所以我们对于小时从0开始枚举到16，分钟从0枚举到64，找到满足条件位数并且满足时间上限的那些时间拼接起来就好。

算法2

上面的算法实在不优雅，我们直接枚举小时和分钟就好了。 从0到11开始枚举小时，0到59开始枚举分钟，然后数一下它们加起来1的位数就好。

代码

algorithm 1

class Solution { public: vector<int> calculate(int n, int status) { vector<int> ans; for (int s = 0; s < (1 << (status ? 6 : 4)); s++) { if (__builtin_popcount(s) != n) continue; int time = 0; for (int i = 0; i < (status ? 6 : 4); i++) { if (s & (1 << i)) time += (1 << i); } if (status) { if (time < 60) ans.push_back(time); } else { if (time < 12) ans.push_back(time); } } return ans; } vector<string> readBinaryWatch(int num) { vector<string> ans; for (int i = 0; i <= num; i++) { vector<int> hour = calculate(i, 0); vector<int> minute = calculate(num - i, 1); for (auto x : hour) { for (auto y : minute) { string s = to_string(x); s.push_back(':'); if (y < 10) s.push_back('0'); s = s + to_string(y); ans.push_back(s); } } } return ans; } };

algorithm 2

class Solution { public: vector<string> readBinaryWatch(int num) { vector<string> ans; for (int i = 0; i < 12; i++) { for (int j = 0; j < 60; j++) { if (__builtin_popcount(i) + __builtin_popcount(j) == num) { ans.push_back(to_string(i) + ":" + ((j < 10) ? "0" : "") + to_string(j)); } } } return ans; } };