Python蓝桥杯

Posted on 2024-05-15 Views:

基本语法

进制转换函数

bin(x)将十进制（decimal）转换为二进制（binary）
oct(x)转换为八进制（octal）
hex(x)转换为十六进制（hexadecimal）
其他进制转十进制：int(x, base)：将字符串x按照指定的base进制转换为十进制整数，此处x的值为**’1010’或者’0b1010’都可以**。如果base的值为2，却给一个八进制数’0o1001’，肯定会报错；int函数的其他两个作用：将字符串转化为整数、将浮点数转化为整数

如何手算对应的进制数：比如转化为八进制，那就不断除8，取余，逆序排列即可

将这个字符串转化为列表：

列表推导式[i for i in x]
既然x是可迭代对象，可直接使用list(x)将其转化为列表。只不过第一个方法的可操作空间更多，比如int(i)将其转化为整数

sum()函数用于对一个可迭代对象中的元素进行求和，如sum(list)；还可以指定一个起始值，如sum(list, 10)，在list的基础上再加上10；

map函数

Python 内置的函数之一，用于将一个函数应用于可迭代对象（如列表、元组等）的每个元素，生成一个新的迭代器。例如将一个列表中的每个元素都转换为整数：

1
2
3

numbers = ['1', '2', '3', '4', '5']
integer_numbers = map(int, numbers)
print(list(integer_numbers))  # 输出：[1, 2, 3, 4, 5]

enumerate函数

Python 内置函数之一，用于在迭代可迭代对象时同时获取索引和对应的元素值

my_list = ['apple', 'banana', 'cherry']
# start参数可以修改起始索引值，用来和现实世界照应
for index, value in enumerate(my_list, start=1):
    print(index, value)

range函数

Python 中的一个内置函数，用于生成一个指定范围内的整数序列。它的语法如下：

range(start, stop[, step])

其中参数的含义如下：

start: 序列的起始值（包含在序列中），默认为 0
stop: 序列的结束值（不包含在序列中）
step: 递增（或递减）步长，默认为 1；如果步长为-1，则递减输出，要保证起始值>结束值

sort函数

Python 列表对象的一个方法，用于对列表进行排序，可以升序或降序，语法：

list.sort(key=None, reverse=False)

key: 用于排序的函数，如果指定了该参数，则列表中的每个元素都将被传递给该函数进行排序。默认为 None，表示直接比较元素本身
reverse: 表示是否按逆序排序，默认为 False，表示升序；如果设置为 True，则降序

# 按字符串长度排序
strings = ['apple', 'banana', 'cherry', 'date']
strings.sort(key=len)
print(strings)  # 输出：['date', 'apple', 'banana', 'cherry']

lambda

是 Python 中的一个关键字，用于创建匿名函数。匿名函数是一种在声明时不使用正式名称的小型函数，通常用于在代码中需要一个临时函数的情况下，语法：

lambda arguments: expression

arguments 是函数参数，可以是零个或多个，与普通函数的参数列表类似
expression 是一个表达式，用于计算函数的返回值

math

需要import

math.floor()向下取整；math.ceil()向上取整。取整可以直接用运算符//

4.3距离4.13还有十天，极限备考

首先熟悉一下编辑器IDLE：Anaconda自带IDLE，去安装目录下找到idle.exe并打开即可调出。找一个py文件，右键用IDLE打开，运行，此时提示找不到包，引发思考：Anaconda下的IDLE应该是base环境，也许我用的虚拟环境下也会有IDLE程序，用Everything搜一下，果然有，打开虚拟环境下的IDLE，emmm但是仍然提示找不到，算了不重要

题型

暴力

“暴力”（Brute Force）指的是一种直接、简单、但往往效率低下的解决方法。这种方法通常会尝试所有可能的组合或解决方案，直到找到符合条件的解决方案为止，即穷举

暴力算法不涉及复杂的优化或启发式技巧，尽管暴力算法在某些情况下可能是有效的，但对于大规模的问题或输入数据，它们往往会导致计算成本极高，因为它们可能需要尝试的解决方案数量呈指数增长

举例来说，如果要解决一个密码破解的问题，暴力方法就是尝试所有可能的密码组合，直到找到正确的密码。虽然这种方法在密码空间较小的情况下可能是可行的，但对于更长、更复杂的密码，它的效率将会大大降低

在设计算法时，通常会尝试避免使用暴力方法，而是寻求更加高效和优化的解决方案，例如利用数据结构、算法优化技巧或者启发式算法来提高效率

