2025-03-24  /2025/03/24/PYTHON/ 99+   17 分钟   2.6 k0次访问

PYTHON 算法学习

14天 PY 成神计划

时间 题目链接 完成情况
3.29 比赛链接：https://www.nowcoder.com/acm/contest/106557 百分之50
3.30 比赛链接：https://www.nowcoder.com/acm/contest/106558
3.31 比赛链接：https://www.nowcoder.com/acm/contest/106559
4.1 比赛链接：https://www.nowcoder.com/acm/contest/106560
4.2 比赛链接：https://www.nowcoder.com/acm/contest/106562 优先队列 + 并查集
4.3 比赛链接：https://www.nowcoder.com/acm/contest/106563 搜索 + 剪枝
4.4 比赛链接：https://www.nowcoder.com/acm/contest/106564 动态规划1
4.5 比赛链接：https://www.nowcoder.com/acm/contest/106565 动态规划2
4.6 比赛链接：https://www.nowcoder.com/acm/contest/106566 图论 + 最短路
4.7 比赛链接：https://www.nowcoder.com/acm/contest/106567 数学
4.8 比赛链接：https://www.nowcoder.com/acm/contest/106568 线段树 + 树状数组
4.9 比赛链接：https://www.nowcoder.com/acm/contest/106569 LCA + RMQ
4.10
4.11
4.12 蓝桥杯

知识点完成情况

待办
数学
LCA + RMQ树上问题

PY 笔记

递归

先递归的后算，递归的特性是 自下而上

fold title:递归
1
2
3
4
5
def fun(x):
   if exam():
       return 
   return fun(min_x)

DFS 和 BFS 的实现

DFS 是属于 递归迭代 的算法过程， BFS 是属于 层次扩展（队列完成）

因为有时候DFS的时间复杂度是 2 的n次方，所以如果层次足够少的话，便可以使用BFS来实现

PY中的DP 缓存

fold title:DP缓存
1
2
dp = {}

PY 内置函数

fold title:内置函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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(队列)

fold title:队列基本操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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")



排序算法

基础排序

fold title:结构体排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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))


基数排序（基于每一位的大小排序）

归并排序

fold title:归并算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

归并排序 求 逆序队

fold title:逆序队
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
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)

快排

  • 理解 第一种快排的排序方法
fold title:C++版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

fold title:PY版本
1
2
3
4
5
6
7
8
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)

建树

fold title:vector 建树
1
2
3
4
5
6
7
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

fold title:bisect
1
2
3
4
5
import bisect
bisect.bisect_left() # 靠左 >= 严格大于等于
bisect.bisect_right() # 靠右 > 严格大于
# 从 lo -> hi
 x = bisect.bisect_right(a, need, lo=1, hi=i)

三分

三分用来求函数极值

一般 有 先增后减，先减后增 的特性

三分模版：

1
2
3
4
5
6
7
8
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 这个列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)


优先队列 自定义排序结构

fold title:自定义排序结构
1
2
a = []
heapq.heappush(a, (-item[0], item[1], item[2]))

优先队列相关问题

  • 中位数问题：

    一个小根堆，一个大根队来维护中位数

  • 前 k 大问题

    一个 长度为 k 小根堆来维护

Python 的输入处理

fold title:快读
1
2
import sys
input = sys.stdin.readline
  1. 单个读取：n = int(input())
  2. 一行读取：a = list(map(int, input().split()))
  3. 多行读取 每行一个元素：nums = [int(input()) for _ in range(n)]
  4. 多行读取 每行多个元素：nums = [list(map(int, input().split())) for _ in range(n)]

Python 的输出处理

  • 将字符串连接:
    • ‘m’.join(list)：将列表中的字符串用m连接起来
  • 将列表中的元素先转化为 字符串再输出：
    • ‘m’.join(map(str, list))
      • map的意思是将list中的每一个元素都转化为字符
  • 格式化输出：
    • print(f “{x : .2f}”) 保留两位小数
    • print(f”{name} got {score} points.”)
    • print(x, end = ‘ ‘)

多组测试

fold title:多组测试
1
2
3
4
5
6
while True:
    try:            
    except EOFError:  # 输入结束时退出
        break
    except ValueError:  # 无效输入时退出
        break

字典的操作

  • 基础map
fold title:ma
1
2
3
mp = {}
# 防止访问没有存在的字典，如果不存在 就返回 k
mp.get(a[r], k)
  • 更方便的map
fold title:MAP
1
2
3
from collections import defaultdict
# 可以避免访问不存在的字典出现报错
mp = defaultdict(int)
  • MAP去重离散化
fold title:离散化
1
2
3
4
5
6
7
# 排序 + 去重
sorted(set(arr))
# enumerate 返回的是 (index, vavlue)
# 现在需要的是 key : index
# 所以需要 将 i, x 反转
mp = {x : i for i , x in enumerate(sorted(set(arr)))}

栈和队列

在 PY 中， 栈和队列都可以使用 deque(双端队列)来实现

栈

fold title:栈
1
2
3
4
5
6
7
8
9
10
11
from collections import deque
stack = deque()
stack.append(x)

# 访问栈头
top = stack[-1]
top = stack.pop()

# 清空栈
stack.clear()

队列

fold title:队列
1
2
3
4
5
6
7
8
9
10
11
from collections import deque
q = deque()

# 加入
q.append(x)
q.appendleft(x)
q.insert(l, item)

# 出队
left = q.popleft()

01 分数规划

最大化 (∑a[i]) / (∑b[i])

  • 二分 + 贪心
    设 X = (∑a[i]) / (∑b[i]) -> ∑a[i] - X * ∑b[i] = 0
    二分查找 X，看 X 对于 这个式子的影响是过大还是过小。
fold title:浮点二分
1
2
3
4
5
6
7
8
9
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 背包）

1
2
3
4
5
6
7
8
# 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次方

1
2
3
4
5
6
7
8
9
10
11
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])

1
2
3
4
5
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

数论

埃式筛

1
2
3
4
5
6
7
8
9
10
11
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


拆分因子

1
2
3
4
5
6
7
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)

因子预处理

1
2
3
4
5
6
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 fac

Python 解决字符串分割问题

巧妙的使用 split(‘char’)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

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
# 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]



字典树

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
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] -= 1

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

PYTHON 算法学习

http://example.com/2025/03/24/PYTHON/

作者

Jiely

发布于

2025-03-24

更新于

2025-04-15

许可协议

# 相关文章
  1.算法之美
  2.ACM集训题
  3.alogrithm
  4.老算法笔记
评论

:D 一言句子获取中...

×