蓝桥杯的考察重点：加黑重点 (括号内了解）
算法：枚举、排序、搜索、计数、贪心、动态规划、图论、数论、博弈论、概率论、计算几何、字符串算法。
（递归、二分查找、哈希算法、分治算法、回溯算法）
数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构、嵌套数据结构。
（链表、散列表、二叉树、跳表、Trie树）
| 编程思维： | 说明 |
|---|---|
| 数学思维 | 公式计算 |
| 计算思维 | 程序自动化+抽象过程 |
| 计算机思维 | 不断试错 |
| 随机模拟思维 | 大量随机点模拟 |
| 模块化思维 | 功能拆分——化繁为简，分而治之，模块间松耦合，模块内紧耦合 |
| 规则化思维 | 抽象过程为规则 |
| 递归思维 | 函数内调用函数 |
| 脚本自动化思维 | 数据和功能分离 |
目录
算法复杂度
递归
fibonacci——爬楼梯
数组
两数之和问题
合并两个有序数组
栈
队列
树
二叉树
图
贪心算法
吃饼干问题
搜索
DFS深度优先搜索（Depth First Search）
回溯法
BFS广度优先搜索（Broadth_First Search）
二叉树的遍历
前序遍历
中序遍历
后序遍历
层次遍历
动态规划（Dynamic Programming）
背包问题
最长公共子串问题
最长公共子序列问题(LCS)
排序
快速排序
归并排序
冒泡排序
选择排序
插入排序
算法复杂度
包括时间复杂度和空间复杂度。
对于程序需要优先考虑时间。
Tn = O(f(n))。
时间复杂度是对程序运行时间的估算。
计算：（超过2层循环的算法直接换思路，时间复杂度小于等于O(n**2)）
选择最复杂的循环计算最高阶（包括递归调用，不包括其他循环和非循环）。
嵌套取乘积。
O(N*N)
多数据规模。
O(M+N)
递归例：等比数列2**i实现。
i = 1 while i <= n: i = i*2i依次为1,2,4,8,16...2**i,直到2**i不大于n时停止。
2**i == n。
i == log2(n)。
所以Tn = O(log(n))
思想：（将一个复杂的大问题拆分为小问题来解决）
一个问题的解等价于拆分为子问题的解。
子问题规模变小，但是子问题与原问题思路相同。
存在终止条件（符合算法的有限性）
评价：
优点：递归思想简单，容易理解思考；
缺点：空间复杂度高，堆栈溢出分险，耗时比较高，重复计算问题。
斐波纳吉序列就是典型的递归思想。
1. 递归法解决问题，自顶向下计算，时间复杂度高。
#递归fibonacci
def fun(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fun(n-1) + fun(n-2)
n = int(input())
num = fun(n)
print(num)
2. 递归中存在重复计算问题，将已经计算过的值保存到字典。
#hashmap()存储已经计算的值
di = {}
def func(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
if n in di:
return di.get(n)
else:
result = func(n-1) + func(n-2)
di[n] = result
return result
n = int(input())
num = func(n)
print(num)3. 递推方式，自底向上累加，难理解（用变量临时保存子问题的解）。
#循环，自底向上
def fibonacci(n):
a = 0
b = 1
if n == 0:
return 0
elif n == 1:
return 1
for i in range(1,n):
c = a+b
a = b
b = c
return b
n = int(input())
num = fibonacci(n)
print(num)描述：找出一个一维数组（li）中，两个数和为目标值（n）的下标。
暴力枚举法。
li = [2,7,11,15]
n = 9
for i in range(len(li)):
for j in range(i+1,len(li)):
if li[j]+li[i] == n:#如果两个数之和等于目标值，返回下标
print(i,j)用字典存储遍历过的值。
li = [2,7,11,15,13]
n = 20
di = {}#键存储数据，值存储下标
for i in range(len(li)):
sub = n - li[i]
if sub in di:#判断差值在字典中是否有键，有则返回下标；没有存入字典
print(di[sub],i)
else:
di[li[i]] = i描述：将两个递增数组(a,b)合并，并且排序。
结果存储在(a)。
——一次归并排序
用列表方法——list.extend()合并，list.sort()排序。
（只能说python的列表就是np。
数组遍历真烦。
。
。
）sort()快速排序的时间复杂度：
a = [1,5,9]
b = [3,5,7]
a = a+b
a.sort()
print(a)双指针遍历列表（利用列表有序），比较存入临时列表，再赋值给（a）。
，
双指针从后向前倒序遍历，先排序值大的元素，直接存入（a)。
，
栈先进后出思想
使用场景：1. 解决符号匹配的问题。
2. 解决递归的问题，典型的就是斐波那契数列的递归。
3. 解决四则运算表达式求值问题。
4. 计算机中函数的调用的原理。
栈的空间有限，如果递归没有结束条件，就会不断的压栈，然后栈溢出，程序出错。
所以递归的终止条件非常非常重要。
#写一个堆栈,大小为10
stack = []
print('入栈 *** 作')
num = 0
while num < 10:
date = input('请输入：')
if date == '1':
break
stack.append(date)
num += 1
print(stack)
print('出栈操作')
judge = len(stack)
if judge == 0:
print('空栈')
else:
print('总共有{}个元素'.format(judge))
date = int(input('你需要几个元素：'))
num = judge
while num > judge - date:
element = stack.pop()
num -= 1
#print(stack)
print(element)
先进先出思想
使用场景：1. 防止多个任务之间的冲突。
2.多个用户访问文件的顺序
#写一个队列,大小为10
queue = []
print('入队 *** 作')
num = 0
while num < 10:
date = input('请输入：')
if date == '1':
break
queue.append(date)
num += 1
print(queue)
print('出队操作')
judge = len(queue)
if judge == 0:
print('空队')
else:
print('总共有{}个元素'.format(judge))
date = int(input('你需要几个元素：'))
num = judge
while num > judge - date:
element = queue.pop(0)
num -= 1
#print(stack)
print(element)
概念：
节点
元素
节点的度：节点的子树个数
树的度：最大的节点度
叶子节点：度为0的节点
节点的层：根节点为第1层
节点的深度：自顶向下累加，最上边（根）为1
节点的高度：自底向上累加，最下边（叶子）为1
在Python中，可以用嵌套列表定义树结构。
myTree = ['a', #root
['b', #left subtree
['d', [], []],
['e', [], []] ],
['c', #right subtree
['f', [], []],
[] ]
]二叉树是和树不同的概念。
树变为二叉树：
一、删除父子之间的关系（仅连接长子）
二、连接兄弟关系
三、旋转树
二叉树的左子树为原树的父子关系，右子树为原树兄弟关系。
在python语言中，使用字典来进行定义。
后边对图进行DFS和BFS
#定义一个图的结构
graph={
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['C','D'],
'F':['D']
}树和图的遍历，主要区别是树有根节点，而图需要我们自身指定开始遍历的节点，起始节点的不同会导致遍历节点的不同。
每一次都要最好的结果——局部最优解，从而达到最终问题的结果是最好的——全局最优解
贪心算法
吃饼干问题描述：胃口——能吃多少为g[i]，尺寸——饼干大小为s[j]。
满足s[j]>=g[i]，满足胃口并且吃到最小的饼干，则为局部最优解。
直到每个人都吃到饼干或没有饼干即为全局最优解。
g = list(map(int,input().split()))#wei kou
s = list(map(int,input().split()))#chi cun
g.sort()
s.sort()
count = 0
for i in range(len(g)):
for j in range(len(s)):
if s[j]>=g[i]:
count += 1
s[j] = -1#相当于拿走这块饼干
#g[i] = float('inf')#正无穷大
break
print(count)DFS与BFS
代码来源
DFS深度优先搜索（Depth First Search）相当于树的前序遍历。
从根节点开始遍历每一条树枝，如果没有目标值，则返回节点，直到遇到目标值或者所有节点都被访问才会终止。
用于（遍历/搜索）（树/图）的算法，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次，
使用的栈这个数据结构，利用先进后出的概念。
#DFS指的是深度优先搜索 回溯法(会回看前面的节点)
#一直往前走，走不下去往回跳
#使用stack来进行深度的顺序
#把栈顶元素去除，在把临接点放入
#其实并不难，只要把队列改成栈就可以了
def DFS(graph,s):#图 s指的是开始结点
#需要一个堆栈
stack=[]
stack.append(s)
seen=set()#看是否访问过
seen.add(s)
while (len(stack)>0):
#拿出邻接点
vertex=stack.pop()#这里pop参数没有0了，最后一个元素
nodes=graph[vertex]
for w in nodes:
if w not in seen:#如何判断是否访问过，使用一个数组
stack.append(w)
seen.add(w)
print(vertex)思想：没有目标值，返回结点，遍历新的树枝——回溯法
回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
BFS广度优先搜索（Broadth_First Search）
类似于树的按层次遍历（即先遍历第i层，再遍历第i+1层）的过程。
是一种图形搜索演算法，简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。
如果所有节点均被访问，则算法中止。
利用队列的先进先出的思想来解决问题。
用队列存储遍历的顺序。
#BFS 广度优先搜索 层序遍历
def BFS(graph,s):#graph图 s指的是开始结点
#需要一个队列
queue=[]
queue.append(s)
seen=set()#看是否访问过该结点
seen.add(s)
while (len(queue)>0):
vertex=queue.pop(0)#保存第一结点，并d出，方便把他下面的子节点接入
nodes=graph[vertex]#子节点的数组
for w in nodes:
if w not in seen:#判断是否访问过，使用一个数组
queue.append(w)
seen.add(w)
print(vertex) 按路径遍历每一个节点，使得每个节点均被访问一次，而且仅被访问一次。
二叉树遍历四种方法
前序遍历根节点->左子树->右子树。
其实感觉是DFS。
左子树->根节点->右子树。
左子树->右子树->根节点。
从根节点开始按层次遍历二叉树的每一层。
其实感觉是BFS。
DP算法：从小问题入手，逐步解决大问题。
求解满足约束条件的最优解。
从子问题的组合中寻找最优方案的求解过程，使用空间换时间的策略。
对于子问题重叠的情况特别有效，因为它将子问题的解保存在表格中，当需要某个子问题的解时，直接取值即可，从而避免重复计算！
第一特征：问题自身具有最优子结构，问题最优解包含子问题最优解。
第二特征：问题自身具有重叠子问题。
步骤：
一、刻画最优子结构性质；
二、递归定义最优解值；
三、自底向上计算最优解；
四、根据计算得到最优解值。
最优子结构：和贪心一样，DP也是把一个复杂问题拆分为一个个步骤；而与贪心不一样的是，贪心是保证当前这一步是当前问题的最优解，而不保证这一步属于整个复杂问题的最优解。
而最优子结构就是要规定当前这一步是整个复杂问题的最优解。
子问题重叠：子问题重叠在贪心也需要体现，走每一步面对的问题都是同一个类型的，例如背包问题的子问题就是：当前我的背包有Xkg空间，我能选择XXX。
边界：边界体现在背包没有空间（无法继续装入物品）
子问题独立：子问题即上面走的每一步之间没有干扰（互不影响）
csu_zipple ：贪心算法为什么可能不是最优解？解答：比较贪心算法和DP算法
当每一步都是最优解的时候为什么总体却不是最优解，也就是说如何判断贪心算法是不是最优解？子问题最优->整体最优
和动态规划之间的问题不值一提咕咕鸽：贪心算法只能求局部最优，比如一条路是A -B-C，距离是5+9=14，另一条路是A-D-C，距离是9+1=10，贪婪算法直接走第一条路，因为5<9，但很明显第二条路短，所以我觉得有条件的话穷举然后比大小，这样最精确。
再例背包问题：
背包承重4。
物品A价值10，重量3；物品B价值3，重量1；物品C价值9，重量2。
用贪心算法，只会先选择价值比最高的C，然后只能选择B，但是并不是最优解=12
用动态规划，选择A和B，满足背包为4下的最优解=13
动态规划python实现
背包问题物品价值Vi，重量Wi。
对于背包承重w的最优解是c[i,w]
第i个物品重量大于背包容量，则不会选。
第i个物品重量不大于背包容量，考虑第i个物品选的价值大还是不选的价值大，进而选择最优解。
表示第i个物品选的价值
表示第i个物品不选的价值
w\\ max\left \{ {c[i-1,w-w_{i}]+v_{i},c[i-1,w]} \right \} & ,i>0 and w_{i}\leqslant w \end{matrix}\right." src="https://latex.codecogs.com/gif.latex?c%5Bi%2Cw%5D%20%3D%20%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%200%20%26%20%2Ci%3D0%20or%20w%3D0%5C%5C%20c%5Bi-1%2Cw%5D%20%26%20%2Cw_%7Bi%7D%3Ew%5C%5C%20max%5Cleft%20%5C%7B%20%7Bc%5Bi-1%2Cw-w_%7Bi%7D%5D+v_%7Bi%7D%2Cc%5Bi-1%2Cw%5D%7D%20%5Cright%20%5C%7D%20%26%20%2Ci%3E0%20and%20w_%7Bi%7D%5Cleqslant%20w%20%5Cend%7Bmatrix%7D%5Cright." />
m[i][j] = min(m[i-1][j],m[i][j-1]) + p[i][j]
最长公共子串问题 最长公共子序列问题(LCS)0 and x_{i}=x_{j}\\ max\left \{ l[i,j-1],l[i-1,j] \right \} & ,i,j>0 and x_{i}\neq x_{j} \end{matrix}\right." src="https://latex.codecogs.com/gif.latex?l%5Bi%2Cj%5D%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%200%20%26%20%2Ci%3D0%20or%20j%3D0%5C%5C%20l%5Bi-1%2Cj-1%5D+1%20%26%20%2Ci%2Cj%3E0%20and%20x_%7Bi%7D%3Dx_%7Bj%7D%5C%5C%20max%5Cleft%20%5C%7B%20l%5Bi%2Cj-1%5D%2Cl%5Bi-1%2Cj%5D%20%5Cright%20%5C%7D%20%26%20%2Ci%2Cj%3E0%20and%20x_%7Bi%7D%5Cneq%20x_%7Bj%7D%20%5Cend%7Bmatrix%7D%5Cright." />
排序十大排序算法：
比较排序
交换排序（冒泡排序、快速排序）
选择排序（简单选择排序、堆排序）
插入排序（直接插入排序、希尔排序）
归并排序（归并排序）
非比较排序
计数排序、基数排序、桶排序
十大排序算法
快速排序选择一个元素（枢轴元素），把小的放它左边，大的放它右边。
递归，分治法（分而治之）。
#寻找中间位置
def middle(li,left,right):
temp = li[left]#选取左边为枢轴元素，暂存temp
while left < right:#直到left==right退出，为中间空位
while left < right and li[right] >= temp:#右边大的不变
right -= 1
li[left] = li[right]#小的放左边空位
while left < right and li[left] <= temp:#左边小的不变
left += 1
li[right] = li[left]#大的放右边空位
li[left] = temp#将枢轴元素放到空位li[right] = temp
return left#此时left==right
#快速排序递归分治，传入参数：排序列表li，左边下标left，右边下标right
def kuaipai(li,left,right):
if left < right:#至少有两个元素才有顺序而言
mid = middle(li, left, right)
kuaipai(li,left,mid-1)#递归分治小的部分
kuaipai(li,mid+1,right)#递归分治大的部分
li = [13,76,6,44,39,82,55]
kuaipai(li, 0, len(li)-1)
print(li)一次归并：将两个有序表合并为一个新的有序表。
比较两个有序表中最小的元素，更小的放在新有序表中。
（一次归并是两个有序表合并为一个有序表，那么应用递归的思想。
）
归并排序：一个元素必然是有序的，一次归并两个元素为有序表。
再不断递归一次归并，形成最终的有序表。
递归，二分法。
#归并排序，传入参数：
#排序列表li，
#有序表1的开始位置low，
#有序表1的结束位置mid,(说明有序表2的起始位置为mid+1)
#有序表2的结束位置为high
def yiciguibing(li,low,mid,high):
i = low#第一个表的下标
j = mid + 1#第二个表的下标
ltmp = []#临时存储有序列表
while i <= mid and j <= high:#左右两边都有数，比较更小的放入ltmp
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
while i <= mid:#左边还有数，右边没数
ltmp.append(li[i])
i += 1
while j <= high:#右边还有数，左边没数
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp#替换原来的列表
# li 是由两个有序表组成
# li = [2,4,7,9,1,3,5,6,8]
# yiciguibing(li, 0,3,len(li)-1)
# print(li)
def guibing(li,low,high):
if low < high:#至少有两个元素（终止条件）
mid = (low + high) // 2#二分
guibing(li, low, mid)#归并左边
guibing(li, mid + 1, high)#归并右边
yiciguibing(li, low, mid, high)#合并左边和右边（二分直到单个有序才会一次归并）
li = [6,2,5,4,8,1,9,3,7]
guibing(li, 0, len(li)-1)
print(li)比较相邻位置元素。
小的左移，大的右移。
def maopao(n):
temp = None
for i in range(len(n)):#控制循环次数j
for j in range(len(n)-i-1):#控制比较次数
if n[j+1] < n[j]:#比较j和j+1项
temp = n[j+1]
n[j+1] = n[j]
n[j] = temp
return n
li = [13,76,6,44,39,82,55]
a = maopao(li)
print(a)找出最小的元素，放在最左边 。
def xuanze(n):
for i in range(len(n)):
index = i#i作为当前最小元素的下标index
for j in range(i,len(n)):
if n[j] < n[index]:#寻找比index更小的元素作为index
index = j
temp = n[index]
n[index] = n[i]
n[i] = temp
return n
li = [13,76,6,44,39,82,55]
b = xuanze(li)
print(b)将元素插入到有序列表的相应位置（扑克牌）
def charu(li):
for i in range(len(li)):
preindex = i -1
value = li[i]#元素的值
while preindex >= 0 and li[preindex] > value:#比元素大的向后移
li[preindex+1] = li[preindex]
preindex -= 1
li[preindex+1] = value#把元素放到空位（有序列表向后移而出现的）
li = [13,76,6,44,39,82,55]
charu(li)
print(li)
参考：
蓝桥杯前辈
python实现图的DFS和BFS_科研小阿斗的博客-CSDN博客_dfs python
Python 实现树结构_木水_的博客-CSDN博客_python 树
动态规划python实现_入眸幻灭的博客-CSDN博客_python 动态规划
学不完了，明天真题，后天比赛。
。
。
写文章牢记——要保存!!!十分钟一次！！！
坚毅——GRIT
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）