目录：自己复习用，非题解，请谅解！今天内写完, 【更新中】 周一写 周二写

1. 单链表

LeetCode版：

## 定义链表结构：
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 输出该链表l1的元素
while l1:
        print(l1.val)
        l1 = l1.next

#将一个list的数据存为链表：
#复制代码
def list2listnode(num):
    head = ListNode(num[0])
    result = head
    for i in range(1,len(num)):
        head.next = ListNode(num[i])
        head = head.next
    return result

# ①head存储链表头 ② val[] 存节点的值 ③next[]存节点的next指针 ④cur存位置,即index当前到了哪个节点
##          初始化单链表          ##
val = [0]* N
next = [0]* N
head = -1
####################################
##          主体                  ##
def add_to_head(x): # 将x添加到头节点
    global cur
    global head
    val[cur] = x
    next[cur] = head
    head = cur
    cur += 1

def add(k, x): # 在第k个输入的数后面插入一个数x
    global cur
    val[cur] = x
    next[cur] = next[k]
    next[k] = cur
    cur += 1

def delete(k): # 删除第k个输入的数后面的数
    global head
    if k == 0: 
        head = next[head]
        return
    next[k] = next[next[k]]

2. 双链表

##          初始化双链表          ##
    e = [0]*(M+10)    # M表示最多的节点数
    r = [0]*(M+10)
    l = [0]*(M+10)
    r[0] = 1
    l[1] = 0
    idx = 2
##          主体                  ##
def add(k, x):
    # 在第k个插入的数后面添加数x
    global idx
    e[idx] = x
    r[idx] = r[k]
    l[idx] = k
    l[r[k]] = idx    # ！！！注意：后两句的顺序不能颠倒，否则r[k] = idx，l[r[k]] = l[idx] = idx，出错
    r[k] = idx
    idx += 1 

def delete(k):
    # 删除第k个插入的数后面的数
    r[l[k]] = r[k]
    l[r[k]] = l[k]

3. 栈

1) 函数式 2) 数组模拟

##          初始化栈          ##
N_inputList = []
stack = []
#输入
for i in range(N):
    N_inputList.append(input()) #题意所需操作存进来(即input输入数据)
##          主体              ##
def push(x):
    global stack
    stack.append(x)

def pop():
    global stack
    del stack[-1]

def empty():
    global stack
    if stack == []:
        print('YES')
    else:
        print('NO')

def query():
    print(stack[-1])
#题意 ans
def ans(string):
    global stack
    string = list(string.split())
    classes, x = string[0], string[-1]
    if classes == 'push':
        push(x)
    if classes == 'pop':
        pop()
    if classes == 'empty':
        empty()
    if classes == 'query':
        query()
##          输出          ##
for i in N_inputList:
    ans(i)

②

##          初始化栈          ## h, idx= [0]*100010, 0

def push(x):
    global idx
    h[idx] = x
    idx += 1

def pop():
    global idx
    idx -= 1

def empty():
    global idx
    if idx == 0:
        return 'YES'
    return 'NO'

def query():
    global idx
    return h[idx-1]

4. 队列

##          同数组模拟          ##
##          初始化队列          ##
q = [0]*(M+10)
hh = 0 # 即head
tt = -1 # 即tail
##          主体                ##
for _ in range(M):
    in_li = input().split()
    op = in_li[0]
    if op=="push":    # 队尾插入元素
        x = int(in_li[1])
        tt += 1
        q[tt] = x
    elif op=="pop":    # 弹出队头元素
        hh+=1
    elif op=="empty":
        if tt>=hh: print("NO")
        else: print("YES")
    else:
        print(q[hh])

# 函数式 数组模拟
def push(x):
    global idx
    h[idx] = x
    idx += 1

def pop():
    global head
    head += 1

def empty():
    global idx,head
    if idx == head:
        return 'YES'
    return 'NO'

def query():
    global head
    return h[head]

def operate(s):
    op = s.split()[0]
    if op == 'push':
        x = s.split()[1]
        push(x)
    elif op == 'pop':
        pop()
    elif op == 'empty':
        print(empty())
    elif op == 'query':
        print( query())

5. 单调栈 循环队列

待更新

6. 单调栈

