Skip to content

Commit 29af5be

Browse files
znn0301znn0301
committed
hash heap
1 parent cdc2f82 commit 29af5be

File tree

8 files changed

+393
-2
lines changed

8 files changed

+393
-2
lines changed

‎src/main/java/com/chen/algorithm/znn/hash/test15/Solution.java‎

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
package com.chen.algorithm.znn.hash.test15;
2+
3+
import org.junit.Test;
4+
5+
import java.util.ArrayList;
6+
import java.util.Arrays;
7+
import java.util.List;
8+
9+
/**
10+
* @Auther: zhunn
11+
* @Date: 2020/10/26 14:35
12+
* @Description: 三数之和：排序+双指针
13+
*/
14+
public class Solution {
15+
16+
/**
17+
* 官方解法
18+
*
19+
* @param nums
20+
* @return
21+
*/
22+
public List<List<Integer>> threeSum1(int[] nums) {
23+
int n = nums.length;
24+
Arrays.sort(nums);
25+
List<List<Integer>> ans = new ArrayList<>();
26+
// 枚举 a
27+
for (int first = 0; first < n; ++first) {
28+
// 需要和上一次枚举的数不相同
29+
if (first > 0 && nums[first] == nums[first - 1]) {
30+
continue;
31+
}
32+
// c 对应的指针初始指向数组的最右端
33+
int third = n - 1;
34+
int target = -nums[first];
35+
// 枚举 b
36+
for (int second = first + 1; second < n; ++second) {
37+
// 需要和上一次枚举的数不相同
38+
if (second > first + 1 && nums[second] == nums[second - 1]) {
39+
continue;
40+
}
41+
// 需要保证 b 的指针在 c 的指针的左侧
42+
while (second < third && nums[second] + nums[third] > target) {
43+
--third;
44+
}
45+
// 如果指针重合，随着 b 后续的增加
46+
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
47+
if (second == third) {
48+
break;
49+
}
50+
if (nums[second] + nums[third] == target) {
51+
List<Integer> list = new ArrayList<>();
52+
list.add(nums[first]);
53+
list.add(nums[second]);
54+
list.add(nums[third]);
55+
ans.add(list);
56+
}
57+
}
58+
}
59+
return ans;
60+
}
61+
62+
//public List<List<Integer>> threeSum(int[] nums) {
63+
// int n = nums.length;
64+
// Arrays.sort(nums);
65+
// List<List<Integer>> ans = new ArrayList<>();
66+
// for (int first = 0; first < n; ++first) {
67+
// if (first > 0 && nums[first] == nums[first - 1]) {
68+
// continue;
69+
// }
70+
// int third = n - 1;
71+
// int target = -nums[first];
72+
// for (int second = first + 1; second < n; ++second) {
73+
// if (second > first + 1 && nums[second] == nums[second - 1]) {
74+
// continue;
75+
// }
76+
// while (second < third && nums[second] + nums[third] > target) {
77+
// --third;
78+
// }
79+
// if (second == third) {
80+
// break;
81+
// }
82+
// if (nums[second] + nums[third] == target) {
83+
// List<Integer> list = new ArrayList<>();
84+
// list.add(nums[first]);
85+
// list.add(nums[second]);
86+
// list.add(nums[third]);
87+
// ans.add(list);
88+
// }
89+
// }
90+
// }
91+
// return ans;
92+
//}
93+
94+
/**
95+
* 推荐此方法，方便记忆
96+
*
97+
* @param nums
98+
* @return
99+
*/
100+
public List<List<Integer>> threeSum2(int[] nums) {
101+
if (nums == null || nums.length < 3) {
102+
return null;
103+
}
104+
105+
List<List<Integer>> ans = new ArrayList<>();
106+
Arrays.sort(nums);
107+
int len = nums.length;
108+
for (int i = 0; i < len; i++) {
109+
if (nums[i] > 0) { // 第一个数大于0，后面的数是递增的，不会有等于0的组合，直接返回结果
110+
return ans;
111+
}
112+
if (i > 0 && nums[i] == nums[i - 1]) { // 去重
113+
continue;
114+
}
115+
int L = i + 1;
116+
int R = len - 1;
117+
while (L < R) {
118+
int sum = nums[i] + nums[L] + nums[R];
119+
if (sum == 0) {
120+
ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
121+
while (L < R && nums[L] == nums[L + 1]) { // 去重
122+
L++;
123+
}
124+
while (L < R && nums[R] == nums[R - 1]) { // 去重
125+
R--;
126+
}
127+
L++;
128+
R--;
129+
} else if (sum < 0) {
130+
L++;
131+
} else {
132+
R--;
133+
}
134+
}
135+
}
136+
return ans;
137+
}
138+
139+
@Test
140+
public void test() {
141+
int[] arrayNum = {-1, 0, 1, 4, 2, -1, -4};
142+
List<List<Integer>> result = threeSum2(arrayNum);
143+
System.out.println(result);
144+
}
145+
}

