第一周

zhangruihao.zhang · zhangruihao.zhang · commit 1942f2270082 · 2019-05-03T23:22:14.000+08:00
diff --git a/Week_01/id_108/LeetCode_687_108.java b/Week_01/id_108/LeetCode_687_108.java
@@ -0,0 +1,50 @@
+/**
+ * @author zhangruihao.zhang
+ * @version v1.0.0
+ * @since 2019/05/03
+ */
+public class LeetCode_687_108 {
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        int maxLen = 0;
+        public int longestUnivaluePath(TreeNode root) {
+            if(root == null){
+                return 0;
+            }
+            longest(root);
+            return maxLen;
+        }
+
+        private int longest(TreeNode root){
+            if(root == null){
+                return 0;
+            }
+            int leftLen=longest( root.left);
+            int rightLen=longest( root.right);
+            int leftUnivalueLen = 0;
+            int rightUnivalue = 0;
+            if(root.left != null && root.left.val == root.val){
+                leftUnivalueLen = leftLen + 1;
+            }
+
+            if(root.right != null && root.right.val == root.val){
+                rightUnivalue = rightLen + 1;
+            }
+
+            maxLen = max(maxLen , leftUnivalueLen + rightUnivalue );
+            return max(leftUnivalueLen,rightUnivalue);
+        }
+
+        private int max(int x,int y){
+            return x>y ? x : y;
+        }
+    }
+}
diff --git a/Week_01/id_108/LeetCode_895_108.java b/Week_01/id_108/LeetCode_895_108.java
@@ -0,0 +1,83 @@
+import org.junit.Test;
+
+import java.util.HashMap;
+import java.util.PriorityQueue;
+
+/**
+ * @author zhangruihao.zhang
+ * @version v1.0.0
+ * @since 2019/05/03
+ */
+public class LeetCode_895_108 {
+
+    class FreqStack {
+
+        private PriorityQueue<Pair> queue = null;
+        private HashMap<Integer, Integer> itemCountMap = null;
+        private int count;
+
+        public FreqStack() {
+            itemCountMap = new HashMap<>();
+            queue = new PriorityQueue<>((o1, o2) ->
+                    o1.getCount().compareTo(o2.getCount()) == 0 ?
+                            -o1.getOrder().compareTo(o2.getOrder()) : -o1.getCount().compareTo(o2.getCount()));
+        }
+
+        public void push(int x) {
+            count ++;
+            itemCountMap.put(x, itemCountMap.getOrDefault(x, 0) + 1);
+            queue.offer(new Pair(x, count, itemCountMap.getOrDefault(x, 0) + 1));
+        }
+
+        public int pop() {
+            Pair peek = queue.poll();
+            int item = peek == null ? -1 : peek.item;
+            Integer integer = itemCountMap.get(item);
+            if(integer == 1){
+                itemCountMap.remove(item);
+            }else {
+                itemCountMap.put(item, itemCountMap.get(item) - 1);
+            }
+            return item;
+        }
+
+        private class Pair {
+            private int item;
+            //添加入队的顺序
+            private Integer order;
+            //共有几个相同的元素
+            private Integer count;
+
+            public Pair(int item, Integer order, Integer count) {
+                this.item = item;
+                this.order = order;
+                this.count = count;
+            }
+
+            public int getItem() {
+                return item;
+            }
+
+            public void setItem(int item) {
+                this.item = item;
+            }
+
+            public Integer getOrder() {
+                return order;
+            }
+
+            public void setOrder(Integer order) {
+                this.order = order;
+            }
+
+            public Integer getCount() {
+                return count;
+            }
+
+            public void setCount(Integer count) {
+                this.count = count;
+            }
+        }
+    }
+
+}
