距离蓝桥杯58天
学习算法是为了提升我们的思维能力
坚持算法训练不仅可以帮助我们度过笔试的那一关 人生的各项加成也很多
真题训练1（编程题）：完全二叉树的权值>>考察对二叉树深度， 结点， 关系的掌握
首先 我们需要了解完全二叉树的定义：除去最后一层为满二叉树+最后一层结点从左往右排列；满二叉树：除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树
掌握两者的深度计算公式：若已知二叉树有n个结点
完全二叉树:depth=[log(2,n+1)] (向下取整)[这个可以记忆一下]
满二叉树:depth=log(2,n+1)[这个可以直接推导]
最后掌握满二叉树第i层有2^（i-1）个结点 即可解决
因此对于本题 我们可以创建一个列表s s[i]用于储存第i行的总和
已知每行结点的个数 要求每行的总和只需知道每行首尾元素的索引
观察易得每行首元素的索引呈2的等比数列排布 因而尾元素索引可求
故每行总和可求
题目要求最大的权值对应的深度 只需利用index 和max函数
max函数都明白，index函数 指的是序列中首次出现指定元素的索引
故我们先获取max 再利用index 便是最大值相同的情况的最小深度
N=int(input()) import math depth=int(math.log(N,2))+1 s=[0]*depth res=list(map(int,input().strip().split())) for i in range(depth-1): s[i]=sum(res[2**i-1:2**(i+1)-1]) s[depth-1]=sum(res[2**(depth-1)-1:]) print(s.index(max(s))+1) ##math.log(x,y)=m 等价于 y^m=x
真题训练2：迷宫>>考察BFS
图片中的是题目给出的例子，题目的迷宫在这里
问题分析：BFS常用来解决迷宫最短路径问题 原因：C语言对这个的解释（传送门）
并建议去<<算法图解>>第六章一看
对于本道题 BFS采用队列 开始状态（0，0）入队 然后四个方向依次试探
可通过便入队 同时创建父子结点关系（即记录一层父子节点关系）当广度搜索层数增加到最外层出现终点，停止搜索。
本题不仅要求最短路径（实际上没有但应当必须掌握），还要输出路径并且此路径的字典序最小
因此我们需要回溯：由于先前记录了父子结点的层次关系 且迷宫上每移动一步就创建了一层父子关系 从终点回溯到终点 经历了几层父子关系就是路径长度（而且是最短的）
字典序最小：到达终点的路径有很多种，即通过建立不同的父子关系能达到相同的终点，我们要找到其中字典序最小的(D<L<R<U) 简言之，如果我当前处在位置(x,y)，如果上下左右都通（且还没有被访问过），优先走D其次是L再次是R最后是U，就优先建立和下侧的父子关系其次是左侧再次是右侧最后是上侧
maze_str="""01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 01000000001010100011010000101000001010101011001011 00011111000000101000010010100010100000101100000000 11001000110101000010101100011010011010101011110111 00011011010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000""" dirs=[lambda x,y:(x+1,y), lambda x,y:(x,y-1), lambda x,y:(x,y+1), lambda x,y:(x-1,y)]#字典序最小 因此函数排列顺序有要求 D L R U def f(x1,y1,x2,y2):#x是行,y是列 if x2-x1>0: return 'D' elif x2-x1<0: return 'U' elif y2-y1>0: return 'R' else: return 'L' maze=maze_str.split() from queue import Queue#导入队列模板 row,col=len(maze)-1,len(maze[0])-1 start,end=(0,0),(row,col) path=Queue() path.put(start) pre={(0,0):(0,0)} count=0#路径长度 while not path.empty():#不为空就找 如果为空了说明没有路径前往终点 cur=path.get()#出队 if cur==end: p=end s='' while p!=start: s+=f(pre[p][0],pre[p][1],p[0],p[1])#打印路径 p=pre[p]#回溯 count+=1 print(count) print(s[::-1])#由于是回溯，路径需要取反 break else: for dir in dirs: next_cur=dir(cur[0],cur[1]) x,y=next_cur[0],next_cur[1]#创建父子节点关系（前提没访问过+在迷宫内+非障碍物） if next_cur not in pre.keys() and 0<=x<=row and 0<=y<=col and int(maze[x][y])==0 : pre[next_cur]=cur path.put(next_cur) #count=186 #路径DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
DFS模板：（和本题无关，但是可以解决最短路径长和方案种数问题
n,m,t=map(int,input().strip().split()) point=[[0]*(m+1) for i in range(n+1)] sx,sy,fx,fy=map(int,input().strip().split()) #设置障碍物 for k in range(t): tmp=list(map(int,input().strip().split())) point[tmp[0]][tmp[1]]=1 dx=[1,-1,0,0] dy=[0,0,1,-1] def judge(newx,newy): #越界,障碍物或已访问 if newx>n or newx<=0 or newy>m or newy<=0: return False if point[newx][newy]==1: return False return True count=0 min_step=float('inf') def dfs(x,y,step): global count,min_step if x==fx and y==fy: count+=1 min_step=min(step,min_step) return True else: for i in range(4): newx,newy=x+dx[i],y+dy[i] if judge(newx,newy): point[x][y]=1 dfs(newx,newy,step+1) point[x][y]=0 dfs(sx,sy,0) print(count)#路径总数 print(min_step)#最短路径长
我是小郑 正在备战蓝桥杯 正在奔赴热爱 奔赴山海