‎src/main/java/com/chen/algorithm/znn/hash/test18/Solution.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.chen.algorithm.znn.hash.test18;
2+
3+
import com.alibaba.fastjson.JSON;
4+
import org.junit.Test;
5+
6+
import java.util.ArrayList;
7+
import java.util.Arrays;
8+
import java.util.List;
9+
10+
/**
11+
* @Auther: zhunn
12+
* @Date: 2020/10/26 15:09
13+
* @Description: 四数之和：类比三数之和方法
14+
*/
15+
public class Solution {
16+
17+
public List<List<Integer>> fourSum(int[] nums, int target) {
18+
if (nums == null || nums.length < 4) {
19+
return null;
20+
}
21+
22+
List<List<Integer>> ans = new ArrayList<>();
23+
Arrays.sort(nums);
24+
25+
for (int i = 0; i < nums.length; i++) {
26+
if (i > 0 && nums[i] == nums[i - 1]) {
27+
continue;
28+
}
29+
for (int j = i + 1; j < nums.length; j++) {
30+
if (j > i + 1 && nums[j] == nums[j - 1]) {
31+
continue;
32+
}
33+
int L = j + 1;
34+
int R = nums.length - 1;
35+
while (L < R) {
36+
int sum = nums[i] + nums[j] + nums[L] + nums[R];
37+
if (sum == target) {
38+
ans.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));
39+
while (L < R && nums[L] == nums[L + 1]) {
40+
L++;
41+
}
42+
while (L < R && nums[R] == nums[R - 1]) {
43+
R--;
44+
}
45+
L++;
46+
R--;
47+
} else if (sum < target) {
48+
L++;
49+
} else {
50+
R--;
51+
}
52+
}
53+
}
54+
}
55+
return ans;
56+
}
57+
58+
@Test
59+
public void test() {
60+
int[] nums = {1, 0, -1, 0, -2, 2};
61+
List<List<Integer>> ans = fourSum(nums, 0);
62+
System.out.println(JSON.toJSONString(ans));
63+
}
64+
}

‎src/main/java/com/chen/algorithm/znn/hash/test242/Solution.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,8 @@ public boolean isAnagram(String s, String t) {
2121
counter[t.charAt(i) - 'a']--;
2222
}
2323

