Merge pull request algorithm001#595 from Fanlu91/master

GeekUniversity · web-flow · commit 0f3049f1d41b · 2019-05-06T12:08:05.000+08:00
week 3 homework id 26
diff --git a/Week_03/id_26/Leetcode_703_26.java b/Week_03/id_26/Leetcode_703_26.java
@@ -0,0 +1,42 @@
+package com.fanlu.leetcode.heap;
+
+import java.util.PriorityQueue;
+
+// Source : https://leetcode.com/problems/kth-largest-element-in-a-stream/
+// Id     : 703
+// Author : Fanlu Hai
+// Date   : 2018-05-05
+// Other  : should implement priority queue manually
+// Tips   :
+
+
+public class KthLargest {
+
+    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+    private int size;
+
+    public KthLargest(int k, int[] nums) {
+        this.size = k;
+        for (int n : nums) {
+            add(n);
+        }
+    }
+
+    //99.55% 64.02%
+    public int add(int val) {
+        if (minHeap.size() < size)
+            minHeap.offer(val);
+        else if (minHeap.peek() < val) {
+            minHeap.poll();
+            minHeap.offer(val);
+        }
+        return minHeap.peek();
+    }
+
+}
+
+/**
+ * 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_26/Leetcode_997_26.java b/Week_03/id_26/Leetcode_997_26.java
@@ -0,0 +1,37 @@
+package com.fanlu.leetcode.graph;
+// Source : https://leetcode.com/problems/find-the-town-judge/
+// Id     : 997
+// Author : Fanlu Hai
+// Date   : 2018-05-03
+// Other  :
+// Tips   :
+
+
+public class FindTheTownJudge {
+
+    //98.73% 100.00%
+    public int findJudge(int N, int[][] trust) {
+        boolean[] notJudge = new boolean[N + 1];
+        int[] beingTrusted = new int[N + 1];
+
+        for (int[] pair : trust) {
+            // if trust others, then not judge
+            notJudge[pair[0]] = true;
+
+            boolean not = notJudge[pair[0]];
+            int beTru = pair[1];
+
+            if (notJudge[pair[1]]) {
+                continue;
+            }
+            beingTrusted[pair[1]]++;
+        }
+
+        for (int i = 1; i < N + 1; i++) {
+            if (beingTrusted[i] == N - 1 && !notJudge[i])
+                return i;
+        }
+        return -1;
+    }
+
+}
