引言

主要讲解在 oj 的面试背景下，如何处理数据结构。

文章目录

引言1. 单链表——数组模拟单链表2. 双向链表3. Trie 字典树4. 堆（小顶堆）1. 子函数 down2. 子函数 up3. 操作： 5. 并查集1. 子函数 new2. 子函数 findfather3. 子函数 union例题包括：食物链 2. 双链表 3. 栈与队列（先入后入与先入先出） 4. 单调栈，单调队列 5. trie 字典树 6. 并查集 7. 堆

1. 单链表——数组模拟单链表

因为动态链表比较复杂，每次需要重建的时间成本比较大。因此在题目中一般采用数组模拟静态链表的操作。 定义：e[index]表示编号为index的节点的数值，ne[index]表示编号为index的节点的子节点，每次最后还需要index++表示生成新的数组位置。

e = [0]*100000 ne = [0]*100000 index = 0 head = -1 N = int(input()) def add_to_head(x): # 头插链表，链表的尾部是-1 # 注意设置全局变量 global e, index, head, ne e[index] = x ne[index] = head head = index index += 1 def insert(k, x): # 插入到第k个后面 global e, index,ne e[index] = x ne[index] = ne[k] ne[k] = index index += 1 def delete(k): # 删除第K个插入的数后面的数 global ne ne[k] = ne[ne[k]] for i in range(N): # 注意这里的读入方法 s, *p = input().split() if s == 'H': # int这个函数只能操作字符型 add_to_head(int(p[0])) elif s == 'I': k, x = map(int, p) insert(k-1, x) elif s == 'D': k = int(p[0]) if k == 0: head = ne[head] else: delete(k-1) while head != -1: print(e[head], end=' ') head = ne[head]

2. 双向链表

N = int(input()) e = [0]*100000 r = [0]*100000 l = [0]*100000 index = 2 head = 0 tail = 1 # 构建一个队首一个队尾 r[head] = tail l[tail] = head def insert(k, x): # 插入k在后侧 global index, e, l, r e[index] = x r[index] = r[k] l[index] = k l[r[k]] = index r[k] = index index += 1 def delete(k): # 删除第k个数后面的数字 global r, l l[r[k]] = l[k] r[l[k]] = r[k] for i in range(N): s, *p = input().split() if s == 'L': insert(0, int(p[0])) elif s == 'R': insert(l[1], int(p[0])) elif s == 'IL': k, x = map(int, p) insert(l[k+1],x) elif s == 'IR': k, x = map(int, p) insert(k+1, x) elif s == 'D': delete(int(p[0])+1) head = r[head] while head != 1: print(e[head], end=' ') head = r[head]

3. Trie 字典树

Trie字典树

class Trie: def __init__(self): """ Initialize your data structure here. """ self.dic = {} def insert(self, word: str) -> None: """ Inserts a word into the trie. """ ## 一定要另外调用字典 dic = self.dic for i in word: if not i in dic: dic[i] = {} dic = dic[i] dic['end'] = True def search(self, word: str) -> bool: """ Returns if the word is in the trie. """ dic = self.dic for i in word: if not i in dic: return False dic = dic[i] if 'end' in dic: return True return False def startsWith(self, prefix: str) -> bool: """ Returns if there is any word in the trie that starts with the given prefix. """ dic = self.dic for i in prefix: if not i in dic: return False dic = dic[i] return True

类似题目：前缀统计，最大异或对

4. 堆（小顶堆）

需要支持的操作：

插入一个数求集合中的最小值删除最小值删除任意一个元素修改任意一个元素

之前写过的手撕堆

我发现还是把这个存储堆的序列从1开始编号方便，这样左节点是2i，右节点是2i+1；查询父节点时i//2。

1. 子函数 down

变大了堆顶的元素，下移。每次和两个子节点中小的那个交换位置，直到两个子节点都大于等于。

def down(x): # 时间复杂度是logn child = 2*x while child <= size: if child+1 <= size and heap[child+1]<heap[child]: child += 1 if heap[child] < heap[x]: heap[x], heap[child] = heap[child], heap[x] x = child child *= 2 else: break

2. 子函数 up