24-
for (int n : counter) {
25-
if (n != 0) {
24+
for (int i = 0; i < counter.length; i++) {
25+
if (counter[i] != 0) {
2626
return false;
2727
}
2828
}

‎src/main/java/com/chen/algorithm/znn/hash/test49/Solution.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.chen.algorithm.znn.hash.test49;
2+
3+
import org.junit.Test;
4+
5+
import java.util.*;
6+
7+
/**
8+
* @Auther: zhunn
9+
* @Date: 2020/10/26 11:19
10+
* @Description: 字母异位词分组
11+
*/
12+
public class Solution {
13+
14+
public List<List<String>> groupAnagrams(String[] strs) {
15+
if (strs == null || strs.length == 0) {
16+
return null;
17+
}
18+
19+
Map<String, List<String>> resuMap = new HashMap<>();
20+
21+
for (int i = 0; i < strs.length; i++) {
22+
23+
char[] chars = strs[i].toCharArray();
24+
Arrays.sort(chars);
25+
String key = new String(chars);
26+
27+
if (!resuMap.containsKey(key)) {
28+
resuMap.put(key, new ArrayList<>());
29+
}
30+
resuMap.get(key).add(strs[i]);
31+
}
32+
return new ArrayList<>(resuMap.values());
33+
}
34+
35+
@Test
36+
public void test() {
37+
String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
38+
List<List<String>> result = groupAnagrams(words);
39+
System.out.println(result);
40+
}
41+
}

‎src/main/java/com/chen/algorithm/znn/heap/Test.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,10 @@
44
* @Auther: zhunn
55
* @Date: 2020/10/24 17:23
66
* @Description: 堆相关
7+
* 1、堆的基本操作 heap/Heap
8+
*
9+
* 2、堆化，大根堆，小根堆，堆排序，堆的应用（优先级队列，topK，中位数）
10+
* java的priorityQueue 用小根堆实现的优先级队列
711
*/
812
public class Test {
913
}

‎src/main/java/com/chen/algorithm/znn/heap/test215/Solution.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.chen.algorithm.znn.heap.test215;
2+
3+
import org.junit.Test;
4+
5+
import java.util.PriorityQueue;
6+
7+
/**
8+
* @Auther: zhunn
9+
* @Date: 2020/10/26 16:55
10+
* @Description: 求数组中的第K个最大元素：1-暴力；2-优先级队列
11+
*/
12+
public class Solution {
13+
14+
public int findKthLargest1(int[] nums, int k) {
15+
//if (nums == null || k > nums.length) {
16+
// return -1;
17+
//}
18+
19+
for (int i = 0; i < nums.length - 1; i++) {
20+
for (int j = i + 1; j < nums.length; j++) {
21+
if (nums[j] > nums[i]) {
22+
int temp = nums[i];
23+
nums[i] = nums[j];
24+
nums[j] = temp;
25+
}
26+
}
27+
}
28+
29+
return nums[k - 1];
30+
}
31+
32+
public int findKthLargest(int[] nums, int k) {
33+
PriorityQueue<Integer> queue = new PriorityQueue<>(k);
34+
for (int i = 0; i < nums.length; i++) {
35+
if (queue.size() < k) {
36+
queue.add(nums[i]);
37+
} else if (nums[i] > queue.peek()) {
38+
queue.poll();
39+
queue.add(nums[i]);
40+
}
41+
}
42+
return queue.peek();
43+
}
44+
45+
46+
@Test
47+
public void testCase() {
48+
int[] n = {3, 2, 3, 1, 2, 4, 5, 5, 6};
49+
System.out.println(findKthLargest(n, 2));
50+
51+
}
52+
}

‎src/main/java/com/chen/algorithm/znn/stack/test155/Solution.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.chen.algorithm.znn.stack.test155;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* @Auther: zhunn
7+
* @Date: 2020/10/26 18:20
8+
* @Description: 最小栈
9+
*/
10+
public class Solution {
11+
12+
public Stack<Integer> stack = new Stack<>();
13+
public Stack<Integer> minStack = new Stack<>();
14+
15+
public void push(Integer value) {
16+
stack.push(value);
17+
18+
if (minStack.isEmpty() || value < minStack.peek()) {
19+
minStack.push(value);
20+
}
21+
}
22+
23+
public void pop() {
24+
if (stack.pop().equals(minStack.peek())) {
25+
minStack.pop();
26+
}
27+
}
28+
29+
public int top() {
30+
return stack.peek();
31+
}
32+
33+
public int getMin() {
34+
return minStack.peek();
35+
}
36+
}

0 commit comments

Comments
 (0)