大根堆和小根堆 四个数相加

chenweijie · chenweijie · commit c71bbfcb770a · 2020-08-30T17:37:16.000+08:00
diff --git a/src/main/java/com/chen/CacheMap.java b/src/main/java/com/chen/CacheMap.java
@@ -0,0 +1,35 @@
+package com.chen;
+
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-26 10:29
+ */
+public class CacheMap<K, V> extends LinkedHashMap<K, V> {
+
+
+    private int limit;
+
+    public CacheMap(int limit) {
+        super(limit, 0.75f, true);
+        this.limit = limit;
+    }
+
+    public void putVal(K k, V v) {
+        super.put(k, v);
+    }
+
+    public V getVal(K k) {
+        return super.getOrDefault(k, (V) new Object());
+    }
+
+
+    @Override
+    protected boolean removeEldestEntry(Map.Entry<K, V> entry) {
+        return super.size() > limit;
+    }
+
+
+}
diff --git a/src/main/java/com/chen/Node.java b/src/main/java/com/chen/Node.java
diff --git a/src/main/java/com/chen/algorithm/study/test121/Solution3.java b/src/main/java/com/chen/algorithm/study/test121/Solution3.java
@@ -5,6 +5,8 @@
 /**
  * 双指针算法
  *
+ * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
+ *
  * @author :  chen weijie
  * @Date: 2019-11-01 23:54
  */
