蓝桥杯Python组知识点

一、基础知识

1.基本输入输出

# 单行输入
num1 = input()  # 返回一个字符串
num2 = int(input())  # 将字符串转为整型
a, b, c = map(int, input().split())  # 一行输入多个数字，并以空格分开
lst1 = list(map(int, input().split()))  # 一行输入多个数字，并以空格分开，返回一个列表
print(num1)
print(num2)
print(a,b,c)
print(lst1)

#多行输入
lst12 = [int(input()) for _ in range(3)]
print(lst12)
lst13 = [list(map(int, input().split())) for _ in range(3)]
print(lst13)

# 输入
12
45
12 23 34
56 66 77
1
2
3
1 2 3
4 5 6
7 8 9
# 输出
12
45
12 23 34
[56, 66, 77]
[1, 2, 3]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2.字符列表连接

lst2 = ['hello', 'world']
print(''.join(lst2))

# 输出
helloworld
1
2
3
4
5

3.字母的大小写转换

str1 = 'hello'
str2 = 'WORLD'
print(str1)
print(str1.upper())
print(str2)
print(str2.lower())

# 输出
hello
HELLO
WORLD
world
1
2
3
4
5
6
7
8
9
10
11
12

4.匿名函数lambda

def square(a):
    return a * a
print(list(map(square, [1, 2, 3])))
print(list(map(lambda x: x*x, [1, 2, 3])))
lst3 = [[2, 4],
     [8, 9],
     [4, 5],
     [5, 10]]
print(sorted(lst3, key=lambda x: x[0]))

