p401

发表于 | 分类于 |

LeetCode p401 Binary Watch 题解

1.题目：

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”]

题意：

给一个如图所示的电子表，4个led灯表示小时，6个LAD灯表示时间。
输入一个数字，表示有几个灯亮了，输出所有可能表示的时间。

2.解题思路:

递归。。
注意是12小时制。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
public class Solution {
    public List<String> ans = new ArrayList<String>();
	public List<Integer> s;
	public int[] a = { 1, 2, 4, 8 };
	public int[] b = { 1, 2, 4, 8, 16, 32 };

	public List<String> readBinaryWatch(int num) {

		dpm(num, 0, 0);
		return ans;
	}

	public void dpm(int num, int sum, int k) {
		if (sum >= 12)
			return;
		if (k == 4 || num == 0) {
			int m = sum;
			s = new ArrayList<Integer>();
			if (num > 0)
				dps(num, 0, 0);
			else {
				s.add(0);
			}
			for (int n : s) {
				String s = n + "";
				if (n < 10)
					s = "0" + s;
				 //System.out.println(m + ":" + s+"   "+num);
				ans.add(m + ":" + s);
			}
			return;
		}

		dpm(num - 1, sum + a[k], k + 1);
		dpm(num, sum, k + 1);
	}

	public void dps(int num, int sum, int k) {
		if (sum >= 60)
			return;
		if (k == 6 || num == 0) {
			if (num == 0)
				s.add(sum);
			return;
		}

		dps(num - 1, sum + b[k], k + 1);
		dps(num, sum, k + 1);
	}
}

4.一些总结：