diff --git a/src/main/java/com/chen/algorithm/study/test18/Solution.java b/src/main/java/com/chen/algorithm/study/test18/Solution.java
@@ -0,0 +1,58 @@
+package com.chen.algorithm.study.test18;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 17:15
+ */
+public class Solution {
+
+
+    public List<List<Integer>> fourSum(int[] nums, int target) {
+
+        List<List<Integer>> res = new ArrayList<>();
+        if (nums == null || nums.length == 0) {
+            return res;
+        }
+        Arrays.sort(nums);
+
+        for (int i = 0; i < nums.length; i++) {
+            if (i > 0 && nums[i - 1] == nums[i]) {
+                continue;
+            }
+
+            for (int j = i + 1; j < nums.length; j++) {
+
+                if (j > i + 1 && nums[j - 1] == nums[j]) {
+                    continue;
+                }
+                int left = j + 1, right = nums.length - 1;
+                while (left < right) {
+                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
+
+                    if (sum > target) {
+                        right--;
+                    } else if (sum < target) {
+                        left++;
+                    } else {
+                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
+
+                        while (left < right && nums[left + 1] == nums[left]) {
+                            left++;
+                        }
+                        while (left < right && nums[right] == nums[right - 1]) {
+                            right--;
+                        }
+                        left++;
+                        right--;
+                    }
+                }
+            }
+        }
+
+        return res;
+    }
+}
diff --git a/src/main/java/com/chen/algorithm/study/test227/Solution.java b/src/main/java/com/chen/algorithm/study/test227/Solution.java
@@ -56,8 +56,7 @@ public int calculate(String s) {
 
         int res = 0;
         while (!stack.isEmpty()) {
-            res += stack.peek();
-            stack.pop();
+            res += stack.pop();
         }
 
         return res;
@@ -66,7 +65,7 @@ public int calculate(String s) {
 
     @Test
     public void testCase() {
-        System.out.println(calculate("3/2"));
+        System.out.println(calculate("-30+5/2 "));
     }
 
 
diff --git a/src/main/java/com/chen/algorithm/study/test239/Solution.java b/src/main/java/com/chen/algorithm/study/test239/Solution.java
@@ -0,0 +1,54 @@
+package com.chen.algorithm.study.test239;
+
+import org.junit.Test;
+
+import java.util.ArrayDeque;
+import java.util.Arrays;
+
+/**
+ * https://leetcode-cn.com/problems/sliding-window-maximum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-3/
+ * @author :  chen weijie
+ * @Date: 2020-08-30 01:29
+ */
+public class Solution {
+
+
+    public int[] maxSlidingWindow(int[] nums, int k) {
+
+        int[] res = new int[nums.length - k + 1];
+        // 递减队列
+        ArrayDeque<Integer> queue = new ArrayDeque<>();
+
+        for (int i = 0; i < nums.length; i++) {
+
+            // 添加滑入的数 nums[i] ，构造递减队列
+            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
+                queue.pollLast();
+            }
+            queue.addLast(nums[i]);
+
+            // 删除滑出的数 nums[i - k]，如果删除的数等于队头，删除队头
+            if (i >= k && nums[i - k] == queue.peekFirst()) {
+                queue.pollFirst();
+            }
+
+            // 写入当前最大值
+            if (i >= k - 1) {
+                res[i - k + 1] = queue.peekFirst();
+            }
+        }
+        return res;
+    }
+
+    @Test
+    public void testCase() {
+
+        int[] nums = {1, 3, -1, -3, 5, 3, 2, 6, 7};
+        int k = 3;
+        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
+
+
+    }
+
+
+}
diff --git a/src/main/java/com/chen/algorithm/study/test242/Solution2.java b/src/main/java/com/chen/algorithm/study/test242/Solution2.java
@@ -0,0 +1,30 @@
+package com.chen.algorithm.study.test242;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2020-08-30 16:21
+ */
+public class Solution2 {
+
+
+    public boolean isAnagram(String s, String t) {
+
+        if (s.length() != t.length()) {
+            return false;
+        }
+
+        int[] counter = new int[26];
+
+        for (int i = 0; i < s.length(); i++) {
+            counter[s.charAt(i) - 'a']++;
+            counter[t.charAt(i) - 'a']--;
+        }
+
+        for (int count : counter) {
+            if (count != 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+}
diff --git a/src/main/java/com/chen/dataStructure/study/queen/priorityQueue/MaxHeap.java b/src/main/java/com/chen/dataStructure/study/queen/priorityQueue/MaxHeap.java
@@ -0,0 +1,42 @@
+package com.chen.dataStructure.study.queen.priorityQueue;
+
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+/**
+ * PriorityQueue 默认实现的是小顶堆，如果传入comparator参数定义排序，则可以实现大顶堆。
+ *
+ * @author :  chen weijie
+ * @Date: 2020-08-30 01:23
+ */
+public class MaxHeap {
+
+    private int size;
+
+    public PriorityQueue<Integer> queue = new PriorityQueue<>(size, new Comparator<Integer>() {
+        @Override
+        public int compare(Integer o1, Integer o2) {
+            return o2 - o1;
+        }
+    });
+
+    public MaxHeap(int size, int[] nums) {
+        this.size = size;
+        for (int n : nums) {
+            add(n);
+        }
+    }
+
+
+    private Integer add(int val) {
+
+        if (queue.size() < size) {
+            queue.offer(val);
+        } else if (queue.peek() != null && queue.peek() > val) {
+            queue.poll();
+            queue.offer(val);
+        }
+        return queue.peek();
+    }
+
+}

Original file line number	Diff line number	Diff line change
`@@ -5,6 +5,8 @@`
`5`	`5`	`/**`
`6`	`6`	`* 双指针算法`
`7`	`7`	`*`
	`8`	`+ * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/`
	`9`	`+ *`
`8`	`10`	`* @author : chen weijie`
`9`	`11`	`* @Date: 2019-11-01 23:54`
`10`	`12`	`*/`
Original file line number	Diff line number	Diff line change
`@@ -56,8 +56,7 @@ public int calculate(String s) {`
`56`	`56`
`57`	`57`	`int res = 0;`
`58`	`58`	`while (!stack.isEmpty()) {`
`59`		`- res += stack.peek();`
`60`		`- stack.pop();`
	`59`	`+ res += stack.pop();`
`61`	`60`	`}`
`62`	`61`
`63`	`62`	`return res;`
`@@ -66,7 +65,7 @@ public int calculate(String s) {`
`66`	`65`
`67`	`66`	`@Test`
`68`	`67`	`public void testCase() {`
`69`		`- System.out.println(calculate("3/2"));`
	`68`	`+ System.out.println(calculate("-30+5/2 "));`
`70`	`69`	`}`
`71`	`70`
`72`	`71`