# 输出
[1, 4, 9]
[1, 4, 9]
[[2, 4], [4, 5], [5, 10], [8, 9]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5.进制转换

print(hex(16), oct(16), bin(16))
# 输出
0x10 0o20 0b10000
1
2
3

6.字符与整型之间的转换

print(chr(97), ord('a'))
# 输出
a 97
1
2
3

7.格式化保留小数点后几位小数

num3 = 3.1415926
print(f'{num3:.3f}')
# 输出
3.142
1
2
3
4

8.列表排序

lst4 = [3, 1, 45, 67, 21]
lst5 = sorted(lst4, reverse=True)  # sorted()返回一个新的排序后的列表
print(lst4)
print(lst5)
lst4.sort(reverse=True) # .sort()直接对原来的列表进行重新的排序
print(lst4)

# 输出
[3, 1, 45, 67, 21]
[67, 45, 21, 3, 1]
[67, 45, 21, 3, 1]
1
2
3
4
5
6
7
8
9
10
11

9.str的内建函数

str3 = 'hello world'  # 要注意这些内置函数都是返回一个新的字符串对象，并不是对原本的字符串进行修改
str4 = 'HELLO WORLD'
str5 = 'Hello World'
print(str3.upper())  
print(str4.lower())
print(str5.swapcase())  # 字符串大小写互换
print(str3.capitalize())  # 字符串首个字母大写
print(str3.title())  # 字符串每个单词首个字母大写
print(str3.find('l', 0, -1))  # 在指定范围内搜索第一个匹配的字符并返回其索引，若没有匹配项则返回-1
print(str3.index('l'))  # 搜索第一个匹配的字符并返回其索引，若没有匹配项则报错
print(str3.rfind('l', 0, -1))  # 从后往前找第一个匹配的字符并返回其索引，若没有匹配项则返回-1
print(str3.count('ll'))  # 统计子字符串在字符串中出现的次数
print(str3.replace('l', '*', 3))  # 用新字符替换旧字符指定次数
print(str3.strip('h'))  # 删除字符串首尾指定的字符，只能删除字符串首尾的字符
print(str3.split())  # 以指定的字符为分隔符，将字符串分割成一个列表
print('*'.join(str3))  # 用指定的字符将字符串连接成一个新的字符串
print(str3)
print(str4)
print(str5)

# 输出
HELLO WORLD
hello world
hELLO wORLD
Hello world
Hello World
2
2
9
1
he**o wor*d
ello world
['hello', 'world']
h*e*l*l*o* *w*o*r*l*d
hello world
HELLO WORLD
Hello World
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

10.list的内建函数

lst14 = [1, 2, 3]
lst15 = [3, 4, 5]
print(lst14 + lst15)  # 列表拼接
str5 = 'hello world'
lst14.append(str5)  # 将str5当作一个元素添加
print(lst14)
lst14.extend(str5)  # 将str5的每一个字符当作一个元素添加
print(lst14)
lst14.insert(3, 'hello')  # 在指定为索引位置添加元素
print(lst14)
lst14.remove('l')  # 删除第一个匹配的元素
print(lst14)
print(lst14.index('l'))
1
2
3
4
5
6
7
8
9
10
11
12
13

二、常用内置模块

1.阶乘factorial

使用阶乘函数求组合数

import math
def c(m, n):
    return math.factorial(m)//(math.factorial(n) * math.factorial(m-n))
print(c(5, 2))
print(math.factorial(5))

# 输出
10
120
1
2
3
4
5
6
7
8
9

2.计数器Counter

统计一个列表中各种元素出现的次数

from collections import Counter
lst6 = ['a', 'a', 'c', 'c', 'b']
counter1 = Counter(lst6)
print(counter1)
counter1['a'] += 1;
print(counter1)
print(list(counter1))
print(counter1.keys())
print(counter1.values())
print(counter1.items())
for item in counter1.items():
    print(item[0], item[1])

# 输出
Counter({'a': 2, 'c': 2, 'b': 1})
Counter({'a': 3, 'c': 2, 'b': 1})
['a', 'c', 'b']
dict_keys(['a', 'c', 'b'])
dict_values([3, 2, 1])
dict_items([('a', 3), ('c', 2), ('b', 1)])
a 3
c 2
b 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.默认字典defaultdict

用哈希表计数的时候，若当前元素不存在，则置为1；但是用defaultdict直接+1就行，不需要判断，因为创建defaultdict的时候已经规定了默认值类型。

from collections import defaultdict
dict1 = defaultdict(int)  # 默认为int型，默认值为0
lst7 = ['a', 'a', 'b', 'c', 'c']
for i,x in enumerate(lst7):
    dict1[x] += 1
print(dict1)

# 输出
defaultdict(<class 'int'>, {'a': 2, 'b': 1, 'c': 2})
1
2
3
4
5
6
7
8
9

4.双端队列deque

from collections import deque
dq1 = deque([1, 2, 3], maxlen=4)  # # 初始化一个最大长度为maxlen的队列
dq1.append(1)
print(dq1)
dq1.append(4)
print(dq1)
dq2 = deque()  # 初始化一个无固定长度的队列
dq2.append(2)  # 队尾添加元素
dq2.append(3)
dq2.append(1)
dq2.append(6)
dq2.appendleft(0)  # 队首添加元素
print(dq2)
print(dq2.popleft(),dq2.pop())
print(dq2)

# 输出
deque([1, 2, 3, 1], maxlen=4)
deque([2, 3, 1, 4], maxlen=4)
deque([0, 2, 3, 1, 6])
0 6
deque([2, 3, 1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.全排列permutations

from itertools import permutations
lst8 = list(permutations([1, 2, 3]))  # 全排列
print(lst8)

# 输出
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
1
2
3
4
5
6

6.组合combinations

from itertools import combinations
lst9 = list(combinations([1, 2, 3], 2))  # 第二个参数为选择组合的个数
print(lst9)

# 输出
[(1, 2), (1, 3), (2, 3)]
1
2
3
4
5
6

7.累加accumulate

accumulate在求前缀和时很好用

from itertools import accumulate
lst10 = [1, 2, 3, 4.5, 5]
print(list(accumulate(lst10)))
print(list(accumulate(lst10, initial=0)))  # 如果提供了关键字参数 initial，则累加会以 initial值开始，这样输出就比输入的可迭代对象多一个元素。

# 输出
[1, 3, 6, 10.5, 15.5]
[0, 1, 3, 6, 10.5, 15.5]
1
2
3
4
5
6
7
8

8.堆heapq

python中的堆是小顶堆，如果是二维列表，默认以每个列表的第一个元素来排序。
1）heapify让列表具有堆的特征；
2）heappop弹出最小的元素（总是位于索引0处）
3）heappush用于在堆中添加一个元素；
4）heapreplace从堆中弹出最小的元素，再压入一个新元素

from heapq import *
hpq = [[2, 4], [8, 9], [4, 5], [5, 10]]
heapify(hpq)  # 将列表堆化
print(hpq)
print(heappop(hpq))  # 弹出堆顶元素
print(hpq)
heappush(hpq, [1, 10])  # 元素进堆
print(hpq)
print(heapreplace(hpq, [4,6]))  # heapreplace()将原堆的堆顶元素弹出，并且将新元素压进堆里
print(hpq)
1
2
3
4
5
6
7
8
9
10

时间库datetime

from datetime import *
start = date(year=2024, month=2, day=25)
end = date(year=2024, month=2, day=29)
t = timedelta(days=1)
while start <= end:
    print(start, start.weekday())
    start += t
print(end.year, end.month, end.day)
time1 = '2024-02-25 09:45:30'
time2 = '2024-02-25 11:22:03'
print(type(time1), time1)
time1 = datetime.strptime(time1, '%Y-%m-%d %H:%M:%S')  # strptime定一个时间字符串和分析模式，返回一个时间对象。
print(type(time1), time1)
time2 = datetime.strptime(time2, '%Y-%m-%d %H:%M:%S')
deltat = time2 - time1
print(deltat.seconds)

# 输出
2024-02-25 6
2024-02-26 0
2024-02-27 1
2024-02-28 2
2024-02-29 3
2024 2 29
<class 'str'> 2024-02-25 09:45:30
<class 'datetime.datetime'> 2024-02-25 09:45:30
5793
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

三、常用算法模板

1.最大公因数与最小公倍数

求两个数的最大公因数可以通过math.gcd(n,m)获取，同时也可以定义辗转相除法获取。
m*n = 最大公因数 * 最小公倍数
因此求两个数的最小公倍数可以通过最大公因数求得。

import math
print(math.gcd(3, 6))
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a
print(gcd(6, 3))

def lcm(a, b):
    return a*b // math.gcd(a,b)
print(lcm(3, 6))
# 输出
3
3
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.质数的判断，质数个数的求解

判断一个数是否为质数，可以通过暴力算法求得，而对于求（n, m）范围内，不包括m，质数的个数，可以通过埃氏筛来求取。
埃氏筛原理：一个数为质数，则它的倍数一定不是质数。

def isPrim(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
print(isPrim(4))

def countPrim(n,m):
    flags = [True for i in range(m)]
    for i in range(2,m):
        if flags[i]:
            for j in range(i+i, m, i):
                flags[j] = False
    count = 0
    for i in range(n,m):
        if flags[i]:
          count += 1
    return count
print(countPrim(2,7))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.快速幂

快速幂，可以有效优化幂次运算的时间效率

def normalPower(base, power):
    result = 1
    while power:
        if power % 2 == 1:
            result = result * base
        base = base * base
        power //= 2
    return result
print(normalPower(2,16))

# 输出
65536
1
2
3
4
5
6
7
8
9
10
11
12

4.二分查找与插入

1)查找：
bisect：查找目标元素右侧插入点
bisect_right：查找目标元素右侧插入点
bisect_left：查找目标元素左侧插入点
2)插入：
insort：查找目标元素右侧插入点，并保序地插入元素
insort_right：查找目标元素右侧插入点，并保序地插入元素
insort_left： 查找目标元素左侧插入点，并保序地插入元素

from bisect import *
lst11 = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5]
print(bisect(lst11,3))
print(bisect_right(lst11,3))
print(bisect_left(lst11,3))
insort(lst11,3.5)
print(lst11)
insort_right(lst11,3)
print(lst11)
insort_left(lst11,3)
print(lst11)

# 输出
[1, 2, 2, 3, 3, 3, 3.5, 4, 4, 4, 4, 5]
[1, 2, 2, 3, 3, 3, 3, 3.5, 4, 4, 4, 4, 5]
[1, 2, 2, 3, 3, 3, 3, 3, 3.5, 4, 4, 4, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.获取一个数每一位的值

num4 = int(input())
while num4:
    print(num4 % 10)
    num4 //= 10
# 输入
45642
# 输出
2
4
6
5
4
1
2
3
4
5
6
7
8
9
10
11
12

6.动态规划

最长上升子序列问题

lst1 = list(input())

dp = [1 for _ in range(len(lst1))] # dp[i]表示以第i个字符作为结尾的最长上升子序列

for i in range(1, len(lst1)):
    for j in range(i):
        if lst1[j] < lst1[i]:
            dp[i] = max(dp[j] + 1,dp[i])
print(max(dp))
1
2
3
4
5
6
7
8
9

最长公共子串

lst1 = list(input())
lst2 = list(input())
##dp[i][j]表示以lst2[i]和lst1[j]结尾的最长字串长度
dp = [[0 for _ in range(len(lst1)+1)] for _ in range(len(lst2)+1)]

for i in range(1,len(lst2)+1):
    for j in range(1,len(lst1)+1):
        if lst1[j-1] == lst2[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = 0
res = 0
for i in range(len(lst2)+1):
    for j in range(len(lst1)+1):
        if dp[i][j] > res:
            res = dp[i][j]
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最长公共子序列

lst1 = list(input())
lst2 = list(input())

##dp[i][j]表示lst2的前i个字符与lst1的前j个字符的最长公共子序列
dp = [[0 for _ in range(len(lst1)+1)] for _ in range(len(lst2)+1)]

for i in range(1, len(lst2)+1):
    for j in range(1, len(lst1)+1):
        if lst1[j-1] == lst2[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[-1][-1])
1
2
3
4
5
6
7
8
9
10
11
12
13

最长公共上升子序列

lst1 = list(input())
lst2 = list(input())

##dp[i][j]表示以lst2前i个字符和lst1前j个字符并且以lst1[j]作为公共上升子序列末尾的子序列长度
dp = [[0 for _ in range(len(lst1)+1)] for _ in range(len(lst2)+1)]

for i in range(1,len(lst2)+1):
    submax = 0 # 用于存储lst2[i] > lst1[j] 时lst2前i-1个字符与lst1前j个字符可以组成的最大上升子序列
    for j in range(1,len(lst1)+1):
        if lst1[j-1] != lst2[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = submax + 1
        if lst1[i-1] > lst2[j-1]:
            submax = max(submax,dp[i-1][j])
print(max(dp[-1])) # 最后一行表示lst2所有字符，分别以lst1第一个到最后一个字符为公共上升子序列结尾的上升子序列长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

更新时间

2024.03.05

参考链接

1
2