[数据结构与算法]蓝桥杯python（题目思路即解答（笔记，持续更新））

这篇文章是为蓝桥杯做准备时顺便做的笔记，用来讨论即参考用的，如有错误欢迎指正，有更好的方法也可以提出来一起讨论，谢谢各位大佬们orz
因为本人不是VIP，只能刷蓝桥杯里面的普通题，还请见谅orz
注：代码中的input别尚自加东西进去，会报错。别问，问就是血淋淋的教训，改了半个小时的代码QAQ

基础练习

A+B问题

content = input()
str_list = content.split(' ')
int1 = int(str_list[0])
int2 = int(str_list[1])
result = int1 + int2
print(result)

数列排序

这道题我自己写了一个快速排序，也是给自己做练习用的，可以直接用python自带的排序函数

python自带函数

n = int(input())
arr = list(map(int,input().split()))
arr = sorted(arr)
for i in range(n):
    print(arr[i],end=' ')

快速排序

n = int(input())
arr = list(map(int,input().split()))
def partition(arr,low,high):
    i = low
    j = high
    if low < high:
        key = arr[low]
        while i < j:
            while arr[j] >= key and j != i:#向前寻找，找寻比key小的数
                j-=1
            arr[i],arr[j] = arr[j],arr[i]#交换位置
            while arr[i] < key and i != j:#向后寻找，找寻比key大的数
                i+=1
            arr[j],arr[i] = arr[i],arr[j]#交换位置
        else:
            partition(arr,low,i-1)
            partition(arr,i+1,high)
partition(arr,0,n-1)
for i in range(n):
    print(arr[i],end=' ')

十六进制转八进制

n = int(input())
arr = []
j = 0
for i in range(n):
    arr.append(input())
for i in arr:
    print(oct(int(i,16)).split('o')[-1])

十六进制转十进制

n = input()
print(int(n,16))

十进制转十六进制

这道题里面的输出要注意，他要求输出的字母是大写，所以可以用upper函数转过来

n = int(input())
a = hex(n).split('x')[-1]
print(a.upper())

特殊回文数

代码中的continue是出于习惯加进去的，听说在循环里能加快运行速度，但实际本人并没有测试过

n = int(input())
for i in range(10000,1000000):
    istr = str(i)
    if istr[:] == istr[::-1]:
        b = [int(j) for j in istr]
        if sum(b) == n:
            print(i)
        else:
            continue
    else:
        continue

回文数

回文数的特点就是正向读和反向读是一样的，所以可以直接判定字符串正向和反向是否相同即可

for i in range(1000,10000):
    istr = str(i)
    if istr[:] == istr[::-1]:
        print(i)

特殊的数字

def ok(a):#用于映射
    return a**3
for i in range(100,1000):
    istr = str(i)
    iint = [int(j) for j in istr]
    iint = list(map(ok,iint))
    if sum(iint) == i:
        print(i)

杨辉三角形

n = int(input())
k = []#用来存储杨辉三角形的元素
for i in range(1,n+1):
    if i == 1:
        k.append(1)
        print(1)
    else:
        for j in range(1,i+1):
            if j == 1:#第一列都是1
                print(1,end=' ')
                k.append(1)
            elif j == i:#每行的最后一列也是1
                print(1)
                k.append(1)
            else:
            #从杨辉三角形中找规律，可以发现除第一列和最后一列的元素，其它的都是其上一行正上方的元素加左上角的元素，所以找到其在列表k中对应的位置即可
                num = int(i*(i+1)/2) - i + j
                k.append(k[num-i]+k[num-i-1])
                print(k[num-i]+k[num-i-1],end=' ')

查找整数

n = int(input())
iint = list(map(int,input().split()))
m = int(input())
j = 0
for i in range(len(iint)):
    if m == iint[i]:
        print(i+1)
        j+=1
        break
if j == 0:
    print(-1)

数列特征

n = int(input())
iint = list(map(int,input().split()))
print(max(iint))
print(min(iint))
print(sum(iint))

字母图形

