h5视频怎么制作教学_洛阳疫情防控政策最新_营销培训课程有哪些_seo文章优化技巧

一、Python中的列表（List）

Python的列表是动态数组，内置于语言中，功能强大且易用，非常适合算法竞赛。

1. 基本概念

定义：列表是一个有序、可变的序列，可以存储任意类型的元素（整数、字符串、甚至其他列表等）。

声明方式：

my_list = []  # 空列表
my_list = [1, 2, 3]  # 包含元素的列表
mixed_list = [1, "hello", 3.14]  # 混合类型

特点：
- 动态大小：可以随时添加或删除元素，无需预先指定大小。
- 可变性：可以修改列表中的元素。
- 索引：支持正向索引（从0开始）和负向索引（从-1开始倒数）。
- 内存：Python列表内部是动态数组，扩容时会分配更多空间（通常是当前大小的1.5到2倍）。

2. 常用操作

以下是Python列表的核心操作，时间复杂度标注在括号中：

访问元素：my_list[i] （

O (1)

）

print(my_list[0])  # 访问第一个元素
print(my_list[-1])  # 访问最后一个元素

修改元素：my_list[i] = value （ $O (1)$ ）
```
my_list[0] = 10  # 将第一个元素改为10
```
追加元素：append(value) （均摊 $O (1)$ ）
```
my_list.append(4)  # 在末尾添加4
```
插入元素：insert(index, value) （ $O (n)$ ，因为需要移动元素）
```
my_list.insert(1, 5)  # 在索引1处插入5
```
删除元素：
- pop(index)：删除并返回指定索引的元素，默认删除末尾（ $O (1)$ 末尾， $O (n)$ 其他位置）
```
my_list.pop()  # 删除末尾元素
my_list.pop(0)  # 删除第一个元素
```
- remove(value)：删除第一个匹配的值（ $O (n)$ ，因为需要查找）
```
my_list.remove(2)  # 删除值为2的元素
```

切片：my_list[start:end:step] （

O (k)

，k是切片长度）

print(my_list[1:3])  # 获取索引1到2的子列表
print(my_list[::-1])  # 反转列表

长度：len(my_list) （ $O (1)$ ）

排序：sort()（原地排序，

O (n l o g n)

）或sorted()（返回新列表）

my_list.sort()  # 默认升序
my_list.sort(reverse=True)  # 降序
new_list = sorted(my_list)  # 返回排序后的新列表

查找：value in my_list （ $O (n)$ ）
```
if 3 in my_list:print("Found")
```

3. 高级用法

列表推导式：快速生成列表。

squares = [x**2 for x in range(5)]  # [0, 1, 4, 9, 16]
evens = [x for x in my_list if x % 2 == 0]  # 提取偶数

嵌套列表：实现二维数组（矩阵）。

matrix = [[1, 2], [3, 4]]
print(matrix[0][1])  # 访问第1行第2列

注意：二维列表初始化时要小心浅拷贝问题：

# 错误：所有行指向同一对象
matrix = [[0] * 3] * 3
# 正确：
matrix = [[0 for _ in range(3)] for _ in range(3)]

4. 竞赛中的应用

动态数组：Python列表适合大多数需要动态调整大小的场景，如存储输入数据。
栈和队列：用append()和pop()实现栈，用append()和pop(0)实现队列（不过pop(0)是 $O (n)$ ，建议用collections.deque优化队列操作）。
排序和搜索：内置的sort()和sorted()非常高效，适合排序相关问题。
多维数组：处理矩阵、图的邻接表等。

5. 注意事项

性能：pop(0)和insert(0, value)是 $O (n)$ ，如果需要频繁操作列表头部，考虑用collections.deque。
内存：列表动态扩容可能导致内存开销，尽量预估大小。

浅拷贝 vs 深拷贝：

a = [1, 2, 3]
b = a  # 浅拷贝，指向同一对象
c = a.copy()  # 深拷贝（一级）
import copy
d = copy.deepcopy(a)  # 完全深拷贝（多级嵌套）

二、C++中的列表（std::vector）

C++没有直接的“列表”概念，但std::vector是最接近Python列表的动态数组结构，广泛用于算法竞赛。C++还有std::list（双向链表），但竞赛中极少使用，因为链表操作较慢。

1. 基本概念

定义：std::vector是C++标准模板库（STL）中的动态数组，支持随机访问和动态调整大小。
头文件：需要包含<vector>。
```
#include <vector>
using namespace std;
```

声明方式：

vector<int> vec;  // 空向量
vector<int> vec = {1, 2, 3};  // 初始化
vector<int> vec(5, 0);  // 5个0

