[数据结构与算法]python算法模板第二部分(1)（单链表、双链表、模拟栈、模拟队列、单调栈、单调队列、KMP算法）

注：本文是在学习了acwing的算法基础课后撰写，主要用于记录python版本算法的模板。其中部分参考了acwing众多大佬的题解。

1.单链表

思想：
本部分将使用数组实现链表操作，而不使用指针。数组e用于存放链表值(val)，数组ne用于存放下一个链表节点(next)，index用于存下标。

常见操作：
1.向链表头插入一个数
2.删除第 k 个节点后的节点
3.在第k个节点后插入一个节点
注：第 k 个节点并不是指当前链表的第 k 个数，而是第k个插入链表的数（即下标为k的数）

模板：

N = 100010
head = -1       # 头结点下标
e = [0] * N     # 用于存值
ne = [0] * N    # 用于存next
idx = 0         # 用于记录下标（第几个插入的数）

def addToHead(x):
    global head, e, ne, idx
    e[idx] = x
    ne[idx] = head
    head = idx
    idx += 1

def remove(k):
    global e, ne
    ne[k] = ne[ne[k]]
    
def insert(k, x):
    global e, ne, idx
    e[idx] = x
    ne[idx] = ne[k]
    ne[k] = idx
    idx += 1

2.双链表

思想：
本部分将使用数组实现链表操作，而不使用指针。数组e用于存放链表值(val)，数组l用于存放左侧节点(left)，数组r用于存放右侧节点(right)，index用于存下标。

常见操作：
1.在第k个节点后面添加数x
2.删除第k个节点后面的数
注：第 k 个节点并不是指当前链表的第 k 个数，而是第k个插入链表的数（即下标为k的数）

模板：

# 初始化双链表
e = [0]*(M+10)    	# M表示最多的节点数，存放数值
r = [0]*(M+10)		# 存放左侧节点
l = [0]*(M+10)		# 存放右侧节点
r[0] = 1			# 初始化两个节点，互相连通，做哨兵的角色
l[1] = 0
idx = 2				# 后续添加的节点下标从2开始

# 在第k个插入的数后面添加数x
def add(k, x):
    global idx
    e[idx] = x
    r[idx] = r[k]
    l[idx] = k
    l[r[k]] = idx    # 后两句的顺序不能颠倒
    r[k] = idx
    idx += 1 
    
# 删除第k个插入的数后面的数
def delete(k):
    r[l[k]] = r[k]
    l[r[k]] = l[k]

3.模拟栈

思想：
数组模拟栈。通过一个数组加一个指针即可。

常见操作：
1.push x – 向栈顶插入一个数 x；
2.pop – 从栈顶弹出一个数；
3.empty – 判断栈是否为空；
4.query – 查询栈顶元素。

模板：

# 初始化栈
stack = [0] * N
tt = 0

# push
def push(x):
    stack[tt] = s[1]
    tt += 1
    
# pop
def pop():
    tt -= 1
    
# query
def query():
	tmp == tt - 1
	print(stack[tmp])

# empty
def empty():
	print("YES") if tt <= 0 else print("NO")

4.模拟队列

思想：
数组模拟队列。通过一个数组加两个指针（head、tail）即可。

常见操作：
1.push x – 向队尾插入一个数 x；
2.pop – 从队头弹出一个数；
3.empty – 判断队列是否为空；
4.query – 查询队头元素。

模板：

N = 100010
queue = [0] * N
head, tail = 0, 0

def push(x):
    queue[tail] = x
    tail += 1
    
def pop():
    head += 1
    
def empty():
    print("NO") if head < tail else print("YES")
    
def query():
    print(queue[head])

5.单调栈

思想：
单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

常见题型：
通常是一维数组，要寻找任一元素右边（左边）第一个比自己大（小）的元素，且要求 O(n) 的时间复杂度

模板：

n = int(input())
nums = list(map(int, input().split()))
stack = []

# 单调栈
for i in range(n):
    while stack and stack[-1] >= nums[i]:		# 单调栈核心语句
        stack.pop()
    if len(stack) != 0:
        print(stack[-1], end = " ")
    else:
        print(-1, end = " ")
    stack.append(nums[i])

6.单调队列

思想：
类似单调栈

常见题型：
滑动窗口

模板：

from collections import deque
# nums为给定序列 n为序列长度 k为窗口长度

# 记录滑动窗口最大值	
def maxSlidingWindow():
    max_deque = deque()
    res = []
    for i, j in zip(range(1-k, n+1-k), range(n)):	# 使用zip函数可使i,j同时更新
        # nums[i-1]此时已经不再窗口中了，如果它还在deque中的话将其删除
        if i > 0 and max_deque[0] == nums[i-1]:
            max_deque.popleft()
        # 维护单调性
        while max_deque and max_deque[-1] < nums[j]:	#若要记录最小值，这里改成>即可
            max_deque.pop()
        # 最右侧元素入队
        max_deque.append(nums[j])
        # 将每个窗口的最大值放入res，i<0时有效窗口还未形成
        if i >= 0:
            res.append(max_deque[0])

7.KMP算法

思想：
快速从主串中找出想要的子串。

步骤：
1.写子串前缀表prefix_table
2.找公共最长前后缀
例：T中找P
T：abaacababcac
P：ababc
-1
0 a
0 ab
1 aba
2 abab
???ababc
得prefix_table：
ababc
-10012

模板：

    # ne
    i, j = 2, 0
    while(i <= n):
        while(j and p[i] != p[j + 1]): j = ne[j]
        if(p[i] == p[j + 1]): j += 1
        ne[i] = j
        i += 1

    i, j = 1, 0
    while(i <= m):
        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]
        i += 1