Merge pull request algorithm001#565 from zsndev/master

GeekUniversity · web-flow · commit da00806954f9 · 2019-05-06T12:13:09.000+08:00
week3-129
diff --git a/Week_03/id_129/LeetCode_104_129.java b/Week_03/id_129/LeetCode_104_129.java
@@ -0,0 +1,7 @@
+import java.util.PriorityQueue;
+
+public class LeetCode_104_129 {
+    public int maxDepth(TreeNode root) {
+        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
+    }
+}
diff --git a/Week_03/id_129/LeetCode_373_129.java b/Week_03/id_129/LeetCode_373_129.java
@@ -0,0 +1,27 @@
+import java.util.ArrayList;
+import java.util.List;
+import java.util.PriorityQueue;
+
+public class LeetCode_373_129 {
+    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
+        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] + b[1] - a[0] - a[1]);
+        List<int[]> res = new ArrayList<>();
+        if (nums1.length == 0 || nums2.length == 0 || k == 0) return res;
+        for (int i = 0; i < Math.min(nums1.length, k); i++) {
+            for (int j = 0; j < Math.min(nums2.length, k); j++) {
+                int[] cur = new int[]{nums1[i], nums2[j]};
+                if (queue.size() < k) {
+                    queue.add(cur);
+                } else if (queue.peek()[0] + queue.peek()[1] > cur[0] + cur[1]) {
+                    queue.poll();
+                    queue.add(cur);
+                }
+            }
+        }
+
+        while (!queue.isEmpty()) {
+            res.add(queue.poll());
+        }
+        return res;
+    }
+}
diff --git a/Week_03/id_129/LeetCode_703_129.java b/Week_03/id_129/LeetCode_703_129.java
@@ -0,0 +1,25 @@
+import java.util.PriorityQueue;
+
+public class LeetCode_703_129 {
+    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+    private int size;
+
+    public LeetCode_703_129(int k, int[] nums) {
+        KthLargest(k, nums);
+    }
+
+    public void KthLargest(int k, int[] nums) {
+        this.size = k;
+        for (int n : nums) add(n);
+    }
+
+    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();
+    }
+
+}
diff --git a/Week_03/id_129/TreeNode.java b/Week_03/id_129/TreeNode.java
@@ -0,0 +1,9 @@
+public class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