减小了某个叶节点，上移。每次和父节点进行比较，如果父节点大于自己，交换。

3. 操作：

插入：堆尾插入，依次上浮。size+= 1, heap[size] = c, up(c)求最小值：返回堆首，注意我们这里堆从1开始索引的。heap[1]删除最小值：把整个堆的最后一个元素覆盖堆顶元素，然后再下沉。heap[1] = heap[size], hize--, down(1)删除任意元素：heap[k] = heap[size], size--, down(k), up(k)修改某元素：heap[k] = num, down(k), up(k)建堆：$O(n)$的时间复杂度，保证了每个儿子都是堆了。for i in range(n//2, 0, -1) down(i)

5. 并查集

专门的并查集的讲解参考，可以参考 。这里在总结一下并查集的子函数结构。

1. 子函数 new

生成新的并查集编号，一般我习惯用字典。

def __init__(self): self.fathernode = {} self.val = {} self.size = {} # 初始化节点 def new_UF(self, node): # 当节点已经存在时 if node in self.fathernode: return self.fathernode[node] = node self.val[node] = 1.0 # 数值 self.size[node] = 1 # 规模

2. 子函数 findfather

寻找每个节点的父节点，这里可以用递归也可以用迭代。递归会更简单一些。

# -------------------------------递归------------------------------ # 查询父节点 同时进行值的更新 # 使用递归 同时对路径进行压缩 将每个节点连接到与父节点的关系 def getfather(self, node): if self.fathernode[node] == node: return node # 递归得到父节点 fa = self.getfather(self.fathernode[node]) # 递归的更新当前节点得值 前父节点关系值 * 更新后得父节点值 self.val[node] = self.val[self.fathernode[node]] * self.val[node] # 将节点的父节点更新为最父节点 self.fathernode[node] = fa return fa # -----------------------------迭代-------------------------------- def findfather(self, node): while self.fathernode[node] != node: self.fathernode[node] = self.fathernode[self.fathernode[node]] node = self.fathernode[node] return node

3. 子函数 union

实现合并，一般方法就是合并父节点。

def union(self, node1, node2): node1fa = self.findfather(node1) node2fa = self.findfather(node2) if node1fa == node2fa: return self.count += 1 size_node1 = self.nodesize[node1fa] size_node2 = self.nodesize[node2fa] if size_node1>size_node2: self.fathernode[node2fa] = node1fa self.nodesize[node1fa] += size_node2 else: self.fathernode[node1fa] = node2fa self.nodesize[node2fa] += size_node1

例题包括：食物链

思路是使用一个并查集，然后我们维护了每个节点到根节点的距离。保证维护并查集中，每个节点到根节点的距离，定义距离为0，1，2，3 ， 1吃0， 2吃1， 0吃2且与1一类。

## 利用并查集解决问题 # 维护并查集中，每个节点到根节点的距离，定义距离为0，1，2，3 # 1吃0， 2吃1， 0吃2且与1一类 N, M = map(int, input().split()) p = {} d = {} def new(x): p[x] = x d[x] = 0 def find(x): if x == p[x]: return x t = find(p[x]) # 先对px进行完路径压缩，这样可以维护好d[px] d[x] += d[p[x]] # d[px]表示了p[x]到根节点的距离，在加上x到px的距离 p[x] = t return p[x] def union(x,y,t): fx = find(x) fy = find(y) p[fx] = fy # 把x连接到y上 add = (d[y]-d[x]+t)# 因为(d[x]+?-d[y]-1)%3 == 0,所以?=d[y]+1-d[x],这里的问号是d[fx]距离d[fy]的距离。 d[fx] = add ans = 0 for i in range(M): a,x,y = map(int,input().split()) if x>N or y>N: ans += 1 #print(x,y) else: if x not in p: new(x) if y not in p: new(y) fx = find(x) fy = find(y) if a == 1: if fx == fy: if (d[x] - d[y])%3 != 0: ans += 1 # 同类矛盾 else: union(x,y, 0) elif a == 2: if fx == fy: if (d[x]-d[y]-1)%3 != 0: # 因为x吃y，所以x比y大1的距离 ans += 1 else: union(x, y, 1) print(ans)