Skip to content

Commit de38715

Browse files
author
chenweijie
committed
update
1 parent 5ddc504 commit de38715

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

44 files changed

+1821
-232
lines changed

‎src/main/java/com/chen/Test.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.chen;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2020-09-18 20:03
6+
*/
7+
public class Test {
8+
9+
10+
11+
}

‎src/main/java/com/chen/algorithm/study/test107/Solution.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.chen.algorithm.study.test107;
2+
3+
import java.util.*;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2020-09-16 14:57
8+
*/
9+
public class Solution {
10+
11+
public List<List<Integer>> levelOrderBottom(TreeNode root) {
12+
List<List<Integer>> res = new ArrayList<>();
13+
14+
if (root == null) {
15+
return res;
16+
}
17+
18+
Queue<TreeNode> queue = new LinkedList<>();
19+
queue.add(root);
20+
Stack<List<Integer>> stack = new Stack<>();
21+
22+
while (!queue.isEmpty()) {
23+
int size = queue.size();
24+
List<Integer> list = new ArrayList<>();
25+
// res.add(list);
26+
stack.push(list);
27+
for (int i = 0; i < size; i++) {
28+
TreeNode node = queue.remove();
29+
list.add(node.val);
30+
31+
if (node.left != null) {
32+
queue.add(node.left);
33+
}
34+
if (node.right != null) {
35+
queue.add(node.right);
36+
}
37+
}
38+
}
39+
// res = new ArrayList<>();
40+
while (!stack.isEmpty()) {
41+
res.add(stack.pop());
42+
}
43+
44+
return res;
45+
}
46+
}

‎src/main/java/com/chen/algorithm/study/test107/TreeNode.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.chen.algorithm.study.test107;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-11-01 00:03
6+
*/
7+
public class TreeNode {
8+
9+
int val;
10+
11+
TreeNode left;
12+
13+
TreeNode right;
14+
15+
public TreeNode() {
16+
}
17+
18+
public TreeNode(int val) {
19+
this.val = val;
20+
}
21+
22+
public int getVal() {
23+
return val;
24+
}
25+
26+
public void setVal(int val) {
27+
this.val = val;
28+
}
29+
30+
public TreeNode getLeft() {
31+
return left;
32+
}
33+
34+
public void setLeft(TreeNode left) {
35+
this.left = left;
36+
}
37+
38+
public TreeNode getRight() {
39+
return right;
40+
}
41+
42+
public void setRight(TreeNode right) {
43+
this.right = right;
44+
}
45+
}

‎src/main/java/com/chen/algorithm/study/test11/Solution2.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.chen.algorithm.study.test11;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2019-11-08 23:37
8+
*/
9+
public class Solution2 {
10+
11+
12+
public int maxArea(int[] height) {
13+
14+
int maxArea = 0;
15+
16+
int i = 0, j = height.length - 1;
17+
18+
while (i < j){
19+
maxArea = Math.max((j - i) * Math.min(height[i], height[j]), maxArea);
20+
if (height[i] < height[j]) {
21+
i++;
22+
} else {
23+
j--;
24+
}
25+
}
26+
return maxArea;
27+
}
28+
29+
30+
@Test
31+
public void testCase() {
32+
33+
int[] n = {1, 8, 6, 2, 5, 4, 8, 3, 7};
34+
35+
System.out.println(maxArea(n));
36+
37+
}
38+
39+
40+
}

