week3作业提交

Jewons · Jewons · commit 076bee47c92d · 2020-06-28T23:34:28.000+08:00
diff --git a/Week03/NOTE.md b/Week03/NOTE.md
@@ -1 +1,6 @@
-学习笔记
+学习笔记
+1.主要学习了递归，记住递归的模板。  1.terminator 2.process 3.drill down 4.reverse 
+2.回溯、分治也是，相当于递归的变种。
+3.对于回溯的了解还是有点不到位，需要反复复习及练习题去了解。
+4.分治其实还好，最初了解分治思想是通过归并排序（我认为是最好理解的排序算法之一）。
+5.还是需要熟练的使用递归。
diff --git a/Week03/lowest-common-ancestor-of-a-binary-tree.cpp b/Week03/lowest-common-ancestor-of-a-binary-tree.cpp
@@ -0,0 +1,34 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    TreeNode *answer;
+    //深度遍历
+    bool dfs(TreeNode* root,TreeNode* p,TreeNode* q){
+        //terminator
+        if(root == nullptr)
+            return false;
+        //process
+
+        //drill down
+        bool lson = dfs(root->left,p,q);
+        bool rson = dfs(root->right,p,q);
+        if((lson && rson) ||( (root->val == p->val || root->val == q->val) && (lson || rson)) )
+        {
+            answer = root;
+        }
+        return lson || rson || (p->val == root->val || q->val == root->val);
+    }
+
+    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
+        dfs(root,p,q);
+        return answer;
+    }
+};
diff --git a/Week03/permutations.cpp b/Week03/permutations.cpp
@@ -0,0 +1,24 @@
+class Solution {
+public:
+    void backtrack(std::vector<std::vector<int>>& result, std::vector<int>& output, int index, int len){
+        //terminator
+        if (index == len) {
+            result.push_back(output);
+            return;
+        }
+        //process
+        for (int i = index; i < len; ++i) {
+            swap(output[i], output[index]);
+            //drill down
+            backtrack(result, output, index + 1, len);
+            //reverse
+            swap(output[i], output[index]);
+        }
+    }
+    vector<vector<int>> permute(vector<int>& nums) {
+        std::vector<vector<int> > result;
+        int n = nums.size();
+        backtrack(result, nums, 0, n);
+        return result;
+    }
+};
