week03 first commit

herost789 · herost789 · commit 32d44ac8b5c6 · 2020-06-27T22:30:14.000+08:00
diff --git a/Week03/NOTE.md b/Week03/NOTE.md
@@ -1 +1,38 @@
-学习笔记
+学习笔记
+###递归的实现，特性以及思维要点
+#####递归-循环，字节码上看是相似的
+	向下递归到不同的层，向上又回到原来一层
+	用参数来传递不同层之间的变量
+	经典递归，计算n！
+	递归代码模板
+	1. 递归终结条件 recursion terminator
+	public void recur(int level,int param){
+		if level > MAX_LEVEL
+		process_result
+		return;
+		}
+	2. 处理当前层逻辑 process logic in current level
+		process(level,param)
+	3. 下探到下一层 drill down 
+		recur(level+1,newParam)
+	4. 清理当前层
+	
+		// Java
+	public void recur(int level, int param) { 
+	  // terminator 
+	  if (level > MAX_LEVEL) { 
+		// process result 
+		return; 
+	  }
+	  // process current logic 
+	  process(level, param); 
+	  // drill down 
+	  recur( level: level + 1, newParam); 
+	  // restore current status 
+	 
+	}
+#####递归思维要点
+	1.不要进行人肉递归(最大误区)
+	2.找到最近最简方法，将其拆解成可重复解决的问题(重复子问题)
+	3.数学归纳法的思维
+#####分治回溯就是一种特殊的递归或者是较为复杂的递归
diff --git a/Week03/com/myhomework/LowestCommonAncestor.java b/Week03/com/myhomework/LowestCommonAncestor.java
@@ -0,0 +1,20 @@
+package com.myhomework;
+
+public class LowestCommonAncestor {
+    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+        if (root == null || root == p || root == q) return root;
+        TreeNode left = lowestCommonAncestor(root.left, p, q);
+        TreeNode right = lowestCommonAncestor(root.right, p, q);
+        //当left和right同时为空，说明左右子树都不包含p，q，返回null
+        if (left == null && right == null) return null;
+        //p,q其中一个在root的右子树中，此时right指向 p（假设为p）；
+        //p,q两节点都在root的右子树中，此时的right指向最近公共祖先节点 ；
+
+        if (left == null) return right;
+        if (right == null) return left;
+        //当左右子树都不为空，说明p, q分列在root的异侧（分别在左/右子树）
+        //因此root为最近公共祖先，返回root
+        return root;
+
+    }
+}
diff --git a/Week03/com/myhomework/Permute.java b/Week03/com/myhomework/Permute.java
@@ -0,0 +1,51 @@
+package com.myhomework;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class Permute {
+    public List<List<Integer>> permute(int[] nums) {
+        // 首先是特判
+        int len = nums.length;
+        // 使用一个动态数组保存所有可能的全排列
+        List<List<Integer>> res = new ArrayList<>();
+
+        if (len == 0) {
+            return res;
+        }
+
+        boolean[] used = new boolean[len];
+        List<Integer> path = new ArrayList<>();
+
+        dfs(nums, len, 0, path, used, res);
+        return res;
+    }
+    private void dfs(int[] nums, int len, int depth,
+                     List<Integer> path, boolean[] used,
+                     List<List<Integer>> res) {
+        if (depth == len) {
+            res.add(new ArrayList<>(path));
+            return;
+        }
+
+        for (int i = 0; i < len; i++) {
+            if (!used[i]) {
+                path.add(nums[i]);
+                used[i] = true;
+
+                dfs(nums, len, depth + 1, path, used, res);
+                // 注意：这里是状态重置，是从深层结点回到浅层结点的过程，代码在形式上和递归之前是对称的
+                used[i] = false;
+                path.remove(path.size() - 1);
+            }
+        }
+    }
+    public static void main(String[] args) {
+        int[] nums = {1, 2, 3};
+        Permute test = new Permute();
+        List<List<Integer>> lists = test.permute(nums);
+        System.out.println(lists);
+    }
+
+
+}
diff --git a/Week03/com/myhomework/TreeNode.java b/Week03/com/myhomework/TreeNode.java
@@ -0,0 +1,11 @@
+package com.myhomework;
+
+public class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+
+    TreeNode(int x) {
+        this.val=x;
+    }
+}
