Skip to content

Commit 7cdb593

Browse files
author
chenweijie
committed
算法
1 parent 2a3ceba commit 7cdb593

File tree

12 files changed

+558
-0
lines changed

12 files changed

+558
-0
lines changed

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

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.chen.algorithm.study.test102;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
/**
8+
* @author : chen weijie
9+
* @Date: 2019-12-03 00:47
10+
*/
11+
public class Solution {
12+
13+
14+
class TreeNode {
15+
int val;
16+
TreeNode left;
17+
TreeNode right;
18+
19+
TreeNode(int x) {
20+
val = x;
21+
}
22+
}
23+
24+
25+
public List<List<Integer>> levelOrder(TreeNode root) {
26+
27+
if (root == null) {
28+
return null;
29+
}
30+
31+
32+
List<List<Integer>> result = new ArrayList<>();
33+
34+
result.add(Arrays.asList(root.val));
35+
36+
37+
while (root.left!=null||root.right!=null){
38+
39+
List<Integer> list = new ArrayList<>();
40+
41+
42+
43+
44+
}
45+
46+
47+
48+
49+
return null;
50+
}
51+
52+
53+
}

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

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.chen.algorithm.study.test139;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Arrays;
6+
import java.util.HashSet;
7+
import java.util.List;
8+
import java.util.Set;
9+
10+
/**
11+
* @author : chen weijie
12+
* @Date: 2019-12-04 23:26
13+
*/
14+
public class Solution {
15+
16+
17+
public boolean wordBreak(String s, List<String> wordDict) {
18+
19+
Set<String> wordDictSet = new HashSet<>(wordDict);
20+
21+
boolean[] dp = new boolean[s.length() + 1];
22+
dp[0] = true;
23+
for (int i = 1; i <= s.length(); i++) {
24+
for (int j = 0; j < i; j++) {
25+
26+
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
27+
dp[i] = true;
28+
break;
29+
}
30+
}
31+
}
32+
return dp[s.length()];
33+
}
34+
35+
36+
@Test
37+
public void testCase() {
38+
39+
String s = "catsandog";
40+
List<String> wordDict = Arrays.asList("cats", "dog", "sand", "and", "cat");
41+
42+
System.out.println(wordBreak(s, wordDict));
43+
44+
45+
}
46+
47+
48+
}

‎src/main/java/com/chen/algorithm/study/test142/ListNode.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package com.chen.algorithm.study.test142;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-12-05 00:05
6+
*/
7+
public class ListNode {
8+
9+
int val;
10+
ListNode next;
11+
12+
ListNode(int x) {
13+
val = x;
14+
next = null;
15+
}
16+
}

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

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.chen.algorithm.study.test142;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-12-05 00:05
6+
* https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
7+
*/
8+
public class Solution {
9+
10+
11+
public ListNode detectCycle(ListNode head) {
12+
13+
ListNode slow = head;
14+
ListNode fast = head;
15+
16+
while (true) {
17+
if (fast == null || fast.next == null) {
18+
return null;
19+
}
20+
21+
fast = fast.next.next;
22+
slow = slow.next;
23+
if (fast == slow) {
24+
break;
25+
}
26+
}
27+
28+
fast = head;
29+
while (slow != fast) {
30+
slow = slow.next;
31+
fast = fast.next;
32+
}
33+
34+
return fast;
35+
}
36+
37+
38+
}

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

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.chen.algorithm.study.test142;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
/**
7+
* @author : chen weijie
8+
* @Date: 2019-12-05 00:16
9+
*/
10+
public class Solution2 {
11+
12+
13+
public ListNode detectCycle(ListNode head) {
14+
15+
Set<ListNode> set = new HashSet<>();
16+
ListNode node = head;
17+
while (node != null) {
18+
19+
if (set.contains(node)) {
20+
return node;
21+
}
22+
set.add(node);
23+
node = node.next;
24+
}
25+
return null;
26+
}
27+
28+
29+
}

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

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.chen.algorithm.study.test146;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @author : chen weijie
8+
* @Date: 2019-12-05 22:41
9+
*/
10+
public class Solution {
11+
12+
13+
class LRUCache extends LinkedHashMap<Integer, Integer> {
14+
15+
16+
private int capacity;
17+
18+
public LRUCache(int capacity) {
19+
super(capacity, 0.75F, true);
20+
this.capacity = capacity;
21+
}
22+
23+
public int get(int key) {
24+
return super.getOrDefault(key, -1);
25+
}
26+
27+
public void put(int key, int value) {
28+
super.put(key, value);
29+
}
30+
31+
@Override
32+
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
33+
return size() > capacity;
34+
}
35+
}
36+
37+
38+
}

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

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
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 Solution2 {
12+
13+
class Node {
14+
15+
public int key, val;
16+
17+
public Node next, prev;
18+
19+
public Node(int key, int value) {
20+
this.key = key;
21+
this.val = value;
22+
}
23+
}
24+
25+
26+
class DoubleList {
27+
28+
private Node head, tail;
29+
30+
private int size;
31+
32+
33+
public DoubleList() {
34+
35+
this.size = 0;
36+
head = new Node(0, 0);
37+
tail = new Node(0, 0);
38+
head.next = tail;
39+
tail.prev = head;
40+
}
41+
42+
public void addFirst(Node x) {
43+
44+
x.next = head.next;
45+
x.prev = head;
46+
head.next.prev = x;
47+
head.next = x;
48+
size++;
49+
}
50+
51+
// 删除链表中的 x 节点（x 一定存在）
52+
public void remove(Node x) {
53+
x.prev.next = x.next;
54+
x.next.prev = x.prev;
55+
size--;
56+
}
57+
58+
59+
// 删除链表中最后一个节点，并返回该节点
60+
public Node removeLast() {
61+
if (tail.prev == head)
62+
return null;
63+
Node last = tail.prev;
64+
remove(last);
65+
return last;
66+
}
67+
68+
// 返回链表长度
69+
public int size() {
70+
return size;
71+
}
72+
}
73+
74+
75+
class LRUCache {
76+
77+
78+
private HashMap<Integer, Node> map;
79+
80+
private DoubleList cache;
81+
82+
private int cap;
83+
84+
public LRUCache(int capacity) {
85+
86+
this.cap = capacity;
87+
map = new HashMap<>();
88+
cache = new DoubleList();
89+
}
90+
91+
public int get(int key) {
92+
93+
if (!map.containsKey(key))
94+
return -1;
95+
int val = map.get(key).val;
96+
// 利用 put 方法把该数据提前
97+
put(key, val);
98+
return val;
99+
}
100+
101+
public void put(int key, int value) {
102+
103+
Node x = new Node(key, value);
104+
105+
if (map.containsKey(key)) {
106+
// 删除旧的节点，新的插到头部
107+
cache.remove(map.get(key));
108+
cache.addFirst(x);
109+
map.put(key, x);
110+
} else {
111+
if (cap == cache.size) {
112+
Node last = cache.removeLast();
113+
map.remove(last.key);
114+
}
115+
cache.addFirst(x);
116+
map.put(key, x);
117+
}
118+
}
119+
120+
121+
}
122+
123+
124+
}

0 commit comments

Comments
 (0)