蓝桥杯必备算法模板（python）：

• 前缀和模板
• 差分模板
• 二分
• 双指针
• 位运算
• 最大公约数和最小公倍数模板
• 判断质数和埃氏筛法模板
• 唯一分解定理和质因数分解关系和模板
• 快速幂
• 并查集
• 区间合并
• 回溯算法模板：
• DFS(深度优先搜索)
• BFS(广度优先搜索)
• 最小生成树
• 拓扑排序
• floyd算法
• 狄克斯特拉算法
• 动态规划(01背包)：

🔥只有把基础的算法模板熟练掌握，才有可能解决考场上变化的题目，本篇文章最适合了解这些算法的同学进行全盘复习，不断背诵使用。当然如果是小白，大部分算法模板我都放了视频链接，相信你们一定能看懂的，蓝桥杯冲冲冲！文章最下方还有篇文章链接哦！！！🚀🚀🚀

前缀和模板

一维前缀和：

应用场景：设计到区间求和

前缀和：就是原数组中前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常用操作和模块
点个关注吧，问问题秒回的那种！💖