学弟带你速通Python3
Python 语法核心要点总结
________________________________________
一、基础语法
1. 字面量与数据类型
o 字面量类型包括整数(666)、浮点数(13.14)、字符串("Hello")、布尔值(True/False)等12。
o 数据类型分为:int、float、str、list、tuple、dict、set,可通过 type() 函数查看25。
2. 注释规则
o 单行注释以 # 开头,多行注释用三引号包裹("""注释内容""")12。
3. 变量与赋值
o 变量无需声明类型,直接赋值即可(如 name = "Alice")26。
o 支持多重赋值和解包:a, b = 1, 2 或 x, *y = [1, 2, 3]48。
4. 缩进与代码块
o Python 依赖缩进(通常4个空格)定义代码块,缩进错误会引发 IndentationError67。
________________________________________
二、字符串操作
1. 定义与嵌套
o 单引号或双引号均可定义字符串,支持引号嵌套(如 "It's OK")2。
o 转义字符 \ 用于处理特殊符号(如 \n 换行)23。
2. 拼接与格式化
o 字符串拼接用 +,格式化推荐使用 f-string(f"{变量}")或 % 占位符(%s、%d)23。
o 字符串方法:replace()、split()、strip() 等处理文本58。
________________________________________
三、数据结构
1. 列表(List)
o 有序可变序列,支持增删改查:
pythonCopy Code
nums = [1, 2, 3]
nums.append(4) # 追加元素
nums.remove(2) # 删除元素
```:ml-citation{ref="5,8" data="citationList"}。
2. 字典(Dict)
o 键值对集合,通过键快速检索:
pythonCopy Code
info = {"name": "Bob", "age": 20}
print(info["name"]) # 输出 "Bob"
```:ml-citation{ref="4,5" data="citationList"}。
3. 元组与集合
o 元组(tuple)不可变,集合(set)元素唯一58。
________________________________________
四、流程控制
1. 条件语句
pythonCopy Code
if score >= 90:
print("优秀")
elif score >= 60:
print("及格")
else:
print("不及格")
```:ml-citation{ref="7,8" data="citationList"}。
2. 循环结构
o for 循环遍历序列(如列表、字符串):
pythonCopy Code
for i in range(5):
print(i)
```:ml-citation{ref="5,8" data="citationList"}。
o while 循环处理条件判断5。
________________________________________
五、函数与模块
1. 函数定义
o 使用 def 关键字定义函数,支持参数和返回值:
pythonCopy Code
def add(a, b):
return a + b
```:ml-citation{ref="8" data="citationList"}。
o 装饰器(@decorator)扩展函数功能,如日志记录4。
2. 模块与文件操作
o 通过 import 导入模块(如 import os)8。
o 文件读写使用 with open(...) as f 确保资源自动释放47。
________________________________________
六、高级特性
1. 推导式
o 简化列表、字典、集合的创建:
pythonCopy Code
squares = [x**2 for x in range(10)] # 列表推导式
even_dict = {x: x*2 for x in range(5)} # 字典推导式
```:ml-citation{ref="4,5" data="citationList"}。
2. 生成器与迭代器
o 生成器表达式((x for x in data))惰性求值,节省内存4。
________________________________________
七、异常处理
pythonCopy Code
try:
result = 10 / 0
except ZeroDivisionError:
print("除数不能为0")
finally:
print("执行结束")
```:ml-citation{ref="8" data="citationList"}。
---
以上为 Python 语法核心要点总结,涵盖基础语法到高级特性,适合快速查阅和系统学习。
________________________________________
一、基础规则
1. 注释
o 单行注释:# 这是注释
o 多行注释:"""这是多行注释""" 或 '''这也是多行注释'''
2. 变量与命名
o 变量无需声明类型,直接赋值:name = "Alice"
o 变量名规则:字母/下划线开头,区分大小写,不可用关键字(如 if, for)。
3. 缩进
o Python 用缩进(通常 4 个空格)表示代码块,不可混用空格和 Tab:
pythonCopy Code
if True:
print("正确缩进") # ✅
________________________________________
二、数据类型
类型 示例 说明
int 10, -5 整数
float 3.14, -0.5 浮点数
str "Hello", 'Python' 字符串(不可变)
bool True, False 布尔值(首字母大写)
list [1, "a", True] 列表(可变有序序列)
tuple (1, "a", True) 元组(不可变有序序列)
dict {"name": "Bob"} 字典(键值对集合)
set {1, 2, 3} 集合(元素唯一、无序)
________________________________________
三、运算符
1. 算术运算符
+, -, *, /(浮点除), //(整除), %(取余), **(幂)
pythonCopy Code
print(5 // 2) # 2(整除)
print(2 ** 3) # 8(2的3次方)
2. 比较运算符
==, !=, >, <, >=, <=
3. 逻辑运算符
and, or, not
________________________________________
四、流程控制
1. 条件语句
age = 18
if age < 12:
print("儿童")
elif age < 18:
print("青少年")
else:
print("成年人")
2. 循环语句
o for 循环遍历序列:
for i in range(3): # 输出 0,1,2
print(i)
o while 循环:
pythonCopy Code
count = 0
while count < 3:
print(count)
count += 1
________________________________________
五、字符串操作
1. 定义与拼接
pythonCopy Code
s1 = "Hello"
s2 = 'Python'
s3 = s1 + " " + s2 # "Hello Python"
2. 格式化输出
o f-string(推荐):
pythonCopy Code
name = "Alice"
print(f"Hello, {name}!") # Hello, Alice!
o 传统方法:
pythonCopy Code
print("Value: %d, Str: %s" % (10, "test"))
________________________________________
六、数据结构操作
1. 列表(List)
pythonCopy Code
nums = [1, 2, 3]
nums.append(4) # 追加元素 → [1,2,3,4]
nums.pop() # 删除末尾 → [1,2,3]
print(nums) # 索引访问 → 1
2. 字典(Dict)
pythonCopy Code
info = {"name": "Bob", "age": 20}
print(info["name"]) # 取值 → "Bob"
info["age"] = 21 # 修改值
info["city"] = "Beijing" # 新增键值对
________________________________________
七、函数
1. 定义与调用
pythonCopy Code
def add(a, b):
return a + b
print(add(3, 5)) # 8
2. 默认参数
pythonCopy Code
def greet(name="World"):
print(f"Hello, {name}!")
greet() # Hello, World!
________________________________________
八、文件操作
pythonCopy Code
# 写入文件
with open("test.txt", "w") as f:
f.write("Hello Python!")
# 读取文件
with open("test.txt", "r") as f:
content = f.read()
print(content) # Hello Python!
________________________________________
九、异常处理
pythonCopy Code
try:
num = int(input("输入数字: "))
except ValueError:
print("输入无效!")
else:
print("输入正确:", num)
finally:
print("程序结束")
________________________________________
快速检查工具
• 查看类型:type(变量)
• 类型转换:int("123"), str(100), list("abc")
• 帮助文档:help(函数名)(如 help(print))________________________________________
P
________________________________________
一、基础语法要点
1. 代码结构与缩进
o Python 依赖缩进(通常 4 个空格)定义代码块,缩进错误会引发 IndentationError14。
o 示例:
pythonCopy Code
if True:
print("正确") # ✅ 正确缩进
2. 变量与数据类型
o 变量无需声明类型,直接赋值:name = "Alice"25。
o 核心数据类型:
不可变:int、float、str、tuple
可变:list、dict、set56。
3. 运算符与表达式
o 比较运算符(==、> 等)和逻辑运算符(and、or)需注意优先级56。
________________________________________
二、核心数据结构操作
数据结构 操作示例 常见错误场景
列表 nums.append(4) 索引越界(IndexError)36
字典 info["name"] = "Bob" 键不存在(KeyError)36
字符串 s = f"Value: {x}" 引号不匹配(SyntaxError)28
________________________________________
三、流程控制与函数
1. 条件与循环
o if/elif/else 语句必须以冒号结尾26,如:
pythonCopy Code
if age >= 18: # ✅ 冒号不可省略
print("成年")
o for 循环遍历序列时避免修改原列表36。
2. 函数定义与调用
o 默认参数需放在非默认参数后,否则触发 SyntaxError26。
o 示例:
pythonCopy Code
def greet(name="World"): # ✅ 默认参数在后
print(f"Hello, {name}!")
________________________________________
四、高频编程错误及解决方法
1. 语法错误(SyntaxError)
o 常见原因:
缺少冒号(if x > 5 print() → 补冒号 :)26。
括号不匹配(print("Hello') → 统一引号)48。
o 解决方法:使用 IDE 自动检查(如 PyCharm)56。
2. 名称错误(NameError)
o 场景:使用未定义变量(如 print(undeclared_var))36。
o 解决:检查变量命名与作用域,使用 global 声明全局变量6。
3. 类型错误(TypeError)
o 场景:类型不兼容(如 "Hello" + 10 → str(10))36。
4. 缩进错误(IndentationError)
o 场景:代码块缩进不一致(如混用空格与 Tab)14。
o 解决:统一使用 4 个空格,IDE 设置自动转换56。
________________________________________
五、调试与避坑建议
1. 工具辅助
o 使用 try/except 捕获异常并输出友好提示36。
o IDE 调试功能(断点、变量监视)快速定位问题56。
2. 代码规范
o 避免复杂嵌套,拆分函数提升可读性56。
o 文件操作使用 with open(...) 自动释放资源56。
________________________________________
示例:综合错误处理
pythonCopy Code
try:
num = int(input("输入数字: "))
print(10 / num)
except ValueError:
print("输入非数字!"):ml-citation{ref="3,6" data="citationList"}
except ZeroDivisionError:
print("除数不能为0"):ml-citation{ref="1,7" data="citationList"}
________________________________________
________________________________________
Python 语法核心要点总结(2025年最新版)
结合最新语法规范与高频使用场景,以下为结构化整理:
________________________________________
一、基础语法
1. 注释与编码声明
o 单行注释以 # 开头,多行注释用三引号包裹("""注释""")16。
o Python 3 默认使用 UTF-8 编码,无需显式声明8。
2. 变量与命名规则
o 变量无需声明类型,直接赋值:name = "Alice"17。
o 命名规则:字母/下划线开头,区分大小写,不可使用关键字(如 if、for)68。
3. 数据类型
o 基本类型:int(整数)、float(浮点数)、str(字符串)、bool(布尔值)15。
o 类型转换:int("123")、str(100)、list("abc")16。
4. 运算符
o 算术运算符:+、-、*、//(整除)、**(幂)56。
o 逻辑运算符:and、or、not56。
________________________________________
二、数据结构
类型 定义与操作示例 特性说明
字符串
s = "Hello"
s.replace("H", "h") → "hello" 不可变,支持切片、格式化14。
列表
nums = [1, 2, 3]
nums.append(4) → [1,2,3,4] 有序、可变,支持增删改查57。
字典
info = {"name": "Bob"}
info["age"] = 20 → {"name":"Bob", "age":20} 键值对集合,键唯一57。
集合
s = {1, 2, 3}
s.add(4) → {1,2,3,4} 元素唯一、无序5。
________________________________________
三、流程控制
1. 条件语句
pythonCopy Code
if score >= 90:
print("优秀")
elif score >= 60:
print("及格")
else:
print("不及格") # 注意冒号和缩进:ml-citation{ref="6,7" data="citationList"}。
2. 循环语句
o for 循环遍历序列:
pythonCopy Code
for i in range(3):
print(i) # 输出 0,1,2:ml-citation{ref="5,7" data="citationList"}。
o while 循环:
pythonCopy Code
count = 0
while count < 3:
print(count)
count += 1:ml-citation{ref="5,7" data="citationList"}。
________________________________________
四、函数与模块
1. 函数定义与调用
pythonCopy Code
def add(a, b=0): # 默认参数需在后
return a + b
print(add(3, 5)) # 8:ml-citation{ref="2,5" data="citationList"}。
2. 匿名函数
pythonCopy Code
square = lambda x: x ** 2
print(square(3)) # 9:ml-citation{ref="5,8" data="citationList"}。
3. 模块导入
pythonCopy Code
import math
print(math.sqrt(16)) # 4.0:ml-citation{ref="2,8" data="citationList"}。
________________________________________
五、文件与异常处理
1. 文件读写
pythonCopy Code
with open("data.txt", "w") as f:
f.write("Hello") # 自动关闭文件:ml-citation{ref="7,8" data="citationList"}。
2. 异常捕获
pythonCopy Code
try:
num = int(input("输入数字: "))
except ValueError:
print("输入无效!"):ml-citation{ref="3,6" data="citationList"}。
________________________________________
六、高级特性
1. 推导式
pythonCopy Code
squares = [x**2 for x in range(5)] # [0,1,4,9,16]:ml-citation{ref="5,8" data="citationList"}。
2. 生成器
pythonCopy Code
gen = (x for x in range(3))
print(next(gen)) # 0(惰性计算):ml-citation{ref="5,8" data="citationList"}。
________________________________________
注意事项
• 缩进规则:必须使用 4 个空格,不可混用 Tab 和空格78。
• 字符串格式化:推荐 f-string(f"{变量}")14。
• 错误排查:使用 try-except 捕获异常,IDE 调试工具定位问题36。
掌握以上语法,可覆盖 90% 的日常开发场景,建议结合实践巩固理解! 🚀
python常见错误以及自己的解决办法
________________________________________
一、语法错误(SyntaxError)
1. 常见场景
o 缺少冒号 ::在 if/for/def 后忘记加冒号。
o 括号/引号不匹配:print("Hello) 或 if (x > 5。
o 错误缩进:混合使用空格和 Tab。
2. 示例
pythonCopy Code
if x > 5 # ❌ 缺少冒号
print("x 大于5")
3. 解决方法
o 检查代码块末尾是否有冒号 :。
o 使用 IDE(如 PyCharm、VSCode)的语法高亮和自动补全功能。
o 统一缩进为 4 个空格,避免混合 Tab 和空格。
________________________________________
二、名称错误(NameError)
1. 原因
o 变量/函数未定义就被使用。
o 拼写错误(如 list 写成 lisst)。
2. 示例
pythonCopy Code
print(age) # ❌ age 未定义
3. 解决方法
o 检查变量是否在作用域内(如全局变量需用 global 声明)。
o 使用 IDE 的变量名提示功能,避免拼写错误。
________________________________________
三、类型错误(TypeError)
1. 常见场景
o 类型不兼容:字符串 + 整数,如 "年龄:" + 18。
o 函数参数类型错误:len(10)。
2. 示例
pythonCopy Code
result = "总分:" + 100 # ❌ 字符串和整数不能直接相加
3. 解决方法
o 显式转换类型:str(100) 或 f"总分:{100}"。
o 使用 isinstance() 检查变量类型。
________________________________________
四、索引错误(IndexError)
1. 原因
o 访问列表/元组时索引超出范围。
2. 示例
pythonCopy Code
nums = [1, 2, 3]
print(nums) # ❌ 最大索引是2
3. 解决方法
o 检查列表长度:len(nums)。
o 使用安全访问:if index < len(nums): print(nums[index])。
________________________________________
五、键错误(KeyError)
1. 原因
o 字典中不存在的键被访问。
2. 示例
pythonCopy Code
info = {"name": "Alice"}
print(info["age"]) # ❌ 键 "age" 不存在
3. 解决方法
o 使用 get() 方法:info.get("age", "默认值")。
o 检查键是否存在:if "age" in info:。
________________________________________
六、属性错误(AttributeError)
1. 原因
o 对象没有某个属性或方法。
2. 示例
pythonCopy Code
num = 10
num.append(20) # ❌ 整数没有 append 方法
3. 解决方法
o 检查对象的类型和方法列表:dir(num)。
o 确认是否正确导入模块或类。
________________________________________
七、缩进错误(IndentationError)
1. 示例
pythonCopy Code
def func():
print("Hello") # ❌ 缺少缩进
2. 解决方法
o 确保代码块内统一缩进 4 个空格。
o 在 IDE 中开启“显示空格和 Tab”功能。
________________________________________
八、模块导入错误(ImportError)
1. 原因
o 模块未安装或路径不正确。
2. 示例
pythonCopy Code
import numpy # ❌ 若未安装 numpy 会报错
3. 解决方法
o 安装缺失的包:pip install numpy。
o 检查 PYTHONPATH 或项目路径设置。
________________________________________
九、值错误(ValueError)
1. 场景
o 类型正确但值无效:int("abc")。
2. 示例
pythonCopy Code
num = int("12.5") # ❌ 字符串无法转为整数
3. 解决方法
o 先验证数据合法性:"12.5".isdigit()。
o 使用异常捕获:
pythonCopy Code
try:
num = int(input("输入整数: "))
except ValueError:
print("输入无效!")
________________________________________
十、零除错误(ZeroDivisionError)
1. 示例
pythonCopy Code
result = 10 / 0 # ❌ 除数不能为0
2. 解决方法
o 检查除数是否为0:if divisor != 0:。
o 使用异常处理:
pythonCopy Code
try:
result = a / b
except ZeroDivisionError:
result = 0
________________________________________
十一、文件操作错误(FileNotFoundError)
1. 示例
pythonCopy Code
with open("data.txt", "r") as f: # ❌ 文件不存在
content = f.read()
2. 解决方法
o 检查文件路径和权限。
o 使用 os.path.exists() 验证文件是否存在:
pythonCopy Code
import os
if os.path.exists("data.txt"):
# 读取文件
________________________________________
十二、逻辑错误(代码能运行但结果错误)
1. 场景
o 条件判断错误(如 if x > 5 and x < 3)。
o 循环变量未更新,导致死循环。
2. 解决方法
o 使用 print() 或调试器逐行检查变量值。
o 编写单元测试(如 unittest 模块)。
________________________________________
调试技巧
1. 打印关键变量:在复杂逻辑中插入 print() 输出中间结果。
2. 使用断点调试:在 IDE 中设置断点,逐行执行代码。
3. 异常捕获:用 try-except 包裹可能出错的代码块。
4. 静态检查工具:使用 mypy 检查类型错误,pylint 检查代码规范。
________________________________________
预防错误的小习惯
1. 写代码前画流程图:明确逻辑再动手。
2. 分模块测试:先测试小功能再整合。
3. 善用类型提示:
pythonCopy Code
def add(a: int, b: int) -> int:
return a + b
Python 经典算法大全
________________________________________
一、排序算法
1. 冒泡排序
• 描述:通过相邻元素比较和交换实现排序,时间复杂度 O(n2)O(n2),空间复杂度 O(1)O(1),稳定13。
• 代码示例:
pythonCopy Code
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
2. 快速排序
• 描述:分治法思想,选取基准元素分割数组递归排序,平均时间复杂度 O(nlogn)O(nlogn),不稳定34。
• 代码示例:
pythonCopy Code
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
3. 归并排序
• 描述:分治法递归分割后合并有序子序列,时间复杂度 O(nlogn)O(nlogn),稳定35。
• 代码示例:
pythonCopy Code
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
res = []
while left and right:
res.append(left.pop(0) if left < right else right.pop(0))
return res + left + right
4. 其他排序算法
• 堆排序:利用堆结构选择最大/小元素,时间复杂度 O(nlogn)O(nlogn),不稳定35。
• 计数排序:适用于整数范围有限的数据,时间复杂度 O(n+k)O(n+k),稳定35。
• 基数排序:按位数分桶排序,时间复杂度 O(d(n+k))O(d(n+k)),稳定35。
________________________________________
二、搜索与查找算法
1. 二分查找
• 描述:在有序数组中快速定位目标,时间复杂度 O(logn)O(logn)7。
• 代码示例:
pythonCopy Code
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
2. 广度优先搜索(BFS)
• 描述:逐层遍历图或树的节点,常用于最短路径问题7。
• 代码示例(图遍历):
pythonCopy Code
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
queue.append(neighbor)
return visited
________________________________________
三、动态规划与分治算法
1. 动态规划(DP)
• 描述:将复杂问题分解为子问题,避免重复计算,典型应用如背包问题、斐波那契数列7。
• 示例(斐波那契数列):
pythonCopy Code
def fibonacci(n):
dp = [0, 1] + * (n-1)
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
2. 分治算法
• 描述:递归分解问题后合并结果,典型应用如归并排序、快速排序37。
________________________________________
四、图论算法
1. Dijkstra 最短路径算法
• 描述:解决单源最短路径问题,适用于非负权图,时间复杂度 O(mlogn)O(mlogn)(堆优化)36。
• 代码示例:
pythonCopy Code
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
________________________________________
五、其他经典算法
1. 贪心算法
• 描述:通过局部最优选择寻求全局最优,典型应用如霍夫曼编码7。
2. 回溯算法
• 描述:通过试错法解决约束满足问题,如八皇后、数独7。
________________________________________
性能与适用场景总结
算法类型 典型应用场景 时间复杂度 稳定性/特性
冒泡排序 小规模数据或教学示例 O(n2)O(n2) 稳定34
快速排序 大规模数据快速排序 O(nlogn)O(nlogn) 不稳定34
二分查找 有序数据集检索 O(logn)O(logn) 需有序7
动态规划 最优化问题(如背包、最短路径) 依问题复杂度 需状态转移方程7
________________________________________
Python 竞赛必备算法指南
________________________________________
一、基础算法
1. 排序算法
o 快速排序:分治法思想,平均时间复杂度 O(nlogn)O(nlogn),适用于大规模数据快速处理12。
o 归并排序:稳定排序,适合链表或外部排序场景,时间复杂度 O(nlogn)O(nlogn)26。
o 计数排序/基数排序:适用于整数范围较小的数据,时间复杂度 O(n+k)O(n+k)26。
2. 搜索算法
o 二分查找:在有序数组中快速定位目标,时间复杂度 O(logn)O(logn),常用于优化搜索问题68。
o 哈希查找:利用哈希表实现 O(1)O(1) 平均查找时间,适合快速匹配场景6。
________________________________________
二、图论与路径算法
1. 最短路径算法
o Dijkstra 算法:单源最短路径(非负权图),堆优化后时间复杂度 O(mlogn)O(mlogn)67。
o Floyd-Warshall 算法:多源最短路径,时间复杂度 O(n3)O(n3),适合小规模全源计算67。
2. 图遍历算法
o BFS(广度优先搜索):逐层遍历,解决最短路径、连通性问题67。
o DFS(深度优先搜索):递归或栈实现,用于拓扑排序、回溯问题67。
________________________________________
三、动态规划与贪心算法
1. 经典动态规划问题
o 背包问题:0-1背包、完全背包,通过状态转移方程优化资源分配67。
o 最长公共子序列(LCS):字符串匹配问题,时间复杂度 O(nm)O(nm)67。
2. 贪心算法
o 区间调度:选择不冲突的区间最大化任务数6。
o 霍夫曼编码:优先合并频率低的节点,生成最优前缀码67。
________________________________________
四、数论与字符串处理
1. 数论算法
o 欧几里得算法:计算最大公约数(GCD),扩展版本解决线性同余方程68。
o 素数筛法:埃拉托斯特尼筛法快速生成质数表68。
2. 字符串匹配算法
o KMP 算法:通过前缀函数跳过无效匹配,时间复杂度 O(n+m)O(n+m)6。
o Rabin-Karp 算法:利用哈希滚动比较,适合模式串较多场景6。
________________________________________
五、数据结构优化算法
1. 堆(优先队列)
o 快速获取最大/最小值,用于优化 Dijkstra 算法、合并K个有序链表67。
2. 并查集(Disjoint Set)
o 路径压缩 + 按秩合并,解决连通性问题和最小生成树(Kruskal 算法)67。
________________________________________
竞赛实战技巧
1. 模板化代码:提前编写快速排序、BFS/DFS 等高频算法的代码模板16。
2. 复杂度分析:根据数据规模选择算法(如 n≤103n≤103 可用 O(n2)O(n2) 算法,n≥105n≥105 需 O(nlogn)O(nlogn) 算法)26。
3. 调试技巧:利用 print 输出中间变量或使用断点调试工具(如 PyCharm)17。
________________________________________
高频题型与算法对应表
题型 推荐算法 来源
最短路径问题 Dijkstra、BFS 67
动态规划优化 状态压缩、滚动数组 67
大整数运算 字符串模拟、高精度加法 68
图连通性 并查集、Tarjan 算法 67
________________________________________
________________________________________
Python 竞赛必背算法与代码
________________________________________
一、基础算法
1. 快速排序
o 描述:分治法思想,平均时间复杂度 O(nlogn)O(nlogn),适用于大规模数据13。
pythonCopy Code
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
2. 二分查找
o 描述:在有序数组中快速定位目标,时间复杂度 O(logn)O(logn)26。
pythonCopy Code
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
________________________________________
二、图论算法
1. Dijkstra 最短路径(堆优化)
o 描述:单源最短路径,时间复杂度 O(mlogn)O(mlogn)26。
pythonCopy Code
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
2. BFS 广度优先搜索
o 描述:解决最短路径、连通性问题26。
pythonCopy Code
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
queue.append(neighbor)
return visited
________________________________________
三、动态规划
1. 0-1 背包问题
o 描述:状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)46。
pythonCopy Code
def knapsack(weights, values, capacity):
n = len(weights)
dp = [*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, capacity+1):
if j >= weights[i-1]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity]
2. 最长公共子序列(LCS)
o 描述:二维 DP 表解决字符串匹配问题46。
pythonCopy Code
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
________________________________________
四、数论与高效技巧
1. 欧几里得算法(GCD)
o 描述:计算最大公约数,时间复杂度 O(logmin(a,b))O(logmin(a,b))68。
pythonCopy Code
def gcd(a, b):
while b:
a, b = b, a % b
return a
2. 快速幂
o 描述:通过二进制分解优化幂运算,时间复杂度 O(logn)O(logn)26。
pythonCopy Code
def fast_pow(base, exponent):
res = 1
while exponent > 0:
if exponent % 2 == 1:
res *= base
base *= base
exponent = exponent // 2
return res
________________________________________
五、数据结构优化
1. 并查集(路径压缩 + 按秩合并)
o 描述:解决连通性问题,时间复杂度接近 O(1)O(1)67。
pythonCopy Code
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = *n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
________________________________________
竞赛高频算法速查表
题型 推荐算法 时间/空间复杂度
最短路径 Dijkstra(堆优化) O(mlogn)O(mlogn)
动态规划优化 滚动数组法 O(n)O(n) 空间
大整数运算 字符串模拟 O(n)O(n)
连通性检查 并查集 接近 O(1)O(1)
________________________________________
实战建议
1. 代码模板化:提前编写快速排序、Dijkstra 等高频算法模板26。
2. 复杂度敏感:根据数据规模选择算法(如 n≤104n≤104 可用 O(n2)O(n2),否则选 O(nlogn)O(nlogn))24。
3. 调试技巧:使用 print 输出关键变量或使用断言检查中间结果67。
________________________________________
Python 竞赛必背算法与代码扩展
________________________________________
一、字符串与数论优化
1. KMP 字符串匹配算法
o 描述:通过前缀函数跳过无效匹配,时间复杂度 O(n+m)O(n+m),适用于模式串重复匹配问题46。
pythonCopy Code
def kmp(text, pattern):
def build_lps(p):
lps = * len(p)
length = 0
i = 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length-1]
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(pattern)
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
return i - j
else:
if j != 0:
j = lps[j-1]
else:
i += 1
return -1
2. Manacher 算法(最长回文子串)
o 描述:线性时间复杂度求最长回文子串,竞赛高频考点8。
pythonCopy Code
def manacher(s):
s = '#' + '#'.join(s) + '#'
n = len(s)
p = * n
center = right = max_len = 0
for i in range(n):
if i < right:
mirror = 2 * center - i
p[i] = min(right - i, p[mirror])
while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and s[i-p[i]-1] == s[i+p[i]+1]:
p[i] += 1
if i + p[i] > right:
center, right = i, i + p[i]
if p[i] > max_len:
max_len = p[i]
return max_len
________________________________________
二、动态规划强化
1. 多重背包问题(二进制优化)
o 描述:将物品数量拆分为二进制组合,优化多重背包时间复杂度为 O(nlogm⋅v)O(nlogm⋅v)47。
pythonCopy Code
def multi_knapsack(weights, values, counts, capacity):
new_weights = []
new_values = []
for w, v, c in zip(weights, values, counts):
k = 1
while k <= c:
new_weights.append(w * k)
new_values.append(v * k)
c -= k
k *= 2
if c > 0:
new_weights.append(w * c)
new_values.append(v * c)
dp = * (capacity + 1)
for w, v in zip(new_weights, new_values):
for j in range(capacity, w-1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[capacity]
2. 状态压缩动态规划(旅行商问题 TSP)
o 描述:用二进制表示访问状态,解决 NP-Hard 问题的近似优化47。
pythonCopy Code
def tsp(graph):
n = len(graph)
dp = [[float('inf')] * (1 << n) for _ in range(n)]
dp:ml-citation{ref="1" data="citationList"} = 0
for mask in range(1 << n):
for u in range(n):
if mask & (1 << u):
for v in range(n):
if not mask & (1 << v) and graph[u][v] > 0:
new_mask = mask | (1 << v)
dp[v][new_mask] = min(dp[v][new_mask], dp[u][mask] + graph[u][v])
return min(dp[i][(1 << n) - 1] + graph[i] for i in range(n) if graph[i] > 0)
________________________________________
三、图论与高效技巧
1. 拓扑排序(Kahn 算法)
o 描述:解决有向无环图(DAG)的任务调度问题,时间复杂度 O(n+m)O(n+m)47。
pythonCopy Code
from collections import deque
def topological_sort(graph, in_degree):
queue = deque([u for u in in_degree if in_degree[u] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result if len(result) == len(graph) else []
2. 快速选择算法(Top-K 问题)
o 描述:类似快速排序的分治思想,平均时间复杂度 O(n)O(n)27。
pythonCopy Code
def quick_select(arr, k):
pivot = arr
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k <= len(left):
return quick_select(left, k)
elif k <= len(left) + len(mid):
return pivot
else:
return quick_select(right, k - len(left) - len(mid))
________________________________________
四、数学与位运算
1. 矩阵快速幂(斐波那契加速)
o 描述:用矩阵乘法优化递推式,时间复杂度 O(logn)O(logn)57。
pythonCopy Code
def matrix_pow(mat, power):
result = [[1 if i == j else 0 for j in range(len(mat))] for i in range(len(mat))]
while power > 0:
if power % 2 == 1:
result = matrix_mult(result, mat)
mat = matrix_mult(mat, mat)
power = power // 2
return result
def matrix_mult(a, b):
return [[sum(a[i][k] * b[k][j] for k in range(len(b))) for j in range(len(b))] for i in range(len(a))]
2. 位运算优化(统计二进制中 1 的个数)
o 描述:使用 Brian Kernighan 算法优化至 O(k)O(k)(k 为 1 的个数)58。
pythonCopy Code
def count_ones(n):
count = 0
while n:
n &= n - 1
count += 1
return count
________________________________________
竞赛高频算法速查表
算法类型 典型应用场景 时间/空间复杂度 引用来源
KMP 字符串匹配 文本快速模式匹配 O(n+m)O(n+m) 46
多重背包(二进制优化) 资源分配问题 O(nlogm⋅v)O(nlogm⋅v) 47
拓扑排序(Kahn) 任务调度、依赖解析 O(n+m)O(n+m) 47
矩阵快速幂 递推式加速(如斐波那契) O(logn)O(logn) 57
________________________________________
实战建议
1. 模板记忆:将拓扑排序、KMP 等代码模板化,方便快速调用47。
2. 边界处理:特别注意动态规划中的状态初始化和越界问题47。
3. 调试技巧:对复杂算法(如 Manacher)使用中间变量打印调试8。
掌握以上扩展算法可覆盖更多竞赛难题,建议结合 AtCoder 和 Codeforces 的高频题进行训练! 🚀
Python 竞赛必备算法与代码
________________________________________
一、字符串与图论扩展
1. KMP 字符串匹配算法
o 描述:通过前缀函数跳过无效匹配,实现高效字符串搜索,时间复杂度 O(n+m)O(n+m),适用于大规模文本匹配问题46。
pythonCopy Code
def kmp(text, pattern):
def build_lps(p):
lps = * len(p)
length, i = 0, 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(pattern)
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
return i - j
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
2. Tarjan 算法(强连通分量)
o 描述:用于求解有向图的强连通分量,时间复杂度 O(n+m)O(n+m),适用于网络流、依赖分析等场景17。
pythonCopy Code
def tarjan(u, graph, index, stack, indices, low, in_stack, scc):
indices[u] = index
low[u] = index
index += 1
stack.append(u)
in_stack.add(u)
for v in graph[u]:
if indices[v] == -1:
tarjan(v, graph, index, stack, indices, low, in_stack, scc)
low[u] = min(low[u], low[v])
elif v in in_stack:
low[u] = min(low[u], indices[v])
if low[u] == indices[u]:
component = []
while True:
v = stack.pop()
in_stack.remove(v)
component.append(v)
if v == u:
break
scc.append(component)
________________________________________
二、动态规划与数据结构
1. 区间动态规划(石子合并问题)
o 描述:通过二维 DP 表解决区间最优分割问题,典型应用包括石子合并、回文分割等,时间复杂度 O(n3)O(n3)16。
pythonCopy Code
def stone_merge(stones):
n = len(stones)
prefix = * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + stones[i]
dp = [*n for _ in range(n)]
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + prefix[j+1] - prefix[i]
if cost < dp[i][j]:
dp[i][j] = cost
return dp[n-1]
2. 树状数组(Fenwick Tree)
o 描述:高效处理前缀和与单点更新问题,时间复杂度 O(logn)O(logn),适用于动态数据统计67。
pythonCopy Code
class FenwickTree:
def __init__(self, size):
self.n = size
self.tree = * (self.n + 1)
def update(self, idx, delta):
while idx <= self.n:
self.tree[idx] += delta
idx += idx & -idx
def query(self, idx):
res = 0
while idx > 0:
res += self.tree[idx]
idx -= idx & -idx
return res
________________________________________
三、数学与优化技巧
1. 中国剩余定理(CRT)
o 描述:解决同余方程组问题,时间复杂度 O(k)O(k)(k 为方程数),常用于密码学和数论题目68。
pythonCopy Code
def crt(mods, remainders):
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
total = 0
M = 1
________________________________________
Python 竞赛必备算法与实战题目(2025 年精选版)
________________________________________
一、核心算法与代码实现
1. Kadane 算法(最大子序列和)
o 场景:动态规划解决连续子数组最大和问题,时间复杂度 O(n)O(n)17。
pythonCopy Code
def max_subarray_sum(nums):
max_sum = curr_sum = nums
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
2. 最长递增子序列(LIS)
o 场景:动态规划或二分优化,时间复杂度 O(nlogn)O(nlogn)17。
pythonCopy Code
def length_of_lis(nums):
dp = :ml-citation{ref="1" data="citationList"} * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
3. 唯一字符检测
o 场景:利用集合特性判断字符串是否包含重复字符,时间复杂度 O(n)O(n)3。
pythonCopy Code
def has_unique_chars(s):
return len(set(s)) == len(s)
4. 排列判断
o 场景:通过排序验证两个字符串是否为排列关系,时间复杂度 O(nlogn)O(nlogn)3。
pythonCopy Code
def is_permutation(s1, s2):
return sorted(s1) == sorted(s2)
5. 双指针数组合并
o 场景:合并两个非降序数组,时间复杂度 O(n+m)O(n+m)8。
pythonCopy Code
def merge_sorted_arrays(a, b):
i = j = 0
merged = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
merged.append(a[i])
i += 1
else:
merged.append(b[j])
j += 1
merged += a[i:] + b[j:]
return merged
________________________________________
二、高频算法题与答案
1. 完全平方数问题
o 题目:找到最小的整数 xx,使得 x+100x+100 和 x+268x+268 均为完全平方数2。
pythonCopy Code
def find_special_num():
for x in range(10000):
if (x + 100)‌**0.5 % 1 == 0 and (x + 268)**‌0.5 % 1 == 0:
return x
2. 日期计算(第几天)
o 题目:输入年月日,计算该日是当年的第几天25。
pythonCopy Code
def day_of_year(year, month, day):
days_in_month = [31,28,31,30,31,30,31,31,30,31,30,31]
if (year % 4 == 0 and year % 100 != 0) or year % 400 == 0:
days_in_month:ml-citation{ref="1" data="citationList"} = 29
return sum(days_in_month[:month-1]) + day
3. 反弹高度计算
o 题目:球从 100 米落下,每次反弹原高度一半,求第 10 次落地时总路程5。
pythonCopy Code
def ball_distance():
height = 100
total = height
for _ in range(10):
height /= 2
total += height * 2
return total, height
4. 快速选择算法(Top-K 问题)
o 题目:无需完全排序,快速找出数组中第 K 小的元素7。
pythonCopy Code
def quick_select(arr, k):
pivot = arr
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k <= len(left):
return quick_select(left, k)
elif k <= len(left) + len(mid):
return pivot
else:
return quick_select(right, k - len(left) - len(mid))
________________________________________
三、语法与基础题
1. 统计非负数的个数与和
o 题目:输入 10 个数,统计非负数的个数及总和5。
pythonCopy Code
def count_non_negative():
nums = list(map(int, input().split()))
non_neg = [x for x in nums if x >= 0]
return len(non_neg), sum(non_neg)
2. 字符串处理(替换字符)
o 题目:将字符串中的大写字母转换为小写并输出5。
pythonCopy Code
def to_lowercase(s):
return s.lower()
3. 数组逆序输出
o 题目:将一维数组逆序后输出5。
pythonCopy Code
def reverse_array(arr):
return arr[::-1]
________________________________________
竞赛实战技巧
1. 模板化代码:提前准备常用算法模板(如快速排序、并查集)17。
2. 复杂度优化:根据数据规模选择算法(如 n≤104n≤104 优先用 O(n2)O(n2))15。
3. 边界处理:注意数组越界和特殊输入(如空字符串或零值)35。
________________________________________
Python 竞赛必备十大算法
________________________________________
1. 二分查找
应用场景:有序数组的快速搜索、求极值问题(如最小化最大值)。
时间复杂度:O(logn)O(logn)
pythonCopy Code
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
2. 快速选择算法(Top-K 问题)
应用场景:无需排序直接找第 kk 小/大的元素。
时间复杂度:平均 O(n)O(n)
pythonCopy Code
def quick_select(arr, k):
pivot = arr
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k <= len(left):
return quick_select(left, k)
elif k <= len(left) + len(mid):
return pivot
else:
return quick_select(right, k - len(left) - len(mid))
3. KMP 字符串匹配
应用场景:高效模式串匹配(如文本搜索)。
时间复杂度:O(n+m)O(n+m)
pythonCopy Code
def kmp(text, pattern):
# 前缀函数构建(部分匹配表)
lps = * len(pattern)
length, i = 0, 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
# 匹配过程
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
return i - j
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
4. 并查集(路径压缩)
应用场景:连通性判断、动态合并集合(如最小生成树)。
时间复杂度:O(α(n))O(α(n))(近似常数)
pythonCopy Code
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_y] = root_x
5. Dijkstra 最短路径算法
应用场景:带权有向图单源最短路径(无负权边)。
时间复杂度:O(mlogn)O(mlogn)(优先队列优化)
pythonCopy Code
import heapq
def dijkstra(graph, start):
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
6. 动态规划(0-1 背包问题)
应用场景:有限容量下的最大价值选择。
时间复杂度:O(n⋅capacity)O(n⋅capacity)
pythonCopy Code
def knapsack(weights, values, capacity):
n = len(weights)
dp = * (capacity + 1)
for i in range(n):
for j in range(capacity, weights[i]-1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
7. 滑动窗口最大值(单调队列)
应用场景:固定窗口大小的最值问题。
时间复杂度:O(n)O(n)
pythonCopy Code
from collections import deque
def max_sliding_window(nums, k):
q = deque()
result = []
for i in range(len(nums)):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
if q <= i - k:
q.popleft()
if i >= k - 1:
result.append(nums[q]])
return result
8. 拓扑排序(Kahn 算法)
应用场景:任务调度、依赖解析(DAG 图)。
时间复杂度:O(n+m)O(n+m)
pythonCopy Code
from collections import deque
def topological_sort(graph, in_degree):
queue = deque([u for u in in_degree if in_degree[u] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result if len(result) == len(graph) else []
9. 树状数组(区间求和)
应用场景:动态前缀和、单点更新。
时间复杂度:O(logn)O(logn)
pythonCopy Code
class FenwickTree:
def __init__(self, size):
self.n = size
self.tree = * (self.n + 1)
def update(self, idx, delta):
while idx <= self.n:
self.tree[idx] += delta
idx += idx & -idx
def query(self, idx):
res = 0
while idx > 0:
res += self.tree[idx]
idx -= idx & -idx
return res
10. 回溯算法(N 皇后问题)
应用场景:组合优化、排列问题。
时间复杂度:O(n!)O(n!)
pythonCopy Code
def solve_n_queens(n):
def backtrack(row, cols, diag1, diag2):
if row == n:
result.append(['.' * col + 'Q' + '.' * (n - col - 1) for col in path])
return
for col in range(n):
curr_diag1 = row - col
curr_diag2 = row + col
if col not in cols and curr_diag1 not in diag1 and curr_diag2 not in diag2:
path.append(col)
backtrack(row + 1, cols | {col}, diag1 | {curr_diag1}, diag2 | {curr_diag2})
path.pop()
result = []
path = []
backtrack(0, set(), set(), set())
return result
________________________________________
应用场景速查表
算法 典型问题类型 竞赛高频题例
二分查找 有序数据搜索、极值优化 寻找旋转数组最小值
并查集 连通性判断、图的最小生成树 朋友圈问题
滑动窗口 子数组/子串最值 最长无重复子串
动态规划(背包) 资源分配、价值最大化 0-1 背包变体
Dijkstra 算法 最短路径问题 网络延迟时间
当时做word文档好好的,复制到这边缩键有问题