蓝桥杯第三级别——算法。

蓝桥杯的考察重点：加黑重点 (括号内了解）

        算法：枚举、排序、搜索、计数、贪心、动态规划、图论、数论、博弈论、概率论、计算几何、字符串算法。（递归、二分查找、哈希算法、分治算法、回溯算法）

        数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构、嵌套数据结构。（链表、散列表、二叉树、跳表、Trie树）

其它的：编程思维：

数学思维（公式计算）

计算思维（程序自动化+抽象过程）

计算机思维（不断试错）

随机模拟思维（大量随机点模拟）

模块化思维（功能拆分——化繁为简，分而治之，模块间松耦合，模块内紧耦合）

规则化思维（抽象过程为规则）

递归思维（函数内调用函数）

脚本自动化思维（数据和功能分离）

目录

算法复杂度

递归

fibonacci——爬楼梯 

数组

两数之和问题

合并两个有序数组

算法复杂度

包括时间复杂度和空间复杂度。

对于程序需要优先考虑时间。Tn = O(f(n))。时间复杂度是对程序运行时间的估算。

 计算：（超过2层循环的算法直接换思路，时间复杂度小于等于O(n**2)）

        选择最复杂的循环计算最高阶（包括递归调用，不包括其他循环和非循环）。

        嵌套取乘积。O(N*N)

        多数据规模。O(M+N)

例：

i = 1
while i <= n:
    i = i*2

i依次为1,2,4,8,16...2**i,直到2**i不大于n时停止。

2**i == n。i == log2(n)。

所以Tn = O(log(n))

递归

思想：（将一个复杂的大问题拆分为小问题来解决）

        一个问题的解等价于拆分为子问题的解。

        子问题规模变小，但是子问题与原问题思路相同。

        存在终止条件（符合算法的有限性）

评价：

        优点：递归思想简单，容易理解思考；

        缺点：空间复杂度高，堆栈溢出分险，耗时比较高，重复计算问题。

fibonacci——爬楼梯 

斐波纳吉序列就是典型的递归思想。

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)。，

贪心算法

每一次都要最好的结果，从而达到最终问题的结果是最好的。——全局最优解

吃饼干问题

描述：胃口——能吃多少为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)

。。。 后面的学不完了，听说还得学会暴力递归，暴力搜索，十大排序（快速排序，归并排序），动态规划。。。

 下一篇：蓝桥杯算法（python）_木北！的博客-CSDN博客