‎src/main/java/com/chen/algorithm/study/test120/Solution1.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.chen.algorithm.study.test120;
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+
* @author : chen weijie
11+
* @Date: 2020-05-17 20:07
12+
*/
13+
public class Solution1 {
14+
15+
public int minimumTotal(List<List<Integer>> triangle) {
16+
17+
int m = triangle.size();
18+
int n = triangle.get(m-1).size();
19+
int[][] dp = new int[m + 1][n + 1];
20+
21+
for (int i = m - 1; i >= 0; i--) {
22+
for (int j = 0; j < triangle.get(i).size(); j++) {
23+
dp[i][j] = Math.min(dp[i+1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
24+
}
25+
}
26+
return dp[0][0];
27+
}
28+
29+
30+
@Test
31+
public void testCase() {
32+
33+
List<List<Integer>> triangle = new ArrayList<>();
34+
35+
triangle.add(Arrays.asList(2));
36+
triangle.add(Arrays.asList(3, 4));
37+
triangle.add(Arrays.asList(6, 5, 7));
38+
triangle.add(Arrays.asList(4, 1, 8, 3));
39+
40+
System.out.println(minimumTotal(triangle));
41+
42+
}
43+
44+
}

‎src/main/java/com/chen/algorithm/study/test146/LRUCache.java

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package com.chen.algorithm.study.test146;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
8+
*
9+
* @author : chen weijie
10+
* @Date: 2019-12-05 23:11
11+
*/
12+
public class LRUCache {
13+
14+
15+
class DLinkedNode {
16+
int key;
17+
int value;
18+
DLinkedNode prev;
19+
DLinkedNode next;
20+
21+
public DLinkedNode() {
22+
}
23+
24+
public DLinkedNode(int _key, int _value) {
25+
key = _key;
26+
value = _value;
27+
}
28+
}
29+
30+
private Map<Integer, DLinkedNode> cache = new HashMap<>();
31+
private int size;
32+
private int capacity;
33+
private DLinkedNode head, tail;
34+
35+
public LRUCache(int capacity) {
36+
this.size = 0;
37+
this.capacity = capacity;
38+
// 使用伪头部和伪尾部节点
39+
head = new DLinkedNode();
40+
tail = new DLinkedNode();
41+
head.next = tail;
42+
tail.prev = head;
43+
}
44+
45+
public int get(int key) {
46+
DLinkedNode node = cache.get(key);
47+
if (node == null) {
48+
return -1;
49+
}
50+
// 如果 key 存在，先通过哈希表定位，再移到头部
51+
moveToHead(node);
52+
return node.value;
53+
}
54+
55+
public void put(int key, int value) {
56+
DLinkedNode node = cache.get(key);
57+
if (node == null) {
58+
// 如果 key 不存在，创建一个新的节点
59+
DLinkedNode newNode = new DLinkedNode(key, value);
60+
// 添加进哈希表
61+
cache.put(key, newNode);
62+
// 添加至双向链表的头部
63+
addToHead(newNode);
64+
++size;
65+
if (size > capacity) {
66+
// 如果超出容量，删除双向链表的尾部节点
67+
DLinkedNode tail = removeTail();
68+
// 删除哈希表中对应的项
69+
cache.remove(tail.key);
70+
--size;
71+
}
72+
} else {
73+
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
74+
node.value = value;
75+
moveToHead(node);
76+
}
77+
}
78+
79+
private void addToHead(DLinkedNode node) {
80+
node.prev = head;
81+
node.next = head.next;
82+
head.next.prev = node;
83+
head.next = node;
84+
}
85+
86+
private void removeNode(DLinkedNode node) {
87+
node.prev.next = node.next;
88+
node.next.prev = node.prev;
89+
}
90+
91+
private void moveToHead(DLinkedNode node) {
92+
removeNode(node);
93+
addToHead(node);
94+
}
95+
96+
private DLinkedNode removeTail() {
97+
DLinkedNode res = tail.prev;
98+
removeNode(res);
99+
return res;
100+
}
101+
102+
}

‎src/main/java/com/chen/algorithm/study/test146/LRUCacheDemo.java

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package com.chen.algorithm.study.test146;
2+
3+
import java.util.HashMap;
4+
5+
/**
6+
* https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
7+
*
8+
* @author : chen weijie
9+
* @Date: 2019-12-05 23:11
10+
*/
11+
public class LRUCacheDemo {
12+
13+
class DoubleLinkedListNode {
14+
int k;
15+
int v;
16+
DoubleLinkedListNode pre;
17+
DoubleLinkedListNode next;
18+
19+
public DoubleLinkedListNode() {
20+
}
21+
22+
public DoubleLinkedListNode(int key, int value) {
23+
this.k = key;
24+
this.v = value;
25+
}
26+
}
27+
28+
29+
private HashMap<Integer, DoubleLinkedListNode> hashMap = new HashMap<>();
30+
private int size;
31+
private int capcity;
32+
private DoubleLinkedListNode head, tail;
33+
34+
public LRUCacheDemo(int capcity, int value) {
35+
this.size = 0;
36+
this.capcity = capcity;
37+
DoubleLinkedListNode head = new DoubleLinkedListNode();
38+
DoubleLinkedListNode tail = new DoubleLinkedListNode();
39+
head.next = tail;
40+
tail.pre = head;
41+
}
42+
43+
44+
public int getValue(int key) {
45+
46+
47+
48+
return 0;
49+
50+
}
51+
52+
public void put() {
53+
54+
55+
}
56+
57+
58+
public void removeNode() {
59+
60+
61+
}
62+
63+
64+
public void moveToHead() {
65+
66+
67+
}
68+
69+
public void addToHead() {
70+
71+
72+
}
73+
74+
public void removeTail() {
75+
76+
}
77+
78+
79+
}

0 commit comments

Comments
 (0)