算法结构

一些算法结构.

字典树

tire 树也叫字典树,是一种 N 叉树,是一种特殊的前缀树结构。

前缀树是N叉树的一种特殊形式。通常来说,一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串(前缀)。每一个节点会有多个子节点,通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串,以及通往该子节点路径上所有的字符组成的。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class TrieNode(object):
def __init__(self, value=None, count=0, parent=None, tag = False):
# 值
self.value = value
# 频数统计
self.count = count
# 父结点
self.parent = parent
# 子节点,{value:TrieNode}
self.children = {}
# 是否是word结尾字符的标志符
self.tag = tag

class Trie(object):
def __init__(self):
self.root = TrieNode()

def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curNode = self.root
for c in word:
if c not in curNode.children:
child = TrieNode(value=c, count=1, parent=curNode)
curNode.children[c] = child
curNode = child
else:
curNode = curNode.children[c]
curNode.count += 1

curNode.tag = True

def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curNode = self.root
for c in word:
if not c in curNode.children:
return False
curNode = curNode.children[c]
if not curNode.tag:
return False

return True

def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
curNode = self.root
for c in prefix:
if not c in curNode.children:
return False
curNode = curNode.children[c]
return True

def delete(self, word):
"""
delete a word in the trie.
:type word: str
:rtype: void
"""
if self.search(word):
curNode = self.root
for c in word:
curNode.children[c].count -= 1
if curNode.children[c].count == 0:
curNode.children.pop(c)
break
else:
curNode = curNode.children[c]
return True
return False


test = Trie()
test.insert('abcd')
test.insert('abf')
test.insert('eh')

print(test.search('abf'))
print(test.search('abc'))
print(test.startsWith('ab'))
print(test.startsWith('ac'))
print(test.delete('abf'))
print(test.search('abf'))
test.insert('abf')
print(test.search('abf'))

结果

1
2
3
4
5
6
7
True
False
True
False
True
False
True

并查集(UnionFind)

并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets UnionFind)的合并及查询问题。常常在使用中以森林来表示。 进行快速规整。主要是用在无向图的连通性的实例场景,例如大部分的岛屿或者部分棋盘问题。

参考1
参考2

在LeetCode上对应的题目有

200.岛屿数量
128.最长连续序列
200.被围绕的区域

  1. 初始化一个并查集 initUnionFind
    初始化并查集,一般是将每个元素作为一个单独的集合,对于下面的示例就是对应的元素父节点就是自己
  2. 合并两个不相交集合 union
    两个元素,分别找到(find)他们的根节点,然后将其中一个元素的根节点的父亲指向另外的一个元素的根节点
  3. 查找某个元素的根节点 find
    查找一个元素的根节点,parent--->parent--->parent.....
    那么问题来了,查找元素根节点途径的元素过多,那么就有一个优化的问题———-路径压缩,直接将该元素的父亲指向根节点或者祖先
  4. 判断两个元素是否属于同一个集合 isConnected
    判断两个元素是否属于同一个集合,就是分别找到他们的根节点,然后判断两个根节点是否相等.

简单实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
class UnionFind:
def __init__(self, n):
self.ancestor = list(range(n))
self.count = n #并查集中集合的数目
def union(self, index1: int, index2: int):
self.ancestor[self.find(index1)] = self.find(index2)
self.count -= 1
def is_connected(self, index1, index2):
return self.find(index1) == self.find(index2)
def find(self, index: int) -> int:
if self.ancestor[index] != index:
self.ancestor[index] = self.find(self.ancestor[index])
return self.ancestor[index]

带rank等级的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class UnionFind:
def __init__(self, n):
self.count = n #并查集中集合的数目
self.parent = [i for i in range(n)]
self.rank = [1 for _ in range(n)]

def get_count(self):
return self.count

def find(self, p):
while p != self.parent[p]:
self.parent[p] = self.parent[self.parent[p]]
p = self.parent[p]
return p

def is_connected(self, p, q):
return self.find(p) == self.find(q)

def union(self, p, q):
p_root = self.find(p)
q_root = self.find(q)
if p_root == q_root:
return

if self.rank[p_root] > self.rank[q_root]:
self.parent[q_root] = p_root
elif self.rank[p_root] < self.rank[q_root]:
self.parent[p_root] = q_root
else:
self.parent[q_root] = p_root
self.rank[p_root] += 1

self.count -= 1