::: warning OVER 学习结束！可能以后都不会用PYTHON写算法题目了，因为PYTHON的一些算法语法基础不牢固导致一道题看了2个小时！ :::
知识点完成情况
| 待办 | ||
|---|---|---|
| 数学 | ||
| LCA + RMQ树上问题 |
PY 笔记
递归
先递归的后算，递归的特性是 自下而上
python
def fun(x):
if exam():
return
return fun(min_x)
DFS 和 BFS 的实现
DFS 是属于 递归迭代 的算法过程， BFS 是属于 层次扩展（队列完成）
因为有时候DFS的时间复杂度是 2 的n次方，所以如果层次足够少的话，便可以使用BFS来实现
PY中的DP 缓存
python
dp = {}
PY 内置函数
python
1. 快速幂
pow(a,b,mod)
pow(a,b)
2. gcd（最大公约数）
import math
math.gcd(a,b)
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
3. 找满足值
next(i for i in range(n - 1) if not fa[i])Deque(队列)
python
from collections import deque
origin = int(input())
q = deque([origin]) # 需要列表存入
x1, x2 = map(int, input().split())
q.append(x1)
q.appendleft(x2)
x = q.popleft()
y = q.pop()
print(q[0],q[-1],x,y,len(q))
if not q:
print("YES")
排序算法
基础排序
python
nums.sort(key=())
class Node:
def __init__(self, a, b,c):
self.a = a
self.b = b
self.c = c
def __repr__(self):
return f'({self.a}, {self.b}, {self.c})'
t = int(input())
nodes = []
for _ in range(t):
a, b, c = map(int, input().split())
nodes.append(Node(a,b,c))
nodes = sorted(nodes, key = lambda x : (x.a, -x.b,x.c))
基数排序（基于每一位的大小排序）
归并排序
python
def guibing(arr):
if len(arr) == 1:
return arr
mid = (len(arr)) // 1
left = guibing(arr[:mid])
right = guibing(arr[mid:])
return merge(left, right)
def merge(left ,right):
ans = []
i = j = 0
while(i < len(left) and j < len(right)):
if(left[i] < right[j]):
ans.append(left[i])
i += 1
else:
ans.appemd(right[j])
j += 1
ans.extend(left[i:])
ans.extend(right[j:])
return ans
归并排序 求 逆序队
python
count = 0
def merge(left, right):
global count
ans = []
i = j = 0
while i < len(left) and j < len(right):
if(left[i] <= right[j]): # 一定要 =
ans.append(left[i])
i += 1
else:
ans.append(right[j])
count += (len(left) - i)
j += 1
ans.extend(left[i:])
ans.extend(right[j:])
return ans
def f(arr):
if len(arr) == 1:
return arr
mid = len(arr) // 2
left = f(arr[:mid])
right = f(arr[mid:])
return merge(left, right)
快排
- 理解 第一种快排的排序方法
python
def quick_sort(l, r,arr):
if l >= r:
return;
i ,j = l, r
x = arr[l]
while i < j:
while i < j and arr[j] >= x:
j -= 1
while i < j and arr[i] <= x:
i += 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[l], arr[i] = arr[i], arr[l]
quick_sort(l, i - 1, arr)
quick_sort(i + 1, r, arr)
python
def quick_sort1(arr):
if len(arr) <= 1:
return arr
povit = arr[0]
left = [x for x in arr[1:] if x <= povit]
right = [x for x in arr[1:] if x > povit]
return quick_sort1(left) + [povit] + quick_sort1(right)建树
python
1. 有权
dj = [[] for _ in range(n + 1)]
dj[a].append((b,w))
2. 无权
dj[a].append(b)
二分查找
C++
- lower_bound() 查找可插入元素的最小位置
- upper_bound() 查找可插入元素的最大位置
- binary_bound() 查找元素是否存在
PY
python
import bisect
bisect.bisect_left() # 靠左 >= 严格大于等于
bisect.bisect_right() # 靠右 > 严格大于
# 从 lo -> hi
x = bisect.bisect_right(a, need, lo=1, hi=i)三分
三分用来求函数极值
一般 有 先增后减，先减后增 的特性
三分模版:
python
while l < r:
mid1 = l + (r - l) // 3
mid2 = r - (r - l) // 3
if f(mid1) > f(mid2):
r = mid2 - 1
else:
l = mid1 + 1
print(f(l))- 常考三分嵌套问题
分治常见题目
解决最近曼哈顿距离
优先队列 heapq
heapq是 默认为 小根堆 需要用大根堆的话可以 可以用 值 * -1来存储
当 a 初始化 为heapq后, 优先队列的长度 和 是否为空的判断都是 判断 a 这个列表
python
import heapq
a = []
# 插入
heapq.heappush(a, item)
# 弹出
heapq.heappop(a)
# 判断是否为空 或者 长度 以 a 为判断
len(a)
if not a
# 如果要将 list(a) 直接变成 优先队列
heapq.heapify(a)
# 取 前 n 大 用队列存
heapq.nlargest(n, a)
# 取 钱前 n 小 用队列存
heapq.nsmallest(n, a)
优先队列 自定义排序结构
python
a = []
heapq.heappush(a, (-item[0], item[1], item[2]))优先队列相关问题
-
中位数问题:
一个小根堆，一个大根队来维护中位数
-
前 k 大问题
一个 长度为 k 小根堆来维护
Python 的输入处理
python
import sys
input = sys.stdin.readline- 单个读取 = int(input())
- 一行读取 = list(map(int, input().split()))
- 多行读取 每行一个元素 = [int(input()) for _ in range(n)]
- 多行读取 每行多个元素 = [list(map(int, input().split())) for _ in range(n)]
Python 的输出处理
- 将字符串连接:
- ‘m’.join(list):将列表中的字符串用m连接起来
- 将列表中的元素先转化为 字符串再输出:
- 'm'.join(map(str, list))
- map的意思是将list中的每一个元素都转化为字符
- 'm'.join(map(str, list))
- 格式化输出:
- print(f "{x : .2f}") 保留两位小数
- print(f"{name} got {score} points.")
- print(x, end = ' ')
多组测试
python
while True:
try:
except EOFError: # 输入结束时退出
break
except ValueError: # 无效输入时退出
break字典的操作
- 基础map
python
mp = {}
# 防止访问没有存在的字典，如果不存在 就返回 k
mp.get(a[r], k)- 更方便的map
python
from collections import defaultdict
# 可以避免访问不存在的字典出现报错
mp = defaultdict(int)- MAP去重离散化
python
# 排序 + 去重
sorted(set(arr))
# enumerate 返回的是 (index, vavlue)
# 现在需要的是 key : index
# 所以需要 将 i, x 反转
mp = {x : i for i , x in enumerate(sorted(set(arr)))}
栈和队列
在 PY 中， 栈和队列都可以使用 deque(双端队列)来实现
栈
python
from collections import deque
stack = deque()
stack.append(x)
# 访问栈头
top = stack[-1]
top = stack.pop()
# 清空栈
stack.clear()
队列
python
from collections import deque
q = deque()
# 加入
q.append(x)
q.appendleft(x)
q.insert(l, item)
# 出队
left = q.popleft()
01 分数规划
- 二分 + 贪心 设 X = (∑a[i]) / (∑b[i]) -> ∑a[i] - X * ∑b[i] = 0 二分查找 X，看 X 对于 这个式子的影响是过大还是过小。
python
l = 0
r = 1e6
eps = 1e-6
while (r - l) > eps:
mid = (r + l) / 2
if exam(mid):
l = mid
else:
r = mid动态规划
一定是 从最优 到 最优
计算当前节点时，统计需要的历史信息（dp的存储）
01 背包 / 完全背包
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
一个是 价值 从小到大（完全背包） 一个是 价值 从大到小（01 背包）
python
# 01 背包
for i in range(1, n+1):
for j in range(C, w[i]-1, -1):
f[j] = max(f[j], f[j - w[i]] + v[i])
# 完全背包
for i in range(1, n+1):
for j in range(C, w[i]-1, -1):
f[j] = max(f[j], f[j - w[i]] + v[i])多重背包
问题:每一个物品有 选择次数限制 s[i]
使用二进制优化 转化成01背包
将 s[i] 使用二进制进行拆分 (k _ w, k _ v) k是 2 的 n次方
python
new = []
for i in range(n):
w, v, s = W[i], V[i], S[i]
k = 1
while k < s:
new.append((w * k, v * k))
s -= k
k <<= 1
if s > 0:
new.append((w * s, v * s))
# 转化成新的 01 背包分组背包
问题:分成 n 组，每一组 选 一个 的最大价值
dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + v[i])
python
for group in groups:
for j in range(V,-1,-1):
for w,v in group:
if j >= w:
f[j] = max(f[j],f[j - w] + v)有依赖背包
树型DP
区间DP
数论
埃式筛
python
prime = []
is_prime = [True] * (n + 1)
for i in range(2,n):
if if_prime[i]:
prime.append(i)
for j in range(i * i, n + 1, i):
is_prime[j] = False
return prime
拆分因子
python
ans = set()
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
ans.add(i)
ans.add(n // i)
return sorted(ans)因子预处理
python
fac = [[] for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(i, n + 1, i):
fac[j].append(i)
return facPython 解决字符串分割问题
巧妙的使用 split('char')
python
s = input().strip()
terms = s.split('+')
ans = 0
for fa in terms:
s1 = fa.split('*')
temp = 1
for fac in s1:
if fac:
temp *= int(fac)
ans += temp
字符串
KMP
python
# NEXT[I] 表示 前 i - 1 个元素的 最长前后缀匹配长度
next = [0] * len(s2)
def get_next(s2):
n = len(s2)
next[0] = -1
next[1] = 0
i, cn = 2,0 # cn 表示 i - 1 的next值
while i < n:
if s2[i - 1] == s2[cn]:
next[i++] = ++cn
elif cn > 0:
cn = next[cn]
else:
next[i++] = 0
def kmp(s1, s2):
n, m = len(s1),len(s2)
x, y = 0, 0
get_next(s2)
while x < n and y < m:
if s1[x] == s2[y]:
x += 1
y += 1
elif y == 0:
x += 1
else:
y = next[y]
字典树
python
cnt = 1
n, s # n 表示 层, s 表示 种类
# 第一层什么不都存储，相当于空字符
tree = [[0]*s for i in range(n)]
# pass 表示 每一个前缀的 访问次数
pass = [0] * N
# end 表示 每一个字符串的结尾 访问次数
def insert(word):
cur = 1
pass[cur] += 1
for x in word:
path = x - 'a'
if tree[cur][path] == 0:
tree[cur][path] = ++cnt
cur = tree[cur][path]
pass[cur] += 1
end[cur] += 1
def prenum(pre):
cur = 1
for x in pre:
path = x - 'a'
if tree[cur][path] == 0:
return 0
cur = tree[cur][path]
return pass[cur]
def delete(word):
if prenum(word) > 0:
cur = 1
for x in word:
path = x - 'a'
pass[tree[cur][path]] -= 1
if pass[tree[cur][path]] == 0:
tree[cur][path] = 0
return;
cur = tree[cur][path]
end[cur] -= 1Dijkstra
python
import heapq
def dj(n, g, start):
dist = [float('inf')] * n
dist[start] = 0
heap = [(0,start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(heap,(dist[v],v))
return dist