Week2 homework in Algorithm Class 10

MrFreezing · MrFreezing · commit 08c4f3245a28 · 2020-06-21T23:46:19.000+08:00
diff --git a/Week02/LeetCodes/144_Binary_Tree_Preorder_Traversal.cpp b/Week02/LeetCodes/144_Binary_Tree_Preorder_Traversal.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+    vector<int> preorderTraversal(TreeNode* root) {
+        vector<int> res;
+        if (!root) return res;
+
+        stack<TreeNode*> s;
+        s.push(root);
+        while(s.size()) {
+            TreeNode * p = s.top();
+            s.pop();
+            if (p) res.push_back(p->val);
+            if(p->right) s.push(p->right);
+            if(p->left) s.push(p->left);
+        }
+
+        return res;
+    }
+};
diff --git a/Week02/LeetCodes/347_Top_K_Frequent_Elements.cpp b/Week02/LeetCodes/347_Top_K_Frequent_Elements.cpp
@@ -0,0 +1,44 @@
+class Solution {
+public:
+    vector<int> topKFrequent(vector<int>& nums, int k) {
+        unordered_map<int, int> frep;
+        for (int i : nums) frep[i]++;
+
+        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second;};
+        priority_queue<pair<int, int> , vector<pair<int, int>>, decltype(cmp)> pq(cmp);
+
+        for (auto f : frep) {
+            pq.push(f);
+            if (pq.size() > k) pq.pop();
+        }
+        
+        vector<int> res;
+        for (int i = 0; i < k; i++) {
+            res.push_back(pq.top().first);
+            pq.pop();
+        }
+
+        return res;
+    }
+
+    // vector<int> topKFrequent(vector<int>& nums, int k) {
+    //     unordered_map<int, int> frep;
+    //     for (int i : nums) frep[i]++;
+
+    //     //超长buckets
+    //     vector<vector<int>> buckets(nums.size() + 1);
+
+    //     for (auto f : frep) 
+    //         buckets.at(f.second).push_back(f.first);
+        
+    //     vector<int> res;
+    //     for (int i = buckets.size() - 1; i >= 0; i--) {
+    //         for (auto bucket : buckets[i]) {
+    //             res.push_back(bucket);
+    //             if (res.size() == k) return res;
+    //         }
+    //     }
+        
+    //     return res;
+    // }
+};
diff --git a/Week02/LeetCodes/429_N-ary_Tree_Level_Order_Traversal.cpp b/Week02/LeetCodes/429_N-ary_Tree_Level_Order_Traversal.cpp
@@ -0,0 +1,48 @@
+/*
+// Definition for a Node.
+class Node {
+public:
+    int val;
+    vector<Node*> children;
+
+    Node() {}
+
+    Node(int _val) {
+        val = _val;
+    }
+
+    Node(int _val, vector<Node*> _children) {
+        val = _val;
+        children = _children;
+    }
+};
+*/
+
+class Solution {
+public:
+    vector<vector<int>> levelOrder(Node* root) {
+        if (!root) return {};
+
+        vector<vector<int>> res;
+        queue<Node*> q;
+        q.push(root);
+        q.push(NULL);
+        vector<int> line;
+
+        while(q.size()) {
+            Node * p = q.front();
+            q.pop();
+
+            if (p) {
+                line.push_back(p->val);
+                for (auto cl : p->children) 
+                    if (cl) q.push(cl);
+            } else {
+                res.push_back(line);
+                line.clear();
+                if (q.size()) q.push(NULL);
+            }
+        }
+        return res;
+    }
+};
diff --git a/Week02/LeetCodes/49.UglyNum.cpp b/Week02/LeetCodes/49.UglyNum.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+    int nthUglyNumber(int n) {
+        vector<int> ug(n, 1);
+
+        int c2 = 2, c3 = 3, c5 = 5;
+        int p2 = 0, p3 = 0, p5 = 0;
+        for(int i = 1; i < n; i++) {
+            int t = ug[i] = min(min(c2, c3), c5);
+            if (c2 == t) c2 = ug[++p2] * 2; 
+            if (c3 == t) c3 = ug[++p3] * 3;
+            if (c5 == t) c5 = ug[++p5] * 5;
+        }
+        return ug[n-1];
+        
+    }
+};
diff --git a/Week02/LeetCodes/94_Binary_Tree_Inorder_Traversal.cpp b/Week02/LeetCodes/94_Binary_Tree_Inorder_Traversal.cpp
@@ -0,0 +1,27 @@
+class Solution {
+public:
+    enum {Black=0, White};
+    vector<int> inorderTraversal(TreeNode* root) {
+        if (!root) return {};
+
+        stack<pair<TreeNode*, int>> s;
+        s.push({root, Black});
+
+        vector<int> res;
+        while(s.size()) {
+            pair<TreeNode*, int> node = s.top();
+            s.pop();
+            if (node.second == White) {
+                res.push_back(node.first->val);
+            } else {
+                if (node.first->right) s.push({node.first->right, Black});
+                s.push({node.first, White});
+                if (node.first->left) s.push({node.first->left, Black});
+            }
+        }
+
+        return res;
+    
+    }
+
+};
diff --git a/Week02/NOTE.md b/Week02/NOTE.md
@@ -1 +1,20 @@
-学习笔记
+学习笔记
+
+树的遍历
+1.前中后序遍历
+	递归写法注意边界条件和顺序。
+	非递归写法可以用颜色栈比较方便。
+2.重建树，已知前中、中后，求剩下的遍历
+	前序的首即为根，后序的尾即为根，在中序中检索，可以求得左子树、右子树
+	对于前后序，求中序，则无法确定左右子树，如前{4，7}， 后{7，4}
+
+堆
+1.建堆、排序、调整算法
+2.大根堆一般用于排序，小根堆一般用于组建优先队列（摘自算法导论）
+3.priority_queue<T, container<T>, compare<T>>
+	默认使用less即大根堆
+	可以使用lambda表达式作为第三个参数
+        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second;};
+        priority_queue<pair<int, int> , vector<pair<int, int>>, decltype(cmp)> pq(cmp);
+4.当TopK问题中的n取值范围较为固定时，可以使用线性排序算法以取得更优的时间复杂度O(n)，如桶排序，计数排序，基数排序。
+ 
