Skip to content

Commit af0506b

Browse files
author
chenweijie
committed
frequency
1 parent d533dc6 commit af0506b

File tree

12 files changed

+270
-2
lines changed

12 files changed

+270
-2
lines changed

‎src/main/java/com/chen/algorithm/study/test208/Trie.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -77,8 +77,7 @@ public TrieNode() {
7777
}
7878

7979
TrieNode(char c) {
80-
TrieNode node = new TrieNode();
81-
node.val = c;
80+
this.val = c;
8281
}
8382
}
8483

‎src/main/java/com/chen/algorithm/znn/array/offer/test57/Solution.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.chen.algorithm.znn.array.offer.test57;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/11/08 15:25
6+
* @Description: 剑指 Offer 57 - II. 和为s的连续正数序列
7+
*/
8+
public class Solution {
9+
}

‎src/main/java/com/chen/algorithm/znn/array/test11/Solution.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.chen.algorithm.znn.array.test11;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/11/08 15:25
6+
* @Description: 盛最多水的容器
7+
*/
8+
public class Solution {
9+
}

‎src/main/java/com/chen/algorithm/znn/array/test287/Solution.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.chen.algorithm.znn.array.test287;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/11/08 15:25
6+
* @Description: 寻找重复数
7+
*/
8+
public class Solution {
9+
}

‎src/main/java/com/chen/algorithm/znn/frequency/test146/LRUCache.java‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package com.chen.algorithm.znn.frequency.test146;
2+
3+
4+
import java.util.HashMap;
5+
import java.util.Map;
6+
7+
/**
8+
* https://leetcode-cn.com/problems/lru-cache/
9+
*
10+
* @Auther: zhunn
11+
* @Date: 2020/11/08 14:47
12+
* @Description: LRU缓存机制：哈希表 + 双向链表
13+
*/
14+
public class LRUCache {
15+
16+
class CacheNode {
17+
private int key;
18+
private int val;
19+
private CacheNode pre;
20+
private CacheNode next;
21+
22+
public CacheNode() {
23+
}
24+
25+
public CacheNode(int key, int val) {
26+
this.key = key;
27+
this.val = val;
28+
}
29+
}
30+
31+
private Map<Integer, CacheNode> cache = new HashMap<>();
32+
private int size;
33+
private int capacity;
34+
private CacheNode head, tail;
35+
36+
public LRUCache(int capacity) {
37+
this.capacity = capacity;
38+
this.size = 0;
39+
this.head = new CacheNode();
40+
this.tail = new CacheNode();
41+
head.next = tail;
42+
tail.pre = head;
43+
}
44+
45+
public int get(int key) {
46+
CacheNode node = cache.get(key);
47+
if (node == null) {
48+
return -1;
49+
}
50+
moveToHead(node);
51+
return node.val;
52+
}
53+
54+
public void put(int key, int value) {
55+
CacheNode node = cache.get(key);
56+
if (node != null) {
57+
node.val = value;
58+
moveToHead(node);
59+
return;
60+
}
61+
62+
CacheNode newNode = new CacheNode(key, value);
63+
cache.put(key, newNode);
64+
addToHead(newNode);
65+
size++;
66+
67+
if (size > capacity) {
68+
CacheNode tail = removeTail();
69+
cache.remove(tail.key);
70+
size--;
71+
}
72+
}
73+
74+
public void addToHead(CacheNode node) {
75+
node.pre = head;
76+
node.next = head.next;
77+
head.next.pre = node;
78+
head.next = node;
79+
}
80+
81+
public void removeNode(CacheNode node) {
82+
node.pre.next = node.next;
83+
node.next.pre = node.pre;
84+
}
85+
86+
public void moveToHead(CacheNode node) {
87+
removeNode(node);
88+
addToHead(node);
89+
}
90+
91+
public CacheNode removeTail() {
92+
CacheNode res = tail.pre;
93+
removeNode(res);
94+
return res;
95+
}
96+
}

‎src/main/java/com/chen/algorithm/znn/frequency/test146/LRUCacheMap.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.chen.algorithm.znn.frequency.test146;
2+
3+
import java.util.LinkedHashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @Auther: zhunn
8+
* @Date: 2020/11/08 14:47
9+
* @Description: LRU缓存机制：1-使用java的LinkedHashMap
10+
*/
11+
public class LRUCacheMap extends LinkedHashMap<Integer, Integer> {
12+
13+
private int capacity;
14+
15+
public LRUCacheMap(int capacity) {
16+
super(capacity, 0.75f, true);
17+
this.capacity = capacity;
18+
}
19+
20+
public int get(int key) {
21+
return super.getOrDefault(key, -1);
22+
}
23+
24+
public void put(int key, int value) {
25+
super.put(key, value);
26+
}
27+
28+
@Override
29+
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
30+
return size() > capacity;
31+
}
32+
}

‎src/main/java/com/chen/algorithm/znn/frequency/test208/Trie.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.chen.algorithm.znn.frequency.test208;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shu-ju-jie-gou-she-ji-zhi-shi-xian-trie-qian-zhui-/
5+
*
6+
* @Auther: zhunn
7+
* @Date: 2020/11/08 14:46
8+
* @Description: 实现 Trie (前缀树)
9+
*/
10+
public class Trie {
11+
12+
public Trie root;
13+
public char val;
14+
public Trie[] children = new Trie[26];
15+
public boolean isWord;
16+
17+
public Trie() {
18+
root = new Trie(' ');
19+
}
20+
21+
public Trie(char val) {
22+
this.val = val;
23+
}
24+
25+
/**
26+
* Inserts a word into the trie.
27+
*/
28+
public void insert(String word) {
29+
Trie ws = root;
30+
for (int i = 0; i < word.length(); i++) {
31+
char c = word.charAt(i);
32+
if (ws.children[c - 'a'] == null) {
33+
ws.children[c - 'a'] = new Trie(c);
34+
}
35+
ws = ws.children[c - 'a'];
36+
}
37+
ws.isWord = true;
38+
}
39+
40+
/**
41+
* Returns if the word is in the trie.
42+
*/
43+
public boolean search(String word) {
44+
Trie ws = root;
45+
for (int i = 0; i < word.length(); i++) {
46+
char c = word.charAt(i);
47+
if (ws.children[c - 'a'] == null) {
48+
return false;
49+
}
50+
ws = ws.children[c - 'a'];
51+
}
52+
return ws.isWord;
53+
}
54+
55+
/**
56+
* Returns if there is any word in the trie that starts with the given prefix.
57+
*/
58+
public boolean startsWith(String prefix) {
59+
Trie ws = root;
60+
for (int i = 0; i < prefix.length(); i++) {
61+
char c = prefix.charAt(i);
62+
if (ws.children[c - 'a'] == null) {
63+
return false;
64+
}
65+
ws = ws.children[c - 'a'];
66+
}
67+
return true;
68+
}
69+
}

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.chen.algorithm.znn.heap.test347;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/11/08 15:25
6+
* @Description: 前 K 个高频元素
7+
*/
8+
public class Solution {
9+
}

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.chen.algorithm.znn.stack.test496;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/11/08 15:25
6+
* @Description: 下一个更大元素
7+
*/
8+
public class Solution {
9+
}

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.chen.algorithm.znn.stack.test674;
2+
3+
/**
4+
* @Auther: zhunn
5+
* @Date: 2020/11/08 15:25
6+
* @Description: 最长连续递增序列
7+
*/
8+
public class Solution {
9+
}

0 commit comments

Comments
 (0)