贪心

“贪心”（Greedy）是一种解决问题的策略或方法。贪心算法在每一步都会做出局部最优的选择，希望通过局部最优解的选择最终能够得到全局最优解。贪心算法通常不会进行回溯，也不会考虑未来可能发生的情况，而是基于当前状态下的最佳选择来进行决策

在某些情况下，贪心算法可能会得到次优解甚至是错误的解。因此，在应用贪心算法时，需要确保问题具有贪心选择性质，并且贪心选择会导致最优解。

一些经典的问题可以使用贪心算法进行求解，例如：

零钱找零问题
活动选择问题
最小生成树问题（如Prim算法和Kruskal算法）
最短路径问题（如Dijkstra算法）

贪心算法通常具有高效的时间复杂度，并且相对简单易于实现。然而，需要注意的是，贪心算法的正确性通常需要经过证明，不能轻易地假设贪心选择一定能得到最优解

动态规划

动态规划（Dynamic Programming，简称DP）是一种解决多阶段决策过程最优化问题的数学方法。它将原问题拆分成一系列子问题，并按照一定的顺序进行求解。与分治法类似，动态规划算法也是将问题分解成更小的子问题来求解，但与分治法不同的是，动态规划会保存子问题的解，避免重复计算，从而提高效率

动态规划常用于解决具有最优子结构性质的问题，即问题的最优解可以通过子问题的最优解来构造。它通常包含以下步骤：

定义状态：明确定义问题的状态，通常用一个或多个变量来表示状态。这些变量可以描述问题的特征，例如长度、容量、位置等。
确定状态转移方程：找出子问题之间的关系，建立状态之间的转移方程。这个方程通常是用当前状态和之前状态来表示当前状态的计算方式。
初始化：确定初始状态的值，通常是边界状态，用于递推计算。
计算最终解：按照状态转移方程和初始化条件，递归地计算出问题的最终解。

动态规划通常通过自底向上（bottom-up）或自顶向下（top-down）两种方式来实现。自底向上的方法从最小的子问题开始逐步求解，直至最终问题；自顶向下的方法则是从最终问题开始逐步分解为子问题，直至最小的子问题。

动态规划算法在解决一些优化问题时非常高效，但是需要注意的是，并非所有问题都适合使用动态规划求解，因为其转移方程和状态定义需要满足一定的条件

DFS深度优先搜索

DFS（Depth-First Search，深度优先搜索）是一种用于遍历或搜索树或图的算法。DFS 从起始顶点开始，沿着图的一条路径尽可能深地搜索，直到到达一个叶子节点或者无法继续前进。当无法继续前进时，DFS 回溯到上一个未访问的节点，并继续探索其他的分支。DFS 的过程可以看作是一种递归的过程，或者使用栈来实现。

DFS 的基本原理如下：

从起始顶点开始，将起始顶点标记为已访问。
从当前顶点出发，依次访问其未访问过的邻居顶点，并标记为已访问。
递归地对当前顶点的未访问过的邻居顶点执行相同的操作，直到到达一个叶子节点。
如果当前顶点没有未访问的邻居顶点，或者已经访问过所有邻居顶点，则回溯到上一个未访问的节点，并重复步骤 2 和步骤 3，直到遍历完成。

DFS 通常适用于解决图的遍历问题、连通性问题以及寻找路径问题。与广度优先搜索（BFS）相比，DFS 更加适用于深度遍历，因此更适合于解决一些连通性问题和路径问题。

在实现 DFS 时，可以使用递归或者栈来实现。递归是一种自然的方式来实现 DFS，但对于大型图或树，递归可能会导致栈溢出，因此对于大型数据集，最好使用栈来实现非递归的 DFS。

BFS广度优先搜索

BFS（Breadth-First Search，广度优先搜索）是一种用于遍历或搜索树或图的算法。BFS 从起始顶点开始，沿着图的一层一层的顺序进行搜索，先访问起始顶点的所有邻居顶点，然后再访问邻居顶点的邻居顶点，以此类推，直到到达目标顶点或遍历完整个图。

BFS 的基本原理如下：

从起始顶点开始，将起始顶点标记为已访问，并将其放入队列中。
从队列中取出一个顶点，访问它的所有未访问过的邻居顶点，并标记为已访问，并将它们放入队列中。
重复步骤 2，直到队列为空，表示已经遍历完整个图。

BFS 的搜索过程可以看作是一层一层地向外扩展，因此 BFS 通常适用于解决最短路径问题、连通性问题以及层级遍历问题。