##            初始化单调栈            ##
stk = [0]*(n+10)
tt = 0
##            主体                    ##
for i in range(n):
    while tt and nums[i]<=stk[tt]:     # 如果要查找元素nums[i]比栈顶元素stk[tt]小，则栈顶元素出栈
        tt-=1     
    if tt: print(stk[tt], end=' ')    # 如果栈非空，则输出栈顶元素，否则输出-1
    else: print(-1, end=' ')
    tt+=1
    stk[tt] = nums[i]    # 要查找元素nums[i]入栈

7. 单调队列

##            初始化单调队列            ##
q = [0]*(1000010)    # 注意：q里面存的是数组nums的索引
hh = 0; tt=-1
##            主体                      ##
    # 输出滑动窗口的最小值
for i in range(n):
    while hh<=tt and i-k+1>q[hh]:    # 判断队头是否划出窗口
        hh+=1
    while hh<=tt and nums[q[tt]]>=nums[i]:    # ？？？判断第i个元素是否比队尾元素小，小的话队尾元素出队；！！！出错：当nums[q[tt]]==nums[i]时，队尾元素也要出队
        tt-=1
    tt+=1; q[tt] = i
    if i-k+1>=0:print(nums[q[hh]], end=" ")    # 如果第i个元素的索引超过了窗口大小才输出最小值
print()
hh = 0; tt = -1 #要再初始化一遍，因为输入了多种情况没归“零”的话head tail会乱
    # 输出滑动窗口的最大值
for i in range(n):
    while hh<=tt and i-k+1>q[hh]:    
        hh+=1
    while hh<=tt and nums[q[tt]]<=nums[i]:    # 与输出最小值的唯一区别：这里循环判断条件是<=
        tt-=1
    tt+=1; q[tt] = i
    if i-k+1>=0:print(nums[q[hh]], end=" ")

def max_min(arr, func):
    q = deque()
    for i, v in enumerate(arr, 1):
        while q and q[0][0] <= i - k: q.popleft()
        while q and func(v, q[-1][1]): q.pop()     # v 在前
        q.append((i, v))
        if i >= k: print(q[0][1], end=' ')
    print("")

max_min(arr, lambda x, y:x < y)     # 单调递增队列
max_min(arr, lambda x, y:x > y)     # 单调递减队列

8. KMP 字符串

##KMP是什么，做什么用的

KMP全称为Knuth Morris Pratt算法，三个单词分别是三个作者的名字。KMP是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串的位置(比如在“hello,world”主串中查找“world”模式串的位置)。

#### KMP算法的高效体现在哪

高效性是通过和其他字符串搜索算法对比得到的，在这里拿BF(Brute Force)算法做一下对比。BF算法是一种最朴素的暴力搜索算法。它的思想是在主串的[0, n-m]区间内依次截取长度为m的子串，看子串是否和模式串一样(n是主串的长度，m是子串的长度)。

通过这个例子可以看出，每次滑动的位数是j-k，滑动位数和主串无关，仅通过模式串就可以求出。在KMP算法中通过next数组来存储当两个字符不相等时模式串应该移动的位数。

如何KMP算法的next数组

再次明确next数组的含义 : next数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标。 $next[i] = j $表示下标以$i-j$为起点，i为终点的后缀和下标以0为起点，j为终点的前缀相等，且此字符串的长度最长。用符号表示为p[0~j] == p[i-j~i]。

def kmp(s, p, m, n):
    ne = [0 for _ in range(len(p))]
    # 1. 生成next数组 def get_next
    j = 0
    for i in range(2, n+1):    # 因为ne[1]默认等于0，所以循环从2开始
#         print(i, j)
        while j and p[i]!=p[j+1]:
            j = ne[j]
        if p[i]==p[j+1]:
            j+=1
        ne[i] = j

    # 2. 字符串匹配
    j = 0
    for i in range(1, m+1):
#         print(i, j)
        while j and s[i]!=p[j+1]:
            j = ne[j]
        if s[i]==p[j+1]:
            j+=1
        if j==n:
            print(i-n, end=" ")   
            j = ne[j]

KMP主要分两步：
1. 求next数组、匹配字符串。所以先把匹配字符串讲一下。
2. s串和 p串都是从1开始的。i 从1开始，j 从0开始，每次s[i] 和p[j + 1]比较

求next数组的思路和实现代码

next数组的求法是通过模板串自己与自己进行匹配操作得出来的

9. Trie树

#多叉树版
import sys
class TreeNode():
    def __init__(self):
        self.next = [None]*26
        self.val = 0

table = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}
root = TreeNode()
def Add(root,string):
    # string分配完则截止
    if len(string) == 0:
        root.val+=1
        return
    if root.next[table[string[0]]] == None:
        # 需要创建
        root.next[table[string[0]]] = TreeNode()
        Add(root.next[table[string[0]]],string[1:])
    else:
        # 已经存在
        Add(root.next[table[string[0]]],string[1:])

def Query(root,string):
    if len(string) == 0:
        return root.val
    if root.next[table[string[0]]] == None:
        return 0
    else:
        return Query(root.next[table[string[0]]],string[1:])

或字典dict版

root = {}

def insert(string):
    p = root
    for char in string:
        p = p.setdefault(char, {})
    p['*'] = p.get('*', 0) + 1


def query(string):
    p = root
    for char in string:
        if char not in p: return 0
        p = p[char]
    if '*' in p: return p['*']
    return 0

10. 并查集UnionFind (disjoint sets)

"""
基本思想:
    每个集合用一棵树表示，树根的编号就是集合的编号；每个节点存它的父节点，即p[x]存的是x的父节点
"""
def find(x):
    if p[x] != x:
        p[x] = find(p[x])    # 路径压缩优化，将多有子节点都指向祖宗节点；!!!注意:这里find函数的参数不能是x，因为这样递归前后函数的参数不变，会陷入死循环
    return p[x]    # ！！！出错：最后要返回的是x的父节点，而不是x

if __name__=="__main__":
    n, m = map(int, input().split())
    p = [i for i in range(n+1)]    # p[x]表示x的父节点,初始化时x的父节点是他自己

    while m:
        op, a, b = input().split()

        a = int(a)
        b = int(b)
        if op=="M":
            p[find(a)] = find(b)    # 合并集合：将节点a的祖宗节点的父节点设置为b的祖宗节点
        else:
            if find(a)==find(b):    # 判断是否在一个集合中：节点a的祖宗节点与节点b的祖宗节点相同
                print("Yes")
            else:
                print("No")
        m-=1

11. 堆 Heap

#一维数组存一个数，左儿子是2x 右儿子2x+1 root 从 1 开始比较方便 要是从0 开始 2x = 0 冲突
# 插入一个数：         heap[++size] = x;  up(size)
# 求集合当中最小的值：  heap[1]
# 删除最小值：         heap[1] = heap[size]; size--; down[1]
# 删除任意一个元素     heap[k] = heap[size]; size --; down[k]; up[k]; (只会执行一个)
# 修改任意一个元素     heap[k] = x; down[k]; up[k];

def down(u):
    t = u
    if u * 2 <= size and h[u * 2] < h[t] : t = u * 2
    if u * 2 + 1 <= size and h[u * 2 + 1] < h[t] : t = u * 2 + 1
    if u != t:
        h[u],h[t] = h[t],h[u]
        down(t)

if __name__ == '__main__':

    n,m = map(int,input().split())
    h = list(map(int,input().split()))
    h.insert(0, 0)

    size = n

    for i in range((n+1)//2,0,-1):
        down(i)

    for i in range(m):
        print(h[1],end = ' ')
        h[1] = h[size]
        size-=1
        down(1)

#Python中堆的实现是靠优先队列PriorityQueue
from queue import PriorityQueue

que = PriorityQueue()
m, n = map(int, input().split())
arr = list( map(int, input().split()) )
for val in arr:
    que.put(val)

for i in range(n):
    print(que.get(), end=' ')
print()

12. 哈希表 HashMap

Python中Dictionary

def insert(x):
    """头插法，将x查到单链表h[k]的头部"""
    global idx
    k = x%100003    # 100003是大于等于100000的第一个素数
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx+=1


def find(x):
    """查找x是否被插入"""
    k = x%100003
    i = h[k]
    while i!=-1:
        if e[i]==x:
            return True
        i = ne[i]
    return False


if __name__=="__main__":
    n = int(input().strip())

    # 初始化邻接表
    N = 100010    # 表示链表最多的节点数
    h = [-1]*(N)
    e = [0]*(N)
    ne = [0]*(N)
    idx = 0

    for i in range(n):
        op, x = input().split()
        x = int(x)
        if op=="I":
            insert(x)
        else:
            flag = find(x)
            if flag: print("Yes")
            else: print("No")

后续补充库函数

ref:

Actor丶
戈好雨
xanxus1111
roon2300