提交

邵联飞 · 邵联飞 · commit 94aa964a44d1 · 2020-06-27T21:08:53.000+08:00
diff --git a/Week03/NOTE.md b/Week03/NOTE.md
@@ -1 +1,11 @@
-学习笔记
+第三周学习笔记
+本周学习了递归，学会了递归模板：
+1. recursion  terminator(递归终止条件)
+2. process logic in current level （处理当前逻辑层）
+3. drill down （下探到下一层）
+4. reverse the current level status if needed (清理当前层)
+
+学习了分治思想及回溯
+
+
+
diff --git a/Week03/first.java b/Week03/first.java
@@ -0,0 +1,32 @@
+
+//题目：组合
+//回溯法
+
+class Solution {
+    List<List<Integer>> output = new LinkedList();
+    int n;
+    int k;
+
+    public void backtrack(int first, LinkedList<Integer> curr) {
+        // if the combination is done
+        if (curr.size() == k)
+            output.add(new LinkedList(curr));
+
+        for (int i = first; i < n + 1; ++i) {
+            // add i into the current combination
+            curr.add(i);
+            // use next integers to complete the combination
+            backtrack(i + 1, curr);
+            // backtrack
+            curr.removeLast();
+        }
+    }
+
+    public List<List<Integer>> combine(int n, int k) {
+        this.n = n;
+        this.k = k;
+        backtrack(1, new LinkedList<Integer>());
+        return output;
+    }
+}
+
diff --git a/Week03/second.java b/Week03/second.java
@@ -0,0 +1,36 @@
+
+//题目： 全排列
+
+
+//回溯
+
+class Solution {
+    public void backtrack(int n,
+                          ArrayList<Integer> output,
+                          List<List<Integer>> res,
+                          int first) {
+        // 所有数都填完了
+        if (first == n)
+            res.add(new ArrayList<Integer>(output));
+        for (int i = first; i < n; i++) {
+            // 动态维护数组
+            Collections.swap(output, first, i);
+            // 继续递归填下一个数
+            backtrack(n, output, res, first + 1);
+            // 撤销操作
+            Collections.swap(output, first, i);
+        }
+    }
+
+    public List<List<Integer>> permute(int[] nums) {
+        List<List<Integer>> res = new LinkedList();
+
+        ArrayList<Integer> output = new ArrayList<Integer>();
+        for (int num : nums)
+            output.add(num);
+
+        int n = nums.length;
+        backtrack(n, output, res, 0);
+        return res;
+    }
+}
