Python 数据结构与语法速查笔记

文章总览YuanDaiMa2048博客文章总览 查看完整专栏LeetCode基础算法专栏专栏文章点击阅读Python 数据结构与语法速查笔记点击阅读哈希表基础原理与题目说明点击阅读双指针基础原理与题目说明点击阅读滑动窗口基础原理与题目说明点击阅读队列与单调队列基础原理与题目说明点击阅读二分查找基础原理与题目说明点击阅读矩阵基础原理与题目说明点击阅读堆(优先队列)基础原理与题目说明点击阅读链表基础原理与题目说明特别说明本文为个人的 LeetCode 刷题与学习笔记内容仅供学习与交流使用禁止转载或用于商业用途。需要强调的是文中的题目解法不一定是最优解可能存在时间或空间复杂度的进一步优化空间主要目的是分享个人的解题思路与逻辑实现仅供参考。笔记内容为个人理解与总结可能存在疏漏或偏差欢迎读者自行甄别并交流探讨。Python 数据结构与语法速查笔记日常以Python开发或刷题时熟练掌握并区分各种数据结构的底层表现和正确语法至关重要。本文对Python中常用的数据结构进行了统一格式的整理方便对比与记忆。一、栈 (Stack) - 使用list特点后进先出LIFO。Python中没有专门的Stack类直接使用列表[]即可实现栈的功能。适用场景括号匹配、单调栈求下一个更大元素、DFS深度优先搜索迭代实现。️ 核心操作速查操作类型代码语法时间复杂度说明创建/初始化stack []O(1)直接初始化为空列表加入 (Push)stack.append(val)O(1)在列表末尾添加元素压栈删除 (Pop)val stack.pop()O(1)弹出并返回列表最后一个元素出栈访问/查看top stack[-1]O(1)查看栈顶元素注意需先判空if stack:⚠️ 注意不要滥用stack.insert(0, val)或stack.pop(0)来模拟栈底操作这会导致 O(N) 的时间复杂度请始终在尾部进行append和pop。二、队列与双端队列 (Queue / Deque)特点先进先出FIFO或 双端操作。不要用list模拟队列因为list.pop(0)是 O(N) 复杂度建议使用标准库的collections.deque。适用场景BFS广度优先搜索、滑动窗口、维护区间状态。️ 核心操作速查操作语法时间复杂度说明创建/初始化deq deque()O(1)需from collections import deque加入队尾deq.append(x)O(1)常规入队尾部添加加入队首deq.appendleft(x)O(1)双端队列特有头部添加删除队首deq.popleft()O(1)常规出队FIFO弹出头部删除队尾deq.pop()O(1)双端队列特有弹出尾部三、哈希表 (Hash Table)哈希表通过键值对快速存取平均时间复杂度为 O(1)。在 Python 中分为四种常用类型dict、set、Counter、defaultdict。在 Python 底层collections.Counter和collections.defaultdict本质上都是继承自 dict 的子类。因此在执行删除操作时候在字典中用的del和pop()完全可以直接用在这两个数据结构上。del 和 pop 的主要区别在于del hash_dict[key]直接在内存中删除该键值对。但是如果这个 key 在字典中不存在它会无情地抛出 KeyError 报错。val hash_dict.pop(key, None)不仅会删除该键值对还会把被删除的值返回给你。更重要的是加上第二个参数如 None后如果 key 不存在它不会报错而是返回 None这可以避免很多因为边界条件引起的意外崩溃。1. 字典 (dict)特点标准的键值对Key-Value映射。操作类型代码语法说明创建/初始化hash_dict {}初始化空字典加入/更新hash_dict[key] val若 key 存在则覆盖不存在则创建删除val hash_dict.pop(key, None)安全删除并返回值。不存在时返回设定的 None访问/查询val hash_dict.get(key, 0)安全访问。不存在时返回设定的默认值 0不报错2. 集合 (set)特点无序且元素唯一的集合主要用于去重和快速查找。操作类型代码语法说明创建/初始化nums_set set()初始化空集合注意不能用{}加入nums_set.add(val)添加单个元素若已存在则忽略删除nums_set.discard(val)安全删除。若元素不存在也不会报错访问/查询if val in nums_set:O(1) 判断元素是否存在如果这个元素在集合中不存在使用nums_set.remove(val)会抛出 KeyError 报错而nums_set.discard(val)则什么都不会发生所以 discard 更“安全”省去了先判断if val in nums_set:的步骤。3. 计数器 (collections.Counter)特点自带统计功能的哈希表自动计算频率。操作类型代码语法说明创建/初始化freq Counter(nums)传入列表等迭代器返回{元素: 频次}字典加入/修改freq[key] 1增加频次键不存在时默认从 0 开始加高级操作freq.most_common(k)返回出现频次最高的 k 个元素[(val, freq), ...]4. 默认字典 (collections.defaultdict)特点访问不存在的键时会自动创建默认值适合分组或构建邻接表。操作类型代码语法说明创建(列表默认)adj defaultdict(list)默认值为空列表[]加入/修改adj[node].append(neighbor)直接 append无需判断node键是否已存在创建(数字默认)count defaultdict(int)默认值为数字0四、优先队列 / 堆 (Heap)特点底层是一棵完全二叉树Python 内置的是小顶堆根节点最小。基于普通的list实现。适用场景动态求极值、Top K 问题。️ 核心操作速查操作语法时间复杂度说明创建/初始化heap []O(1)底层载体也是普通列表原址建堆heapq.heapify(nums)O(N)将无序列表直接原地转化为小顶堆加入 (Push)heapq.heappush(heap, x)O(log N)将 x 放入堆并自动调整维持堆性质删除 (Pop)heapq.heappop(heap)O(log N)弹出并返回堆顶最小元素查看堆顶heap[0]O(1)索引 0 永远是堆顶极小值大顶堆技巧heappush(heap, -x)-存入时取负数弹出时再取负数恢复五、有序数组数组排序 (sort与sorted)操作类型代码语法时间复杂度说明原地排序arr.sort()O(N log N)直接在原列表上修改无返回值。可加reverseTrue实现降序生成新排序列表new_arr sorted(arr)O(N log N)不改变原列表返回一个全新的已排序列表六、自定义数据结构 (链表与树)在刷题如 LeetCode中链表和树通常需要自己定义类。1. 单链表节点 (Linked List)classListNode:def__init__(self,val0,nextNone):self.valval self.nextnext# 创建与遍历演示headListNode(1)head.nextListNode(2)currheadwhilecurr:print(curr.val)currcurr.next2. 二叉树节点 (Binary Tree)classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightright# 创建与初始化演示rootTreeNode(1)root.leftTreeNode(2)root.rightTreeNode(3)数据结构在 CPython 底层的本质[] 列表 —— 本质动态数组 (Dynamic Array)涵盖结构普通列表、栈 (Stack)、堆 (Heap / heapq)、有序数组 (bisect)。原理解析它不是链表而是一块连续的内存空间里面存的是指向实际对象的指针。当数组满了它会申请一块更大的新内存把旧数据拷贝过去过度分配机制。致命缺陷因为是连续内存如果你删除了第 0 个元素pop(0)后面的所有元素都要往前挪动一位时间复杂度为 O(N)。但尾部的 append 和 pop() 只需操作指针所以是 O(1)。collections.deque (双端队列)涵盖结构队列 (Queue)、滑动窗口。专门为了解决上述 [] (动态数组) 头部操作极慢的问题。原理解析底层结构是块状双向链表 (Doubly Linked List of Blocks)。它由一个个固定大小的“块”组成块之间用双向链表连接。在头部或尾部添加/删除元素时只需在最边缘的块操作或新建块不需要移动其他元素实现严格的 O(1)。{} 字典/集合 —— 本质哈希表 (Hash Table)涵盖结构字典 (dict)、集合 (set)、计数器 (Counter)、默认字典 (defaultdict)。原理解析通过哈希函数计算键Key的索引位置实现 O(1) 的极速存取。Python 使用“开放寻址法”解决哈希冲突。注意{} 默认是空字典。空集合必须用 set()。{“a”: 1} 是字典 {1, 2} 是集合。() 元组 —— 本质静态只读数组涵盖结构不可变序列。原理解析一旦创建内存大小和内容就完全固定不支持任何增删改操作。用途正因为其不可变可哈希只有 () 可以作为 {} (字典/集合) 的 Key而 [] 绝对不行例如用 (x,y) 记录网格访问状态。 综合记忆口诀栈要后出只用[]只调append()和pop()。队要先出引deque尾进append()头出popleft()。频率/哈希去重找set映射找dict防越界找defaultdict统计找Counter。最值/Top K引heapq默认小堆取大变负操作带前缀heappush/heappop。