在实现 BFS 时，通常使用队列来存储待访问的顶点。首先将起始顶点入队，然后在每次迭代中从队列中取出一个顶点，访问它的所有未访问过的邻居顶点，并将它们依次入队，直到队列为空为止。

BFS 的特点是保证最先访问的顶点离起始顶点最近，因此它适用于求解最短路径等问题。与深度优先搜索（DFS）相比，BFS 更适合于解决一些广度相关的问题。

二分查找

二分查找（Binary Search）是一种在有序数组中查找特定元素的算法。它通过将数组分成两半，并通过比较中间元素与目标值的大小关系来确定目标值可能在哪一半，从而将搜索范围缩小一半。如果中间元素等于目标值，则找到目标值；如果中间元素大于目标值，则在左半边继续查找；如果中间元素小于目标值，则在右半边继续查找。重复这个过程，直到找到目标值或搜索范围为空为止

二分查找的基本原理如下：

首先，确定数组的左右边界，即起始索引和结束索引。
然后，在每一轮查找中，计算中间元素的索引（取左右边界的中间位置）。
将目标值与中间元素进行比较。
如果中间元素等于目标值，则找到目标值，返回其索引。
如果中间元素大于目标值，则更新搜索范围为左半边，并在左半边继续查找。
如果中间元素小于目标值，则更新搜索范围为右半边，并在右半边继续查找。
重复步骤 2 至步骤 6，直到找到目标值或搜索范围为空为止。

二分查找的时间复杂度为 O(log n)，其中 n 为数组的长度。由于每一轮查找都将搜索范围缩小一半，因此二分查找具有很高的效率，尤其是对于大型有序数组。二分查找适用于静态数据结构，即数据不会频繁变化的情况

前缀和

前缀和（Prefix Sum）是指数组中前缀部分的所有元素的和。换句话说，前缀和数组中的每个元素都表示原始数组中从开头到当前位置的所有元素的和

前缀和的应用非常广泛，特别是在解决数组区间求和问题时。通过预先计算前缀和数组，可以在常数时间内快速求得任意区间的和，而无需每次都重新遍历原始数组

计算前缀和的步骤如下：

初始化一个长度为 n+1 的前缀和数组 prefix_sum，其中 n 是原始数组的长度。
将 prefix_sum[0] 初始化为 0。
对于原始数组中的每个元素 nums[i]，计算 prefix_sum[i+1] = prefix_sum[i] + nums[i]，即当前位置的前缀和等于前一个位置的前缀和加上当前位置的元素值。
最终得到的 prefix_sum 数组即为原始数组的前缀和数组。

通过预先计算前缀和数组，可以在常数时间内快速求得任意区间的和。例如，要计算区间 [i, j] 的和，只需计算 prefix_sum[j+1] - prefix_sum[i] 即可。

前缀和的时间复杂度为 O(n)，其中 n 是数组的长度。虽然计算前缀和需要遍历整个数组一次，但在解决区间求和问题时，通过预先计算前缀和数组可以大大降低计算复杂度

递归和递推

递归（Recursion）和递推（Recurrence）都是解决问题的方法，但它们的概念和应用方式略有不同。

递归：

递归是指一个函数调用自身的过程。在算法和编程中，递归通常用于解决可以被分解为相似子问题的问题。递归的基本思想是将原始问题分解为规模更小的子问题，然后通过递归调用解决这些子问题，最终将子问题的解合并起来得到原始问题的解。在递归过程中，需要定义一个递归终止条件，以避免无限递归

递归常见的应用包括树的遍历、图的搜索、动态规划等。例如，二叉树的前序遍历、中序遍历和后序遍历都可以通过递归实现。

递推：

递推是指根据已知的初始值和递推关系，通过反复迭代计算得到后续的值。递推是一种基于迭代的计算方法，常用于描述数列、序列等数学问题。

在计算机科学中，递推关系通常指的是一个数列中后一项与前几项的关系式。通过递推关系，可以从已知的初始值开始，依次计算出数列中的后续值。递推通常用于解决动态规划问题、数学问题等。例如，斐波那契数列就是一个经典的递推数列，可以通过递推关系 F(n) = F(n-1) + F(n-2) 计算出数列中任意一项的值。

总的来说，递归是一种解决问题的思想和方法，而递推是一种基于迭代的计算方法，常用于描述数列、序列等数学问题。在实际应用中，递归和递推经常会结合使用，特别是在动态规划等问题中。