数组与链表
5 个知识点数组、链表、动态数组、双向链表的概念与实现
栈与队列
5 个知识点栈、队列、循环队列、单调栈、单调队列
栈的概念与实现——像叠盘子一样存放数据
栈是一种“后进先出”的数据结构,就像一摞盘子,后放上去的盘子先被拿走。本文用生活例子讲解栈的原理,并给出C++和Python的完整实现。
队列的概念与实现——像排队打饭一样处理数据
队列是一种“先进先出”的数据结构,就像同学们排队打饭,先来的人先打到饭。本文用生活例子讲解队列原理,并给出C++和Python的完整实现。
循环队列——让数组空间不再浪费
循环队列通过将数组首尾相接,避免普通数组队列的“假溢出”问题,实现空间的高效利用。本文用生活例子和ASCII图讲解循环队列原理,并给出C++和Python实现。
单调栈——让数据保持单调有序的利器
单调栈是一种特殊的栈,它保证了栈内元素从栈底到栈顶保持单调递增或递减,常用于解决“下一个更大元素”等经典问题。本文用生活例子讲解原理,并给出C++和Python实现。
单调队列与滑动窗口——在移动窗口中快速找到最值
单调队列结合了队列的先进先出和栈的单调性,常用于在滑动窗口中高效维护最值。本文用生活例子讲解原理,并给出C++和Python实现。
哈希表
5 个知识点哈希表原理、哈希函数、冲突处理、应用场景
树与二叉树
5 个知识点树的定义、二叉树性质与遍历、完全二叉树、树的存储
树的定义与基本概念
用文件夹和家族树的例子,带你认识树这种非线性结构,理解节点、根、叶子、父子关系等核心术语,并给出C++和Python的节点创建代码。
二叉树的性质与存储
用“左孩子、右孩子”规则介绍二叉树,推导出二叉树的重要性质(节点数、层数关系),并讲解顺序存储和链式存储两种实现。
二叉树的遍历(前序、中序、后序、层序)
用走迷宫和拍集体照的有趣比喻,学会四种方式遍历一棵二叉树,并给出递归和迭代两种实现代码。
完全二叉树与数组存储
通过“填格子”的比喻,讲解完全二叉树如何用连续的数组完美存放,并实现父子下标的快速计算,附带堆的初步认识。
树的常见表示方法(邻接表、父亲表示法等)
介绍除孩子表示法外多种树的存储方式,包括父亲表示法、孩子表示法、孩子兄弟表示法、邻接表,以及它们各自的优缺点。
堆
5 个知识点堆的概念、二叉堆实现、堆排序、优先队列
堆的概念与性质(大根堆、小根堆)
堆是一种特殊的完全二叉树,常用于快速获取最大值或最小值。本文通过生活中的例子介绍大根堆和小根堆的概念、性质,并用C++和Python实现简单堆结构。
二叉堆的实现(上浮与下沉操作)
详细讲解二叉堆中最重要的两个操作——上浮(sift up)和下沉(sift down),包括手动模拟过程、边界条件处理,并给出完整C++和Python代码。
堆排序
堆排序是一种利用堆数据结构进行排序的高效算法。本文讲解堆排序的原理、建堆过程、排序步骤,并给出C++和Python实现。
优先队列(STL priority_queue)
介绍C++ STL中的priority_queue和Python中的heapq模块,它们都基于堆实现。学习如何快速使用优先队列解决最大值/最小值问题。
对顶堆与堆的经典应用
介绍对顶堆(双堆)技巧以及堆在动态中位数、贪心问题、图论等经典场景中的应用,拓宽对堆的理解。
并查集
5 个知识点并查集概念、路径压缩、按秩合并、带权并查集
二叉搜索树
5 个知识点BST的查找插入删除、退化问题、AVL树、Treap
二叉搜索树的概念与查找
用图书馆找书的例子引入二叉搜索树,讲解其“左小右大”的特点和快速查找的原理,并给出C++和Python的完整实现。
二叉搜索树的插入与删除
用整理书架的例子讲解BST的插入和删除操作,包括删除的三种情况(无孩子、一个孩子、两个孩子)及用前驱或后继替代的方法,并给出完整代码。
BST的退化问题与平衡思想
用排队买票的例子说明按顺序插入数据会导致BST退化为链表,引出平衡树的思想,即通过旋转等操作让树保持矮胖。
AVL树与旋转操作简介
用叠积木保持稳定的例子引入AVL树,讲解平衡因子、左旋和右旋,以及插入后的四种失衡情况(LL、RR、LR、RL)的调整方法,并给出简化实现代码。
Treap(树堆)入门
用扔硬币决定书架位置的有趣比喻引入Treap,讲解它如何结合二叉搜索树和堆(随机优先级),通过旋转维持堆性质,并给出完整代码。
树状数组
5 个知识点lowbit原理、单点/区间操作、逆序对、二维树状数组
树状数组的原理(lowbit运算)
树状数组是一种高效维护前缀和的数据结构,它的核心思想是利用「lowbit」运算来组织数据的存储和查询,就像给班级同学分组管理一样,每个小组长只负责管理自己身后的几个同学。
树状数组的单点修改与区间查询
学习如何用树状数组实现单点修改(修改数组中的一个元素)和区间查询(求任意一段连续子数组的和),这是树状数组最基础的应用。
树状数组的区间修改与区间查询
利用差分思想将区间修改问题转化为两个树状数组上的单点更新和前缀和查询,实现 O(log n) 的区间加法和区间求和。
树状数组求逆序对
利用树状数组统计数组中的逆序对数量(即满足 i < j 且 a[i] > a[j] 的数对),通过离散化和顺序插入来高效求解。
二维树状数组简介
将树状数组的思想推广到二维空间,用于快速维护二维矩阵的“前缀和”和支持单点修改、子矩阵查询。
线段树
5 个知识点线段树构建查询、区间修改、懒标记、权值线段树
字典树
5 个知识点Trie的实现、01-Trie、AC自动机、可持久化Trie
字典树(Trie)的概念与实现
字典树是一种利用字符串公共前缀来高效存储和查询单词的树形数据结构,就像一本神奇的“单词速查手册”。
Trie的插入、查找与遍历
深入学习字典树的核心操作:插入、精确查找、前缀查找以及树的深度优先遍历,并用代码实现一个完整的自动补全功能。
01-Trie与异或极值问题
01-Trie是一种专门处理二进制整数的高效数据结构,利用贪心思想在Trie上寻找最大异或值,常用于解决“最大异或对”等经典问题。
AC自动机(Trie上的KMP)
AC自动机是在字典树基础上加入失配指针的一种多模式匹配算法,可以一次性在一段文本中查找多个关键词,像超级“查找替换”工具。
可持久化Trie简介
可持久化Trie允许我们访问插入任意个单词后字典树的历史版本,解决需要查询“在某个时间点之前”或“第i次插入前”等前缀信息的问题。
字符串算法
5 个知识点字符串哈希、KMP、Manacher、后缀数组
高级数据结构
6 个知识点ST表、LCA、树链剖分、主席树、分块、LCT
ST表(Sparse Table)与RMQ
用预处理和倍增思想,在O(1)时间内回答区间最大值/最小值查询,就像提前准备好所有可能长度的尺子。
最近公共祖先(LCA)与树上倍增
把树看作家族谱,用“超级跳”快速找到两个人的共同祖先,就像电梯直接上到高层楼。
树链剖分(HLD)简介
把树切成几条“重链”,让树上路径问题变成区间问题,用线段树等数据结构快速处理。
可持久化线段树(主席树)
给每个历史版本都保存一颗线段树,因为只修改了路径上的log n个节点,所以能共享大部分节点。
分块思想与莫队算法简介
把数据分成若干块,块内暴力,块间预处理,平衡复杂度;莫队算法则通过离线排序让区间移动总距离最小。
动态树(Link-Cut Tree)简介
用Splay树维护森林上的路径,支持连边、断边和路径查询,让树动起来。