Skip to content

Commit 595b69c

Browse files
dunwudunwu
committed
update codes
1 parent daa1066 commit 595b69c

5 files changed

Lines changed: 183 additions & 6 deletions

File tree

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/search/SearchStrategy.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -16,15 +16,15 @@ public class SearchStrategy {
1616
private Search search;
1717

1818
public SearchStrategy(Search search) {
19-
this.search = search;
19+
search = search;
2020
}
2121

2222
public int find(Integer[] list, int key) {
23-
logger.info(this.search.getClass().getSimpleName() + " 查找开始：");
23+
logger.info(search.getClass().getSimpleName() + " 查找开始：");
2424
logger.info("要查找的线性表：{}", ArrayUtil.toString(list));
2525
logger.info("要查找的 key：{}", key);
2626

27-
int index = this.search.find(list, key);
27+
int index = search.find(list, key);
2828
logger.info("{} 的位置是：{}", key, index);
2929
return index;
3030
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/trie/Trie.java‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package io.github.dunwu.algorithm.trie;
2+
3+
import java.util.concurrent.atomic.AtomicInteger;
4+
5+
public class Trie {
6+
7+
private AtomicInteger wordCount = new AtomicInteger(0);
8+
private final TrieNode root = new TrieNode('/'); // 存储无意义字符
9+
10+
// 往 Trie 树中插入一个字符串
11+
public void insert(char[] text) {
12+
TrieNode p = root;
13+
for (int i = 0; i < text.length; ++i) {
14+
int index = text[i] - 'a';
15+
if (p.children[index] == null) {
16+
TrieNode newNode = new TrieNode(text[i]);
17+
p.children[index] = newNode;
18+
} else {
19+
p.children[index].count++;
20+
}
21+
p = p.children[index];
22+
}
23+
wordCount.getAndIncrement();
24+
p.isEnd = true;
25+
}
26+
27+
// 在 Trie 树中查找一个字符串
28+
public boolean find(char[] pattern) {
29+
TrieNode p = root;
30+
for (int i = 0; i < pattern.length; ++i) {
31+
int index = pattern[i] - 'a';
32+
if (p.children[index] == null) {
33+
return false; // 不存在 pattern
34+
}
35+
p = p.children[index];
36+
}
37+
return p.isEnd;
38+
}
39+
40+
public String longest() {
41+
StringBuilder sb = new StringBuilder();
42+
for (int i = 0; i < 26; i++) {
43+
method(root.children[i], sb);
44+
}
45+
return sb.toString();
46+
}
47+
48+
public void method(TrieNode root, StringBuilder sb) {
49+
if (root != null) {
50+
if (root.count == wordCount.get()) {
51+
sb.append(root.data);
52+
if (root.children != null) {
53+
for (int i = 0; i < 26; i++) {
54+
method(root.children[i], sb);
55+
}
56+
}
57+
}
58+
}
59+
}
60+
61+
public class TrieNode {
62+
63+
public int count;
64+
public char data;
65+
public boolean isEnd = false;
66+
public TrieNode[] children = new TrieNode[26];
67+
68+
public TrieNode(char data) {
69+
this.count = 1;
70+
this.data = data;
71+
}
72+
73+
}
74+
75+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/trie/实现Trie_前缀树.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package io.github.dunwu.algorithm.trie;
2+
3+
/**
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @see <a href="https://leetcode-cn.com/problems/implement-trie-prefix-tree/">208. 实现 Trie (前缀树)</a>
6+
* @since 2020-06-15
7+
*/
8+
public class 实现Trie_前缀树 {
9+
10+
public static void main(String[] args) {
11+
实现Trie_前缀树 trie = new 实现Trie_前缀树();
12+
trie.insert("apple");
13+
System.out.println(trie.search("apple")); // 返回 true
14+
System.out.println(trie.search("app")); // 返回 false
15+
System.out.println(trie.startsWith("app")); // 返回 true
16+
trie.insert("app");
17+
System.out.println(trie.search("app")); // 返回 true
18+
}
19+
20+
private TrieNode root;
21+
22+
public 实现Trie_前缀树() {
23+
root = new TrieNode('/');
24+
}
25+
26+
public void insert(String word) {
27+
TrieNode p = root;
28+
for (char c : word.toCharArray()) {
29+
int index = c - 'a';
30+
if (p.children[index] == null) {
31+
TrieNode node = new TrieNode(c);
32+
p.children[index] = node;
33+
}
34+
p = p.children[index];
35+
}
36+
p.isEnd = true;
37+
}
38+
39+
public boolean search(String word) {
40+
TrieNode p = root;
41+
for (char c : word.toCharArray()) {
42+
int index = c - 'a';
43+
if (p.children[index] == null) {
44+
return false;
45+
}
46+
p = p.children[index];
47+
}
48+
return p.isEnd;
49+
}
50+
51+
public boolean startsWith(String prefix) {
52+
TrieNode p = root;
53+
for (char c : prefix.toCharArray()) {
54+
int index = c - 'a';
55+
if (p.children[index] == null) {
56+
return false;
57+
}
58+
p = p.children[index];
59+
}
60+
return true;
61+
}
62+
63+
public static class TrieNode {
64+
65+
public boolean isEnd;
66+
public char data;
67+
public TrieNode[] children;
68+
69+
public TrieNode(char data) {
70+
this.data = data;
71+
this.children = new TrieNode[26];
72+
}
73+
74+
}
75+
76+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/trie/最长公共前缀.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package io.github.dunwu.algorithm.trie;
2+
3+
/**
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @since 2020-06-15
6+
*/
7+
public class 最长公共前缀 {
8+
9+
public static void main(String[] args) {
10+
longestCommonPrefix("flower", "flow", "flight");
11+
}
12+
13+
public static String longestCommonPrefix(String... strs) {
14+
Trie trie = new Trie();
15+
for (String s : strs) {
16+
trie.insert(s.toCharArray());
17+
}
18+
return trie.longest();
19+
}
20+
21+
}

‎docs/linear-list-search.md‎

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -76,9 +76,7 @@ ASL = (N + N-1 + ... + 2 + 1) / N = (N+1) / 2
7676

7777
## 二分查找
7878

79-
**要点**
80-
81-
二分查找又称**折半查找**，它是一种效率较高的查找方法。
79+
> **二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0**。
8280
8381
**存储结构**
8482

@@ -124,6 +122,13 @@ public int binarySearch(int[] list, int length, int key) {
124122

125123
由此可知，二分查找的**平均查找长度**实际上就是树的高度**O(log<sub>2</sub>N)**。
126124

125+
**二分查找的局限性**
126+
127+
- 二分查找依赖的是顺序表结构，简单点说就是数组
128+
- 二分查找针对的是有序数据
129+
- 数据量太小不适合二分查找
130+
- 数据量太大也不适合二分查找
131+
127132
## 分块查找
128133

129134
**要点**

0 commit comments

Comments
 (0)