401. 二进制手表

问题401 二进制手表

https://leetcode-cn.com/problems/binary-watch/

这个题目我一开始的思路是回溯法，把题目要求抽象为从一个包含N个元素的数组中，挑选M个数出来，要求它们的和满足一定限制，返回所有可能的挑选对应的和的集合。然后吭哧吭哧写了一堆代码，正确性没有问题，但是效率较差。

看了一眼官方题解才恍然大悟，其实题目描述已经很明显的是二进制位运算问题，搞不懂为什么会先想到回溯……。从二进制位运算的思路入手，就是给定两个数值，一个小时和一个分钟，判断这俩数值包含的二进制1一共有多少位，如果符合目标值，那么就是时间结果集中的一个。

	public List<String> readBinaryWatch(int turnedOn) {
		List<String> list = new ArrayList<>();

		int[] binaryOneCnt = new int[64];
		for (int i = 0; i < 64; i++) {
			binaryOneCnt[i] = cntBinaryOne(i);
		}

		StringBuilder builder = new StringBuilder();

		for (int hour = 0; hour <= 11; hour++) {
			int hourBinaryOneCnt = binaryOneCnt[hour];
			for (int minute = 0; minute <= 59; minute++) {
				int minuteBinaryOneCnt = binaryOneCnt[minute];
				if (hourBinaryOneCnt + minuteBinaryOneCnt == turnedOn) {
					builder.setLength(0);
					builder.append(hour);
					builder.append(":");
					builder.append(minute < 10 ? "0" + minute : minute);
					list.add(builder.toString());
				}
			}
		}

		return list;
	}

	private int cntBinaryOne(int val) {
		int cnt = 0;
		while (val != 0) {
			cnt++;
			val &= (val - 1);
		}

		return cnt;
	}

在 LeetCode 查看