蓝桥杯必备算法模板（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的位置初始化为0for 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  #导入数据结构dequeq=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常用操作和模块
点个关注吧，问问题秒回的那种！?