特点：
- 动态大小：可以自动扩容，类似Python列表。
- 类型安全：必须指定元素类型（如int、double等）。
- 连续内存：元素存储在连续内存中，支持随机访问（ $O (1)$ ）。
- 扩容机制：当容量不足时，分配更大内存（通常2倍），拷贝元素，释放旧内存。

2. 常用操作

以下是std::vector的核心操作，时间复杂度标注在括号中：

访问元素：vec[i]或vec.at(i) （ $O (1)$ ）
```
cout << vec[0] << endl;  // 第一个元素
cout << vec.back() << endl;  // 最后一个元素
```
注意：vec[i]不检查越界，vec.at(i)会抛异常。
修改元素：vec[i] = value （ $O (1)$ ）
```
vec[0] = 10;
```
追加元素：push_back(value) （均摊 $O (1)$ ）
```
vec.push_back(4);  // 在末尾添加4
```
删除元素：
- pop_back()：删除末尾元素（ $O (1)$ ）
```
vec.pop_back();
```
- erase(iterator)：删除指定位置元素（ $O (n)$ ，因为需要移动元素）
```
vec.erase(vec.begin());  // 删除第一个元素
vec.erase(vec.begin() + 2);  // 删除第3个元素
```
插入元素：insert(iterator, value) （ $O (n)$ ，因为需要移动元素）
```
vec.insert(vec.begin() + 1, 5);  // 在索引1处插入5
```
大小和容量：
- size()：返回元素个数（ $O (1)$ ）
- capacity()：返回当前分配的内存大小（ $O (1)$ ）
- resize(n)：调整大小，不足补默认值，多了截断
- reserve(n)：预分配内存，避免频繁扩容
```
vec.reserve(100);  // 预分配100个元素的空间
```
清空：clear() （ $O (1)$ ，仅清空元素，不释放内存）
```
vec.clear();
```

排序：需要<algorithm>库的sort函数（

O (n l o g n)

）

#include <algorithm>
sort(vec.begin(), vec.end());  // 升序
sort(vec.begin(), vec.end(), greater<int>());  // 降序

查找：find或手动遍历（

O (n)

）

auto it = find(vec.begin(), vec.end(), 3);
if (it != vec.end()) cout << "Found" << endl;

3. 高级用法

迭代器：用于遍历或操作。

for (auto it = vec.begin(); it != vec.end(); ++it) {cout << *it << " ";
}

或用范围for循环（C++11）：

for (int x : vec) {cout << x << " ";
}

二维向量：实现矩阵。

vector<vector<int>> matrix(3, vector<int>(3, 0));  // 3x3矩阵，初始化为0
matrix[0][1] = 5;  // 修改第1行第2列

自定义比较：排序时可以传递比较函数。

sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });  // 降序

4. 竞赛中的应用

动态数组：vector适合需要动态调整大小的场景，如存储图的邻接表。
栈：用push_back()和pop_back()实现栈。
排序和搜索：结合sort和binary_search处理有序数据。
矩阵和图：二维vector用于表示矩阵或邻接表。

5. 注意事项

性能：push_back均摊O(1)，但扩容可能导致拷贝开销，建议用reserve预分配空间。
越界访问：vec[i]不检查越界，可能导致未定义行为，建议用at(i)或检查size()。
内存管理：clear()不释放内存，需用shrink_to_fit()或swap技巧：
```
vector<int>().swap(vec);  // 释放内存
```
迭代器失效：插入或删除元素可能导致迭代器失效，需小心。

三、Python列表与C++ vector的对比

特性/操作	Python List	C++ std::vector
类型	动态数组，内置类型	动态数组，STL模板类
元素类型	任意类型（动态类型）	固定类型（静态类型）
内存分配	动态扩容（1.5-2倍）	动态扩容（通常2倍）
访问	$O (1)$ ，支持负索引	$O (1)$ ，无负索引
追加	`append`，均摊 $O (1)$	`push_back`，均摊 $O (1)$
插入/删除	$O (n)$ ，头部操作慢	$O (n)$ ，头部操作慢
切片	支持，$O(k) $	不支持，需手动实现
排序	`sort()`/`sorted()`， $O (n l o g n)$	`std::sort`， $O (n l o g n)$
内存管理	自动管理	需手动优化（如`reserve`）
竞赛适用性	简单易用，适合快速原型	性能更高，适合严格时间限制

四、算法竞赛中的建议

常见问题与优化：
- 输入处理：
  - Python：input().split()或list(map(int, input().split()))。
  - C++：cin配合vector。
```
int n; cin >> n;
vector<int> vec(n);
for (int i = 0; i < n; ++i) cin >> vec[i];
```
- 性能优化：
  - Python：避免频繁的pop(0)，用deque替代。
  - C++：用reserve减少扩容，ios::sync_with_stdio(false)加速I/O。
- 调试：
  - Python：用print快速调试。
  - C++：用cout或调试器，注意越界问题。