num = list(map(int,input().split()))
n = num[0]
m = num[1]
d = [chr(i) for i in range(65,91)]#先获得字母表的字母
for i in range(n):
    for j in range(m):
        k = abs(i - j)#找规律，发现每个字母的位置对应其行数减去其列数的绝对值
        print(d[k],end = '')
    print()

01字串

这个代码并不泛用，只是单纯为了解决这道题而已，如果要求01编码长度大于5就凉了〒▽〒

for i in range(32):
    a = bin(i).split('b')[-1]
    n = 5-len(a)
    b = ['0']*n
    result = ''.join(b) + a
    print(result)

闰年判断

year = int(input())
if year % 4 == 0 and year % 100 != 0 or year % 400 == 0:#按要求判断
    print('yes')
else:
    print('no')

Fibonacci数列

网上找的方法，自己的理解是相加的话先求余和后求余一样，先求余可以防止大数字出现，加快计算速度
但本人觉得计算速度应该不会差太多，有大佬解释一下吗orz 为什么不能先求和后求余呢

n = int(input())
f1 = 1
f2 = 1
if n > 2:
    for i in range(3,n+1):
        f3 = (f1 + f2) % 10007
        f1 = f2
        f2 = f3
    print(f3)
else:
    print(f1)

圆的面积

没什么说的，要求到小数点后7位，所以pi精确度要高一些，输出用正则即可

r = int(input())
PI=3.14159265358979323
print('%.7f'%(PI*r**2))

序列求和

等差序列的前n项和，直接套公式

n = int(input())
snum = (1+n)*n/2
print(int(snum))

算法训练

印章

可以把这道题看成盒子放球的问题，将n种印章看成n个盒子，然后购买m张印章看成拥有m个相同的球。所以我们只要求n个盒子里都有球的概率即可
这里采用逆向思维（直接算过于复杂），计算至少有一个盒子没有球的概率
可以得到下面公式：
某一个盒子为空：
P { A i } = ( 1 ? 1 n ) m P\left \{ A_{i} \right \}=\left ( 1-\frac{1}{n}\right)^{m} P{Ai?}=(1?n1?)m
同理，某两个盒子为空：
P { A i A j } = ( 1 ? 2 n ) m P\left \{ A_{i}A_{j} \right \}=\left ( 1-\frac{2}{n}\right)^{m} P{Ai?Aj?}=(1?n2?)m
以此类推，有
$$P\left\{\underset{i=1}{\overset{n?1}{?}}{A}_i\right\}={\left(1?\frac{n?1}{n}\right)}^m$$
由n个相容事件的概率公式可得
P { B } = C n 1 ( 1 ? 1 n ) m ? C n 2 ( 1 ? 2 n ) m + ? + ( ? 1 ) n ? 1 C n n ? 1 ( 1 ? n ? 1 n ) m P\left \{ B \right \}=C_{n}^{1}\left ( 1-\frac{1}{n} \right )^{m}-C_{n}^{2}\left ( 1-\frac{2}{n} \right )^{m}+\cdots+\left ( -1\right )^{n-1}C_{n}^{n-1}\left ( 1-\frac{n-1}{n} \right )^{m} P{B}=Cn1?(1?n1?)m?Cn2?(1?n2?)m+?+(?1)n?1Cnn?1?(1?nn?1?)m
所以所有盒子里都装有球的概率为
P { C } = 1 ? P { B } P\left \{ C \right \}=1-P\left \{ B \right \} P{C}=1?P{B}
借鉴文章：
蓝桥杯算法训练-印章

[1]蔣茂森.n个相容事件和的概率公式及其应用[J].数学通报,1964(11):39-40.

num = list(map(int,input().split()))
n,m = num[0],num[1]
def C(n,m):#组合函数
    M = 1
    N = 1
    for i in range(1,m+1):
        M*=i
        N*=(n-i+1)
    return N/M
if n > m:#当买的次数比印章的种类少时，肯定不可能买全
    print('%.4f'%0)
else:#按公式计算
    empty = [(-1)**(i+2)*C(n,i+1)*(1-(i+1)/n)**m for i in range(n-1)]
    print('%.4f'%(1 - sum(empty)))