Merge pull request algorithm004-01#373 from xuyusong37/master

melody-li · web-flow · commit 7e6fb199ef43 · 2019-10-28T12:03:33.000+08:00
651-Week02
diff --git a/Week 02/id_651/LeetCode_46_651.cpp b/Week 02/id_651/LeetCode_46_651.cpp
@@ -0,0 +1,54 @@
+/*
+给定一个没有重复数字的序列，返回其所有可能的全排列。
+
+示例:
+
+输入: [1,2,3]
+输出:
+[
+  [1,2,3],
+  [1,3,2],
+  [2,1,3],
+  [2,3,1],
+  [3,1,2],
+  [3,2,1]
+]
+*/    
+
+/*
+    解法： 递归,回溯, 
+    移动索引, 通过交换位置来去重
+*/
+# include <iostream>
+# include <vector>
+using namespace std;
+class Solution {
+private:
+    vector<vector<int>> answers;
+public:
+    vector<vector<int>> permute(vector<int>& nums) {
+        recursion(nums, 0);
+        return answers;
+    };
+    void recursion(vector<int> nums, int pos){
+        if (pos == nums.size()){
+            answers.push_back(nums);
+            return;
+        }
+        for(int j=pos;j<nums.size();j++){
+            if (pos != j) swap(nums[pos], nums[j]);
+            recursion(nums, pos + 1);
+            if (pos != j) swap(nums[pos], nums[j]);
+        }
+    }
+    
+};
+
+int main(){
+    Solution sol;
+    vector<int> n(4,0);
+    for(int i=0; i<n.size();i++) n[i] = i;
+    vector<vector<int>> answers;
+    answers = sol.permute(n);
+    return 0;
+}
diff --git a/Week 02/id_651/LeetCode_77_651.cpp b/Week 02/id_651/LeetCode_77_651.cpp
@@ -0,0 +1,97 @@
+/*
+给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
+输入: n = 4, k = 2
+输出:
+    [
+    [2,4],
+    [3,4],
+    [2,3],
+    [1,2],
+    [1,3],
+    [1,4],
+    ]
+*/
+
+/*  解法1： 回溯+剪枝 
+    -> 先生成对应数量的初始key-value对， 将生成的对象vector丢入递归函数中
+    -> 递归的跳出条件为： vector的大小等于k的时候。 将结果插入结果vector中
+    -> 遍历vector， 先将当前的vector存储一份（便于回溯）, 然后通过剪枝的方式，从中抽取掉迭代值位置的值
+    -> 每次递归完当前层的数据之后， 需要回复状态，进行下一层的循环
+
+    解法2： 维护栈
+    -> 初始化一个长度为k，每个值为0的vector， 初始化一个指针i=0
+    -> 指针在0和1位置移动
+    -> 每次循环
+        判断vector[i]的值是否大于长度n， 大于则左移
+        判断i的值是否等于k-1, 是则将结果插入到结果vector中
+        剩余的情况则需要继续增加值,将1位置的值持续的加1
+    -> eg:n=3,k=2
+        (1,1,0,0)
+        (1,2,0,0)
+        (1,3,0,0)->准备指针左移
+        (2,1,0,0)
+        (2,2,0,0)
+        (2,3,0,0)
+        (3,1,0,0)
+        (3,2,0,0)
+        (3,3,0,0)
+    一直到指针i的值小于0则跳出循环，返回结果
+*/   
+# include <iostream>
+# include <vector>
+using namespace std;
+
+class Solution {
+private:
+    vector<vector<int>> answers;
+public:
+    // 递归
+    vector<vector<int>> combine(int n, int k) {
+        vector<int> nums(n, {(1,n)});
+        for(int i=0; i<nums.size();i++){
+            nums[i] = i+1;
+        }
+        recursion(nums, k, 0);
+        return answers;
+    };
+    void recursion(vector<int> nums, int k, int pos){
+        if(nums.size() == k){answers.push_back(nums);return;};
+        for(int i=pos;i<nums.size();i++){
+            vector<int> temp(nums);
+            nums.erase(nums.begin() + i);
+            recursion(nums, k, i);
+            nums = temp;
+        }
+    }
+
+
+    // 利用栈
+    vector<vector<int>> combine2(int n, int k) {
+        vector<vector<int>> result;
+        int i = 0;
+        vector<int> temp(k, 0);
+        while(i >= 0){
+            temp[i]++;
+            if (temp[i] > n) --i;
+            else if (i == k-1) result.push_back(temp);
+            else{
+                ++i;
+                temp[i] = temp[i-1];
+            }
+        }
+        return result;
+    };
+};
+
+int main(){
+    Solution sol;
+    vector<vector<int>> result;
+    result = sol.combine(10, 2);
+    for(int i=0; i< result.size(); i++){
+        for(int j=0;j< result[i].size();j++){
+            cout << result[i][j] << " ";
+        }
+        cout << endl;
+    }
+    return 0;
+}
diff --git a/Week 02/id_651/NOTE.md b/Week 02/id_651/NOTE.md
@@ -1,4 +1,36 @@
 # NOTE
+Week 2 总结
 
-  
+1.  哈希表： 散列表， 时间复杂度为O(1), 找到一个key即可映射到对应的存储空间，获取到值
+    哈希函数： 通过函数的设计， 可以对key进行计算操作， 达到快速定位内存中key所对应的value
+    映射： 和内存空间地址差不多， 一个key对应一个或多个value。
+    集合： 有序的去重散列表， 内部会进行排序，去重。
 
+
+2.  树： 链表的一种变形， 有根节点，左节点，右节点
+    常见的数排序（主要是看根节点的位置判断是属于哪一种类型）
+    -> 前序排序 ： 根左右
+    -> 中序排序 ： 左根右  -> 二叉搜索树（有序的中序排序, 结果一定是按大小排好序的）
+    -> 后序排序 ： 左右根
+    图：在树的基础上，加上有环链表的一种变形
+
+3.  递归 : 自己调用自己， 本质上是维护一个栈， 将不需要先执行的推到栈底，需要先执行的推到栈顶。
+    递归函数的模板：
+        1. 结束条件 -> 即是准备开始弹出栈顶元素的时候
+        2. 当前层逻辑 -> 处理当前层的逻辑
+        3. 下一层的逻辑 -> 处理下一层的逻辑
+        4. 清理 -> 相关的有影响因子的变量需要重置或者其他操作
+        def recursion():
+            if () return 
+            deal_current_level()
+            deal_next_level()
+            clear_param()
+
+4.  分治 : 将任务拆分成多个小任务， 按照这个操作执行， 
+           到不能再分， 就可以开始将小任务处理掉，最后汇总到一起得出结果
+    回溯 ： 多层结构， 向下移动的，会保存当前层的状态， 等下一层的执行结果返回
+           若是不符合， 则当前层可以恢复原先的状态。
+
+
+总结：
+    捡回了一些大学的知识点，并且巩固加深了。 看了视频，做了题， 有些知识点就是那种感觉： 哦， 原来是这样/ 还能这么想。 尤其是树，递归，分支，回溯。 基本原理不是很难理解， 但是实际应用确实需要经验，需要培养起那种思维， 我觉得这两块地方的知识， 如果掌握了， 对我的技能提升是很大的。
