蓝桥杯(2):python基础算法【上】

时间复杂度、枚举、模拟、递归、进制转换、前缀和、差分、离散化

1 时间复杂度

重要是看循环，一共运行了几次

1.1 简单代码看循环

#时间复杂度1
n = int(input())
for i in range(1,n+1):
    for j in range(0,i):
        pass
###时间复杂度：1+2+3+....+n=n(1+n)/2 所以时间复杂度是o(n^2)
#时间复杂度2
for i in range(1,n+1):
    for j in range(0,n,i):
        pass
###时间复杂度：n+ n/2+ n/3+ .....+n/n = nlog(n)

1.2 复杂代码

1.2.1 归并排序

通过不断地往回带入得出的：一共带入了多少次呢？

看n可以被多少个2整除就可以 个数为： ，则有个o(n)叠加在一起，所以复杂度为o(nlogn)

2 枚举

2.1 定义

通过逐个尝试，遍历所有的解

2.2 流程

2.3 例子

注意字符串再 in上的伟大应用！！！！

2.3.1 简单计算

a = input()
sum1,sum2=0,0
for s in a:
    if s in "aeiou":
        sum1 +=1
    else:
        sum2+=1
print(sum1)
print(sum2)

2.3.2 洁净数

问题描述：小明不喜欢数字2，包括数位上包含数字2 的数，如果没有2则称为洁净数

n = int(input())
ans = 0
for i in range(1,n+1):
    if "2" not in str(i):
        ans+=1
print(ans)

2.3.3 扫雷【初用矩阵哦】

问题描述：

#枚举
def input_list():
    return list(map(int,input().split()))
n_m = input_list()
n = n_m[0]
m = n_m[1]
a = []
for i in range(n):
    a.append(input_list())
b = [[0]*m for i in range(n)] #生成n行m列的矩阵！
# print(b)
#表示方向
dir = [(1,0),(0,1),(-1,0),(0,-1),(-1,-1),(-1,1),(-1,1),(1,1)]  #一共8个方向
for i in range(0,n):
    for j in range(0,m):
        if a[i][j] == 1:
            b[i][j]=9
        else:
            b[i][j]=0
            for k in range(8):
                x,y = i+dir[k][0],j+dir[k][1]
                if 0