蓝桥杯必备算法模板(python蓝桥杯):
只有把基础的算法模板熟练掌握,才有可能解决考场上变化的题目,本篇文章最适合了解这些算法的同学进行全盘复习,不断背诵使用。当然如果是小白,大部分算法模板我都放了视频链接,相信你们一定能看懂的,蓝桥杯冲冲冲!文章最下方还有篇文章链接哦!!!
前缀和模板
一维前缀和:
应用场景:设计到区间求和
前缀和:就是原数组中前i个数之和,就是高中数列的前n项和,只不过不是等差数列、等比数列。
前缀和优点:可以将for循环以O(n)的时间复杂度求前缀和了可以降到O(1)复杂度。简直是超级加速器。
如何得出前缀和:只需要知道第 i 项和前 i - 1 项和的关系。S[i] = S[i - 1] + a[i]
如何利用前缀和求区间和:很简单的,就一个公式,区间l,r的前缀和为s[r] - s[l - 1]。
前缀和模板(一维):
a=[0]+list(map(int,input().split())) #维护开销,下标0的位置初始化为0
for i in range(1,n+1):
s[i]=s[i-1]+a[i]
print(s[r]-s[l-1])
''' 注意:给前缀和数组赋值时,需要从1开始,而不是0。为什么呢?当 i 等于0时,S[0]=S[-1] + a[0]。这样就会越界访问了,所以要从1开始,并且令S[0] = 0 说明: n个数,区间左端点l,区间右端点r, 权值列表a,前缀和列表s 测试样例: n 1 2 3 a= [0, 8, 5, 6] s=[0, 7, 13, 19] '''
二维前缀和:
如何得出二维前缀和:S[i, j] = 第i行j列格子左上部分所有元素的和 :S[i][j]=S[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1];
如何利用前缀和求区间和:以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
前缀和模板(二维):
s=[[0]*(m+1)] #m为数据的宽度
a=[[0]+list(map(int,input().split())) for i in range(n)]
s.extend(a) #实现s第0行全为0,第0列为0,因为i,j都是从1开始的
for i in range(1,n+1):
for j in range(1,m+1):
#二维前缀和,第i行j列格子左上部分所有元素的和
S[i][j]=S[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1]
print(S[x2,y2]-S[x1-1,y2]-S[x2,y1-1]+ S[x1-1,y1-1])
差分模板
应用场景:给定一个区间[l,r],把A数组里面这些区间全部加上一个C,只需要在B数组修改两个数就可以了这两个数是:B[ l ] +C,B[ r + 1 ] - C
原理:B[ l ] + C会导致,从前缀和数组A[ l ]开始,每一个前缀和数组都加上C(因为al及以后的数组元素求和时会加上bl,而bl又加上了C)。
差分:有一个原始数列a1 、a2、a3 …an,构造一个新数列b1、b2…bn,使得ai = b1 + b2 +… + bi,使得ai是数列b的前缀和,b是a的差分,是前缀和的逆运算 。
差分模板:
#1.构建差分数组
for i in range(len(B)-1,0,-1):
B[i]-=B[i-1]
#2.转换加减(区间加减→端点加减)
B[l-1]+=v
B[r]-=v
#3.前缀相加(前缀和公式)
for i in range(1,n):
B[i]+=B[i-1]
二分
二分:就是一分为二。就是在有序序列里面,通过不断地二分,进而缩小解的范围直到1个元素,从而更快地寻找满足条件的解。
二分条件:如果可以找到某种性质,使得整个区间一分为二,其中一半区间满足条件,另一半区间不满足条件;二分就可以寻找性质的边界。
整数二分主要有两种情况:第一种情况是把区间分为[l,mid] 和[mid + 1,r];第二种是把区间分为[l,mid - 1] 和[mid,r]**;这两种去分取决于mid属于左区间还是右区间。
上来默认使用第一种,等写出代码来的时候看看mid属于左边还是右边。注意都是闭区间。
二分模板:
#check函数是核心
def check(x):
#假设x为答案
#题目一般有有个约束条件
#如果通过某种手段使得在x的条件下存在符合约束条件的解
#那么就是可行解
#区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用,把中间点放在左半边,不管三七二十一先用这个,做题过程中再修改
def bsearch_1(l, r):
while (l < r):
mid = l + r >> 1 #取中间值
if (check(mid)) : #判断是否满足某种性质
r = mid; #更新区间
else :
l = mid +1
return l
#区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用,把中间点放在左半边(比如左边是合法的,右边是不合法的,此时mid属于合法的那一边)
def bsearch_2(l, r):
while (l < r):
mid = l + r + 1 >> 1 #取中间值
if (check(mid)) : #判断是否满足某种性质
l = mid; #更新区间
else :
r = mid - 1
return l
以前我以为只有升序无重复元素的序列才可以二分,其实不是,具体看y总的讲解吧:二分
双指针
双指针:双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作,都使用双指针法。 双指针算法通过设置两个指针不断进行单向移动**来解决问题的方法。
形式:两个指针分别指向不同的序列;两个指针指向同一个序列。比如:快速排序的划分过程。
实现:本来是双层for循环,O(n²)的时间复杂度。通过双指针算法可以优化到O(n)的时间复杂度。那是如何优化的时间复杂度呢?其实是当一个指针满足条件后才会单向移动,没有指针的回溯,而每次都会有指针的移动。简单说就是有个快指针可以不停的移动,有个慢指针需要符合条件后才能移动
双指针模板:
#模板:i快指针,j慢指针
for i in range(n):
j=0
while j < i and check(j): #当j指针满足一一定条件后才会移动
j+=1;
# 每道题的具体逻辑
位运算
介绍:这个操作是为了求 整数 x (十进制)的 第 k 位数是0 / 1(二进制)
原理:1、先把第k位移到最后一位,x >> k,用位移运算
2、看个位是几,x & 1(位运算&,只有两个1&时,才会返回1;否则返回0)
求n的第k位数字: n >> k & 1
介绍:lowbit(x)函数,返回x的最后一位1(二进制下的)
原理:x = 1010(二进制),lowbit(x) = 10(二进制) = 2(十进制)
返回n的最后一位1:lowbit(n) = n & -n
最大公约数和最小公倍数模板
两者关系:若a,b>0 那么a*b=gcd(a,b)*lcm(a,b)
gcd模板:
def gcd(a,b):
while b:
a,b=b,a%b
return a
lmc模板:
def lcm(a,b):
s=a*b
while b:
a,b=b,a%b
return s//a
#因为到最后a,b的值都不是原来的了,需要一开始用s存a*b
这两个板子我相信大家都记得滚瓜烂熟吧。
判断质数和埃氏筛法模板
案例:给定整数n,请问n以内有多少个素数?n<=10^6
你可能会轻蔑的笑了,感觉能自己分分钟秒杀。但是请别急,下面介绍的埃氏算法,能让你更快解决。
思想:首先,将2~n范围内的所有数都写下来,存入一张线性表里(用一维数组实现)。其中最小的数字2是素数。将表中2的倍数都划去,当然也包括其本身。之后表中剩余的最小数字是3。它显然也是素数。那么继续将所有3的倍数划去。同理,依次类推,每次表中剩下的最小数字m都是素数,然后将表中所有的m的倍数划去。如此反复操作,便能筛出n以内的所有素数。
判断质数模板(这个大家一定都会):
#由于一个数n的因子是成对出现的 故只需要枚举到int(n**0.5)
def judge(x):
for i in range(2,int(x**0.5)+1):
if x%i==0:
return False
return True
埃氏筛法模板:
maxn=10000#这个范围自己依据要查找数据范围内的质数设定
is_prime=[True for i in range(maxn+1)]
prime=[] #记录质数
for i in range(2,maxn):
if is_prime[i]:
prime.append(i)
j=i
while j<=maxn:
is_prime[j]=False
j+=i
唯一分解定理和质因数分解关系和模板
唯一分解定理:又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。如:n>1,n=(2^a)*(3^b)*(5^c)…*(x^y),**其中y>=0,x为质数,简单来说就是一个数一定可以*分解*为多个质数的连乘积。
推论:n的约数个数=(a+1)(b+1)…(y+1),(求出数n的因子个数)
质因数分解模板
#该模板函数把分解出来的质数存到列表里并输出
#怎么加工利用看自己需要
def f(x):
i=2
l=[]
while i<=x:
if x%i==0:
l.append(i)
x//=i
else:
i+=1
return l
#例如:12=3⋅2⋅2,这样就完全分解为质数的乘积了
快速幂
介绍:当我们做一些高次幂(数特别大如10的18次方)的计算时,就不能直接进行暴力的计算。这时候如果我们直接进行暴力的计算,时间复杂度为O ( n ) O(n)O(n),那么肯定会超时。
思想:(a * b) % p = (a % p * b % p) % p
快速幂模板:
def fast_power(a,b,p):
abs=1
a%=p
while b:
if b%2==1: #等价b&1
ans=(ans*a)%p
a=(a*a)%p
b//=2
return ans
补充:(a + b) % p = (a % p + b % p) % p ,(a - b) % p = (a % p - b % p) % p 。
如果想去看看思路证明去看看这个视频讲解吧:快速幂算法
并查集
介绍:并查集是一种树型的数据结构,常见操作有两种
1、 将两个集合合并
2、 询问两个元素是否在一个集合当中
并查集进行这两种操作的时间复杂度近乎O(1),而其他数据结构可能完成不了
并查集模板:
#并查集模板
def find(x): #返回x的祖宗节点
if p[x]!=x:
p[x]=find(p[x])
return p[x]
def union(x,y): #合并x,y为同一家族
if find(x)!=find(y):
p[find(x)]=find(y)
# p[N]存储每个点的祖宗节点,索引为当前节点,当前节点的值代表当前节点的祖宗
p=[i for i in range(1,N+1)] #初始化,假定节点编号是1~n
不懂?不懂咱就上视频:并查集
区间合并
介绍:大部分都是用贪心的策略去解决,不是按照左端点排序,就是按照右端点排序,或者按照左右端点双关键字排序。这里我们按照左端点进行排序的,本质其实还是判断重叠区间问题。
实现:先排序,让所有的相邻区间尽可能的重叠在一起,按左边界进行判断。
区间合并模板:
n=int(input()) #多少个初始区间
intervals=[list(map(int,input().split())) for _ in range(n)] #区间集合,intervals = [[1,3],[2,6],[8,10],[15,18]]
def merge(intervals):
if len(intervals) == 0: return intervals
intervals.sort(key=lambda x: x[0]) #按左区间排序
result = [] #记录合并后的区间,操作直接在result中进行
result.append(intervals[0]) #初始化,把第一个区间放入result数组
for i in range(1, len(intervals)):
last = result[-1] #取出result最后一个元素
if last[1] >= intervals[i][0]: #重叠
result[-1] = [last[0], max(last[1], intervals[i][1])] #注意取最大值,因为无法确定两个右边界谁大。
else:
result.append(intervals[i]) #不重叠直接加入result数组
return result
重温一下我卡哥:合并区间视频
回溯算法模板:
介绍:回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,比如下面的深搜也是回溯的一种。
思想:溯法解决的问题都可以抽象为树形结构,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历
一般可以解决如下几种问题:
1.组合问题:N个数里面按一定规则找出k个数的集合
2.切割问题:一个字符串按一定规则有几种切割方式
3.子集问题:一个N个数的集合里有多少符合条件的子集
4.排列问题:N个数按一定规则全排列,有几种排列方式
5.棋盘问题:N皇后,解数独等等
回溯模板:
def backtracking(参数):
if (终止条件) :
存放结果
return
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) :
处理节点
backtracking(路径,选择列表) // 递归
回溯,撤销处理结果
DFS(深度优先搜索)
介绍:从图中一个未访问的顶点 V 开始,沿着一条路一直走到底,然后从这条路尽头的节点回退到上一个节点,再从另一条路开始走到底…,不断递归重复此过程,直到所有的顶点都遍历完成
特点:不撞南墙不回头,空间复杂度是n,不具有最短路效应,因为如果数据量一旦过大,递归树会越来越大最终导致爆栈。对于DFS而言,只要有解即可适合一些思路比较奇怪,对空间要求高的题目。
DFS模板:
def dfs(参数):
if (越界不合法情况):
return
if (终点边界,输出答案):
return
for (循环枚举所有方案):
if(未被标记): # if (越界不合法情况): 也可以放这一块写
(标记)
dfs(下一层)
(还原标记) #回溯
这个视频直接看起来:深度优先算法
BFS(广度优先搜索)
介绍:广度优先遍历,指的是从图的一个未遍历的节点出发,先遍历这个节点的相邻节点,再依次遍历每个相邻节点的相邻节点。放到树的遍历中而言,就是层序遍历(levelorder)
实现:因为需要保存相邻节点,所以我们需要使用到队列(queue)这个数据结构,由于其具有先入先出的特性,就可以遍历完一层又遍历下一层。
特点:从根节点开始向下一层一层的搜索,具有最短路的特点,适用于需要找最短路的题目
BFS模板:
#M:map地图 G:go走过路径 q=deque():双向队列 q.popleft() 头节点从左边出队
from collections import deque #导入数据结构deque
q=deque([(0,0)]) #1.化队列,迷宫开始位置坐标(0,0)
n,m=map(int,input().split())
M=[[int(i) for i in input()] for j in range(n)] #模拟地图
G=[['']*m for i in range(n)] #记录到从起点到该点走过路径的方向(根据题意设置)
while q:
x,y=q.popleft()
if x==n-1 and y==m-1: #2.设置结束条件,输出答案
print(len(G[-1][-1]))
print(G[-1][-1])
break
for i,j,k in [(1,0,'D'),(0,-1,'L'),(0,1,'R'),(-1,0,'U')]:#3.下一步路,遍历可以走的四个方向,得到下一个坐标(a,b)。
a,b=x+i,y+j
if 0<=a<n and 0<=b<m and M[a][b]==0: #3.判断合理,判断坐标是否越界,是否之前遍历过。
M[a][b]=1
q.append((a,b))#4.迭代赋值:判断合理就进行标记,然后添加到队列最后,路径表上增加此刻的方向。
G[a][b]=G[x][y]+k
注意:([(0,0)])有三层,先外面套一层deque()函数小括号,然后里面夹一层列表中括号[ ],最后再加一层代表坐标点小括号().
和上面视频是一家子:广度优先算法
最小生成树
树:如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。
最小生成树:一个图中可能存在多条相连的边,我们**一定可以从一个图中挑出一些边生成一棵树。**这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。
应用举例:要在n个城市之间铺设道路,主要目标是要使这 n 个城市的任意两个之间都可以连通,但铺设费用很高,且各个城市之间铺设费用不同,因此另一个目标是要**使铺设总费用最低。*这就需要找到*带权的最小生成树。
最小生成树模板:
#这里用到并查集的知识点
n=int(input())
edge=[]#edge[i]=[a,b,c]代表i这条边连接了a,b,权值为c
ans=0#权值和
edge.sort(key=lambda x:x[2])#按边权升序排序
for x in edge:#遍历所有边
a,b,c=x[0],x[1],x[2]
if find(a)!=find(b) and j<=n-1:#两顶点不连通且当前边数小于n-1
ans+=x[2]#权值累加
union(a,b)
j+=1
print(ans)
拓扑排序
应用场景:有向图,检测环,有向无环图一定有拓扑序列。
1.一件事情必须在另一件事情完成之后才能进行,这种十分强调事件的先后顺序的问题可以使用拓扑排序解决。例如,我们的升学,只有上完小学才上中学,上了中学才能上大学,上了大学才能上研究生等。
2.任何一个有向无环图一定有拓扑序列,因此拓扑序列可以用来检测环
基本思想:
- 从有向图中选一个无前驱(入度为0)的顶点输出;
- 将此顶点和以它为起点的弧删除;
- 重复上述2个步骤直到不存在无前驱的顶点。
- 若此时输出的顶点数小于有向图的顶点数,则说明有向图中存在回路,否则输出的顶点的顺序即为一个拓扑序列。
实现:那么对于代码来说,我们需要运用深搜的思想来执行拓扑排序的操作,1.找到图中入度为0的顶点 压栈 2.处于栈顶的顶点出栈 并加入列表(另外创建的存储结构,用于存储拓扑序列中的元素) 访问该顶点的所有邻居,如果其存在入度为0的邻居,压栈,执行操作2,如果不存在,回溯。
拓扑排序模板:
#准备工作上需要一个字典:用于存放连接关系
def topsort(graph):
#初始化所有点的入度为0
indegrees=dict((i,0) for i in graph.keys())
#传入入度大小
for i in graph.keys():
for j in graph[i]:
indegrees[j]+=1#'a':'cd',代表a指向c和d,那么c和d的入度增加1
#获取入度为0的顶点
stack=[i for i in indegrees.keys() if indegrees[i]==0]
#创建拓扑序列
seq=[]
while stack:#深搜
tmp=stack.pop()#出栈
seq.append(tmp)#加入拓扑序列
for k in graph[tmp]:#遍历邻居,邻居入度-1,邻居入度为0入栈
indegrees[k]-=1
if indegrees[k]==0:
stack.append(k)
if len(seq)==len(graph):
#无环
print(seq)#输出拓扑序列
else:
print('存在环')#当存在环,最终余下的点入度都不为0,Seq个数少于总顶点
#此处会存在一些入度不为0的结点,他们组成环。
graph={
'a':'cd',
'b':'df',
'c':'e',
'd':'efg',
'e':'g',
'f':'g',
'g':''
}
topsort(graph)
#['b', 'a', 'd', 'f', 'c', 'e', 'g']
如果还是不怎么明白,我知道你很急但是你别急。我相信你看完这个视频,你瞬间会通透的:拓扑排序视频
floyd算法
介绍:用来找每个点两两之间的最短距离(多源最短路径),是典型的动态规划。既可以是有向图也可以是无向图,权重可以为负。
缺点:时间复杂度高
优点:比起狄克斯特拉算法,简单地多,代码量少,容易上手
floyd模板:
n=int(input())#这个根据题意设置,表示结点个数
edge=[[float('inf')]*n for i in range(n)]
#初始化所有边权为无穷大
#根据题意更新edge[i][j]
#更新的时候,如果有无向图需要edge[i][j]=edge[j][i]这样设置,否则不用
#三重循环 结束
for k in range(n): #以k为中转站
for i in range(n):
for j in range(n):
edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
如果不是很明白,我相信你看完这个视频会恍然大悟:floyd视频讲解
狄克斯特拉算法
介绍:既可以是无向图也可以有向图,权值必须非负,求某个顶点到其他顶点的最短距离(单源)
缺点:写起来会稍微麻烦一点比起Floyd 东西比较多
优点:跑的挺快的,数据量比较大的时候也能用Python解决
狄克斯特拉算法模板:
n=int(input())#根据题意 n代表结点个数
edge={
}
#edge[i]={x:费用1,y:费用1....} 存结点之间的费用
cost=[]
#cost[i]代表结点i到出发点的最短开销,和edge在循环的过程中赋值,i不能直接到达的点costs[i]=float('inf')
s=set()
#集合s用于存储处理过的结点
def find_node():#find_node函数用于寻找未被处理过的最便宜的结点
node,spend=None,float('inf')
for i in range(n):
if cost[i]<=spend and i not in s:#
node,spend=i,cost[i]
return node
node=find_node
while node:#只要还有结点未被处理
for i in edge[node]:#遍历node的邻居
cost[i]=min(cost[i],cost[node]+edge[node][i]) #cost[node](起点到node的费用)+node到节点的费用,取最小值。
s.add(node)
node=find_node
print(#根据你的需要输出出发点到某个结点i的费用cost[i])
#此外补充一个,如果题还要我们求最短路径上边的个数
#只需外加一个字典pre 每当更新cost[i]时,创建一个键值对
#最后通过终点逆向遍历统计次数即边数 输出即可
来看看这个视频吧:狄克斯特拉视频讲解
动态规划(01背包):
动态规划五部曲:
1.确定dp数组(dp table)以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
代码演示:
def test01():
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
# 初始化: 全为0
dp = [0] * (bag_weight + 1)
# 先遍历物品, 再遍历背包容量
for i in range(len(weight)):
for j in range(bag_weight, weight[i] - 1, -1):
# 递归公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp)
test01()
如果觉得博主的文章还不错的话,请三连支持一下博主哦
如果还想复习一下基础操作看这里:python常用操作和模块
点个关注吧,问问题秒回的那种!
文章评论