【Python】算法笔记
1 输入
在 Python 中，可以使用 `input()` 函数接收控制台的输入，然后将其转换为数字类型（整数或浮点数）。以下是几种常见的方法：
1. 接收整数输入
num = int(input("请输入一个整数: ")) print("你输入的数字是:", num)2. 接收浮点数输入
num = float(input("请输入一个浮点数: ")) print("你输入的数字是:", num)3. 处理异常（避免输入非数字时报错）
try: num = float(input("请输入一个数字: ")) print("你输入的数字是:", num) except ValueError: print("输入无效，请确保输入的是数字！")4. 接收多个数字（例如，一行输入多个数字，用空格分隔）
input_str = input("请输入多个数字，用空格分隔: ") numbers = list(map(float, input_str.split())) print("你输入的数字列表是:", numbers)`map()` 的作用是什么？
`map()` 是 Python 的一个内置函数，它的作用是对一个可迭代对象（如列表）中的每个元素应用某个函数，并返回一个新的迭代器。**语法：**
```python
map(function, iterable)
```
- `function`：要应用的函数（如 `int`、`float`、`str` 等）。
- `iterable`：可迭代对象（如列表、元组等）。
**`numbers = list(map(float, input_str.split()))` 解析**
1. **`input_str.split()`**
- `input()` 接收的是字符串，例如 `"10 20 30.5"`。
- `.split()` 默认按空格分割字符串，返回一个字符串列表：
```python
["10", "20", "30.5"]
```2. **`map(float, ...)`**
- `map(float, ["10", "20", "30.5"])` 会对列表中的每个元素应用 `float()` 函数，转换成浮点数：
```python
[10.0, 20.0, 30.5] # 但 map() 返回的是迭代器，不是列表
```3. **`list(map(...))`**
- `map()` 返回的是一个迭代器（`map object`），用 `list()` 将其转换成列表：
```python
[10.0, 20.0, 30.5] # 最终结果
```
**替代写法（列表推导式）**
除了 `map()`，也可以用 **列表推导式** 实现相同功能：
```python
numbers = [float(x) for x in input_str.split()]
```
- 效果和 `map(float, ...)` 一样，但更直观。
2 list
2.1 list遍历
for i, x in enumerate(nums): # x=nums[i]2.2 list初始化
# 初始化一个长度为 N 的一维数组 Array = [0] * N # 初始化一个形状为 MxN 的二维数组(矩阵) Matrix = [[0] * N for _ in range(M)] # 思考：可以写成 [[0] * N] * M 吗？**绝对不能写成 `[[0] * N] * M`！** 这两个写法有**本质区别**，会产生不同的结果。 ## 原理分析 ### 1. **正确写法**：`[[0] * N for _ in range(M)]` ```python M = 3 N = 4 Matrix1 = [[0] * N for _ in range(M)] Matrix1[0][0] = 99 # 只修改第一个子列表的第一个元素 print(Matrix1) # 输出：[[99, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] # ✅ 只改变了第0行的第0列，其他行不受影响 ``` **内存结构**：创建了 **M个独立的列表** - `Matrix1[0]`、`Matrix1[1]`、`Matrix1[2]` 都是不同的列表对象 - 修改一个不会影响其他 ### 2. **错误写法**：`[[0] * N] * M` ```python M = 3 N = 4 Matrix2 = [[0] * N] * M Matrix2[0][0] = 99 # 修改第一个子列表的第一个元素 print(Matrix2) # 输出：[[99, 0, 0, 0], [99, 0, 0, 0], [99, 0, 0, 0]] # ❌ 所有行的第0列都被改变了！ ``` **内存结构**：创建了 **M个对同一个列表的引用** - `Matrix2[0]`、`Matrix2[1]`、`Matrix2[2]` 都指向**同一个列表对象** - 修改其中一个，所有引用都会看到变化2.3 list在后面增加一项
.append(xxx)
2.4 排序
nums.sort()
3 逻辑判断
3.1 i is not j
elif i is not j:
不能写成
elif i == j is False:
这行代码在Python中实际上被解释为：(i == j) and (j is False)，而不是你期望的(i == j) == False。
由于j是一个链表节点，它永远不会是False，所以这个条件永远为False
正确写法：
elif i != j: # 使用 != 运算符
elif i is not j: # 使用 is not
elif not (i == j): # 使用 not 包装
3.2 连续不等式或等式
# 判断 a，b，c 是否相等，Python里可以直接写连等 if a == b == c: return True # 不等式也可以 if a <= b < c: return True4 交换元素值
# c语言风格的交换两个元素值 tmp = a a = b b = tmp # python风格 a, b = b, a5 队列
queue = collections.deque()
queue.append(root)
len(queue)
queue.popleft()
6 哈希表
6.1 普通哈希表
hash = dict() hash = collections.defaultdict(list) # 如果 key 不在字典中，则自动插入一个空列表 hash.get(key) # key为None，返回None hash[key] # key为None, 报错 del hash[key] # 删除hash = set(nums) # 把 nums 转成哈希集合 hash.remove(x) hash.add(x) if x not in hash:6.2 记住插入顺序的哈希表
# from collections import OrderedDict self.cache = OrderedDict() # key -> value cache.move_to_end('b', last=False) # 移到开头 self.cache.popitem()7 无限大
cost = float('+inf')8 数学
8.1 整数平方根⌊√n⌋
isqrt(n)