LeetCode Binary Watch
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
For example, the above binary watch reads “3:25”.
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Input: n = 1 Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]Note:
- The order of output does not matter.
- The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
- 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”.
程序员有一个二进制的手表，如图所示，上面4个灯表示小时，下面6个灯表示分钟。现在告诉你手表上亮着n盏灯，问共有多少种时间的可能，要求输出所有可能的时间。 我觉得这应该算中等题，稍微有一点麻烦。 首先我们要把亮着的n盏灯分到小时和分钟上，比如小时亮x盏灯，分钟亮y盏灯，x+y=n。对于小时，长度为4bit，要把亮着的x盏灯填入这4bit中，共有$$C_4^x$$种填法，可以用递归的思路实现。对于分钟，长度为6bit，要把亮着的y盏灯填入这6bit中，共有$$C_6^y$$种填法，也可以用递归的思路实现。 所以我们可以统一小时和分钟的递归算法，具体看代码comb函数。假设初始的灯的状态为cur，我们就是要在cur的[s,t) bit之间填入ones个1bit，对于小时，长度为4bit，所以传入cur=0, s=0, t=4；对于分钟，长度为6bit，所以传入cur=0, s=0, t=6。注意每次递归调用的时候，s都要更新，否则生成的组合结果会有重复。 生成了小时和分钟的组合之后，我们再把小时和分钟字符串组合起来，这个就简单了，不再赘述。完整代码如下： [cpp] class Solution { public: // cur为传入的二进制串，comb要把ones个1填入[s,t)中 void comb(vector<int>& res, int cur, int s, int t, int ones) { if (ones == 0)res.push_back(cur); else { for (int i = s; i < t; ++i) { if ((cur&(1 << i)) == 0) { comb(res, cur | (1 << i), i + 1, t, ones – 1); // 递归把ones-1个1填入[i+1,t)中 } } } } vector<string> readBinaryWatch(int num) { vector<string> ans; for (int hour = 0; hour <= 3; ++hour) { if (hour > num)break; vector<int> hours; comb(hours, 0, 0, 4, hour); vector<int> minutes; comb(minutes, 0, 0, 6, num – hour); for (int i = 0; i < hours.size(); ++i) { if (hours[i] > 11)continue; string tmp_h = to_string(hours[i]); for (int j = 0; j < minutes.size(); ++j) { if (minutes[j] > 59)continue; string tmp_m = to_string(minutes[j]); if (tmp_m.size() < 2)tmp_m = "0" + tmp_m; ans.push_back(tmp_h + ":" + tmp_m); } } } return ans; } }; [/cpp] 本代码提交AC，用时0MS。]]>