Merge pull request algorithm001#614 from MrQingQuan/master

GeekUniversity · web-flow · commit 55af3dd89f1f · 2019-05-06T12:05:43.000+08:00
046-第三周作业提交
diff --git a/Week_03/id_46/leetcode_210_046.cpp b/Week_03/id_46/leetcode_210_046.cpp
@@ -0,0 +1,34 @@
+class Solution {
+public:
+    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
+        vector<vector<int>> nodeLink(numCourses, vector<int>(0));
+        vector<int> result,degree(numCourses,0);
+        for(auto i:prerequisites){
+            nodeLink[i[1]].push_back(i[0]);
+            degree[i[0]]++;
+        }
+        queue<int> nodequeue;
+        for(int i=0; i<degree.size(); i++){
+            if(degree[i] ==0 ){
+                nodequeue.push(i);
+                result.push_back(i);       
+            }
+        }
+        while(!nodequeue.empty()){
+            int tmp = nodequeue.front();
+            nodequeue.pop();
+            for(auto i:nodeLink[tmp]){
+                degree[i]--;
+                if(degree[i]==0){
+                    nodequeue.push(i);
+                    result.push_back(i);  
+                }
+            }
+        }
+        for(int i=0; i<degree.size(); i++){
+            if(degree[i] !=0 )
+                result.clear();
+        }
+        return result;
+    }
+};
diff --git a/Week_03/id_46/leetcode_373_046.cpp b/Week_03/id_46/leetcode_373_046.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+struct cmp{
+    bool operator() ( pair<int,int> &a, pair<int,int> &b ){  
+        return a.first + a.second <= b.first + b.second; }
+};
+vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
+    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
+    for(int i=0; i<min((int)nums1.size(), k); i++){
+        for(int j=0; j<min((int)nums2.size(), k); j++){
+            q.push(make_pair(nums1[i],nums2[j]));
+            if(q.size()>k)
+                q.pop();
+        }
+    }
+    vector<vector<int>> result;
+    while(q.size()>0){
+        vector<int> tmp;
+        tmp.push_back(q.top().first);
+        tmp.push_back(q.top().second);
+        result.push_back(tmp);
+        q.pop();
+    }
+    return result;
+}
+};
diff --git a/Week_03/id_46/leetcode_429_046.cpp b/Week_03/id_46/leetcode_429_046.cpp
@@ -0,0 +1,37 @@
+/*
+// Definition for a Node.
+class Node {
+public:
+    int val;
+    vector<Node*> children;
+
+    Node() {}
+
+    Node(int _val, vector<Node*> _children) {
+        val = _val;
+        children = _children;
+    }
+};
+*/
+class Solution {
+public:
+    vector<vector<int>> levelOrder(Node* root) {
+        vector<vector<int>> result;
+        if(!root) return result;
+        queue<Node*> nq;
+        nq.push(root);
+        while(nq.size()>0){
+            vector<int> tempres;
+            int nqsize = nq.size();
+            for(int i=0; i<nqsize; i++){
+                Node* tmp = nq.front();
+                nq.pop();
+                tempres.push_back(tmp->val);
+                for(int j=0; j<tmp->children.size(); j++)
+                    nq.push(tmp->children[j]);
+            }
+            result.push_back(tempres);
+        }
+        return result;
+    }
+};
diff --git a/Week_03/id_46/leetcode_703_046.cpp b/Week_03/id_46/leetcode_703_046.cpp
@@ -0,0 +1,31 @@
+class KthLargest {
+public:
+    struct cmp{
+        bool operator()(int &a, int &b){
+            return a>b;
+        }
+    };
+    priority_queue<int,vector<int>,cmp> numset;
+    int cap;
+    KthLargest(int k, vector<int>& nums) {
+        cap = k;
+        for(int i=0; i<nums.size(); i++)
+            add(nums[i]);
+    }
+     
+    int add(int val) {
+        if(numset.size()<cap)
+            numset.push(val);
+        else if(numset.top() < val){
+            numset.pop();
+            numset.push(val);
+        }
+        return numset.top();
+    }
+};
+
+/**
+ * Your KthLargest object will be instantiated and called as such:
+ * KthLargest* obj = new KthLargest(k, nums);
+ * int param_1 = obj->add(val);
+ */
diff --git a/Week_03/id_46/leetcode_997_046.cpp b/Week_03/id_46/leetcode_997_046.cpp
@@ -0,0 +1,32 @@
+class Solution {
+public:
+    int findJudge(int N, vector<vector<int>>& trust) {
+        unordered_map<int,set<int>> trustGraph;
+        for(int i=1; i<=N; i++){
+            set<int> tmp;
+            trustGraph[i] = tmp;
+        }
+        
+        for(int i=0; i<trust.size(); i++)
+            trustGraph[trust[i][0]].insert(trust[i][1]);
+        
+        int res = 0, num = 0;
+        for(auto it=trustGraph.begin(); it!=trustGraph.end(); it++){
+            if(it->second.size()==0){
+                num ++;
+                if(num > 1) return -1;
+                res = it->first;
+            }
+        }
+        
+        for(auto it=trustGraph.begin(); it!=trustGraph.end(); it++){
+            if(it->first != res){
+                auto iter = it->second.find(res);
+                if(iter == it->second.end())
+                    return -1;
+            }
+        }
+        
+        return res;
+    }
+};
