BinaryWatchOPT2 [source code]
public class BinaryWatchOPT2 {
boolean DEBUG = false;
public List<String> readBinaryWatch(int num) {
List<String> res = new ArrayList<>();
int[] nums1 = new int[]{8, 4, 2, 1}, nums2 = new int[]{32, 16, 8, 4, 2, 1};
for (int i = 0; i <= num; i++) {
if (DEBUG) System.out.println("=======");
if (DEBUG) System.out.println("Finding: " + i + " for hour and " + (num - i) + " for mininute");
List<Integer> list1 = generateDigit(nums1, i);
if (DEBUG) System.out.println("=======");
List<Integer> list2 = generateDigit(nums2, num - i);
for (int num1 : list1) {
if (num1 >= 12) continue;
for (int num2 : list2) {
if (num2 >= 60) continue;
res.add(num1 + ":" + (num2 < 10 ? "0" + num2 : num2));
}
}
}
return res;
}
public List<Integer> generateDigit(int[] nums, int count) {
List<Integer> res = new ArrayList<>();
generateDigitHelper(nums, count, 0, 0, res);
return res;
}
private void generateDigitHelper(int[] nums, int count, int pos, int sum, List<Integer> res) {
if (DEBUG) System.out.println("count: " + count + ", pos: " + pos + ", sum: " + sum);
if (count == 0) {
if (DEBUG) System.out.println("adding: " + sum);
res.add(sum);
return;
}
for (int i = pos; i < nums.length; i++) {
generateDigitHelper(nums, count - 1, i + 1, sum + nums[i], res);
}
}
public static void main(String[] args) {
BinaryWatchOPT2 tester = new BinaryWatchOPT2();
for (String s : tester.readBinaryWatch(2)) System.out.println(s);
}
}
这个是一个很聪明的基于 DFS 的算法, 速度是3(75), 算是不错的了.
作者对于这个思路的描述是:
Backtracking and Idea of "Permutation and Combination"
这种用 DFS 干这个事情的真的我还是第一次见到, 核心函数就是这个 helper. 有点看不懂. 首先 nums 和 res 这个是很正常的, 两个都是为了提供 access 而已一直往下传的, 有点类似 ocaml 里面做的东西.
以前学 ocaml 或者 prolog 的时候,理解 recursion 的时候常常提醒自己, 关键就在于体会how the arguments change. 其实除此以外, 当在 JAVA 的环境里面的时候, 还有其他的含义, 因为 JAVA 不像那几个语言, argument 传进来以后具体怎么用的, 也就是how the arguments are used, 你也要看一下;
比如这里, count 就很简单, 只出现在下一个 level 的 recursive call 的参数里面, 可以理解为控制搜索深度的, 也可以理解为一个 tree 里面的深度的对应;
pos 比较复杂, 在 recursive call 的参数表里面出现了, 但是并不是一个简单的更新. 再看看 usage, 可以看到 pos 被用在了循环的header 里面, 控制循环的 range. 所以按照 DFS 的角度, 就是控制当前 node 的branching factor, 分叉数.
严格来说, pos 本身并不是branching factor, 而是 nums.length - pos + 1才是branching factor; pos 标记的不是(从0开始的)终点, 而是一个起点;
如果自己画出来一个 tree(比如4选2, 那么root 是(2,0,0)), 那么最后可以看到真正 add 就是发生在 leaf 的位置, 也就是 count 达到0的位置. 这个算法难以理解的地方在于怎么就自动把这个 tree 跟这个搜索过程对应起来.
首先, 一个 tree 肯定有一个深度的概念, 这里这个问题上面这个深度是 explicit 给表示出来的, 当然有些问题不是这么明显, 比如用G.adj(v)这样的表示, 也有. 但是核心的作用都是一样的, 就是让 search 可以继续向下进行. 这里的 count 就是完成了这个角色;
深度的概念有了之后, 要想好怎么定义 branching 的概念. 这里的 branching 的概念就是用 pos 来完成的. 在具体问题的 context 上来说, 这里的这个 pos 代表的是: the index from which we start to find the $count elements. 这个定义其实对应的, 比如说, 我们先是有(2,0,0), 然后我们这个 root 的下一层有三个: (1,1,8), (1,2,4), (1,3,2). 这三个其实对应的就是: the choice of index for the first of the 2 elements, from left to right. 那么pos自然就是从左往右的下一个的位置, 我们对这个进行 branch. 注意的是, 假如我们选择(1,3,2)的时候, 意思就是第二个 element 从[3]开始选. 注意到一个问题没有? 这里暗示的是[0..2]之间只选择了一个, 也就是第一个 element. 但是这个 element 具体是什么? 这个你光是看pos 是看不出来的. 这里的 sum 就是起的这个作用, 保存the actual element that gets chosen at this level. 其实这个可以用一个int[], 也就是一个array of index来完成, 一直往下传(这样到最下面的时候可以直接一下返回上去). 但是我们这个题目的目的很明确, 就是求一个求和, 所以干脆在得到这个index of first element chosen at this level的时候, 就直接加到sum buffer里面就行了.
这样两个概念(depth & branching)定义出来之后, 这个 tree 的结构就很清晰了. 然后你走 tree 肯定自然的是用的DFS 这个order, 你要考虑的就是针对你的题目, 你要在这个 order 过程中做什么. 因为这个问题深度代表 count, 所以我们要做的事情也很明确, 就是在最大深度, 也就是 leaf 的时候返回结果就行了(实际情况是用一个 side effect 来完成的).
总体来说这个算法吧, 你要说看不懂, 也不至于, 就是没想到 DFS 也能这么用过.
结合这个问题, 你认为这里 backtracking 这个元素是怎么体现出来的?
backtrack 这个动作其实就是依赖 DFS 本身的自然属性完成的. 当然, 为了让 DFS 能够有能力完成这个 backtrack 的过程, 你要保存足够的信息, 比如这里的depth & branching这些东西, branching 就对应的是我们425的时候学的decision variable的概念. 这里我们每一个 node 都知道自己的 pos, 意思就是我们know every decision we made. 所以后面 backtrack 就好做了.
总体来说backtracking 这种 search 我还是太陌生了, 我看了一下, 还有那种要求把8queens 所有的答案都打印出来的题目, 我现在这个水平是完全无法理解的.
尝试用combinatorics iterator的角度重新理解一下这个算法. 刚开始想写这样一个 iterator 的时候写不出来, 因为想的很简单: each iterator corresponds to each chosen element's index. 这个做法当时的问题就是你提前不知道有几个elements to be chosen, 你就不知道你具体需要多少个 iterator, 你代码就不知道写几个循环.
这里这个 DFS 的优势在于用一个类似 DP 的概念, 如果非要说iterate on的话, 就是on the count and on the first element chosen.
另外, 还是要提醒一下这里 pos 和 sum 之间的关系: 为什么这两个其中如果只有一个, 就不够呢? 如果只有 pos, 你不知道 pos 左边的这个first element你具体选的是谁. 作为 DFS 的角度, 纯粹为了 traversal 这个是没有问题的, 但是你如果有一个具体的问题, 你就没有任何可以用来解题的信息. 如果你只有 sum, 你只知道the first element chosen. 好像也是可以的? 看了一下, (1,1,8), (1,2,4), (1,3,2), 这三个, 其实the first element chosen都是严格在 pos 的左边紧邻的那一个. 那么如果这样理解, sum 其实就是一个用来当path wise buffer的意思? 好像是这样.
pos - 1记录the index of the element chosen at this level(the first element), 然后从 pos 开始找下面count - 1个 element. sum 就是用来保存当前 path 信息的一个 buffer.
看了一下 discussion 其他的类似的recursion 的解, 基本都没有这个写的清晰干净. 这个算法的功能分离做的比较好, recursion 就是单纯的做一个number value的功能. 其他的有些算法, 把, 比如判断时间 validity (hour < 12, minute < 60), 或者String format, 包括0padding 这些全都加到recursion 里面, 就显得很臃肿.
Problem Description
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".
Difficulty:Easy
Category:Algorithms
Acceptance:44.81%
Contributor: LeetCode
Companies
google
Related Topics
backtracking bit manipulation
Similar Questions
Letter Combinations of a Phone Number Number of 1 Bits