LeetCode Binary Watch

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都要更新,否则生成的组合结果会有重复。

生成了小时和分钟的组合之后,我们再把小时和分钟字符串组合起来,这个就简单了,不再赘述。完整代码如下:

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;
	}
};

本代码提交AC,用时0MS。

Leave a Reply

Your email address will not be published. Required fields are marked *