目录
【题目】将单向链表按某值划分成左边小、中间相等、右边大的形式
时间复杂度
用来衡量一个算法执行所需时间的增长率的指标，评估算法的效率
先看时间复杂度，再分析不同数据样本下的实际运行指标
👀 怎么看时间复杂度？
1. 看循环结构
一层
for循环 → O(n)两层嵌套循环 → O(n²)
for循环中调用了log n的函数 → O(n log n)2. 看递归关系
如果函数调用自身，并且每次都减少一半 → O(log n)
如果函数每次调用两次自身 → O(2ⁿ)
3. 忽略常数和低阶项
时间复杂度 名称 举例 O(1) 常数时间 直接访问数组元素 O(log n) 对数时间 二分查找 O(n) 线性时间 遍历数组 O(n log n) 线性对数时间 快速排序、归并排序 O(n²) 平方时间 冒泡排序、选择排序 O(2ⁿ) 指数时间 递归解决斐波那契 O(n!) 阶乘时间 全排列、旅行商问题 一个优秀的算法 = 正确 + 高效（时间/空间）+ 可读 + 稳定 + 实用
排序O(2ⁿ)的算法：选择，冒泡，插入
选择排序
选择排序的核心是每一轮都“找最小 → 放前面”，直到整个数组有序。
怎么分析选择排序的时间复杂度？
✅ 每轮都要找一次最小值：
❗不管数组是否已排序，选择排序都要比较 n² 次！
空间复杂度分析：
选择排序只用到常数个变量（如
min_index和交换临时变量）没有额外内存开销，不用辅助数组
✅ 空间复杂度：O(1)（原地排序）
是否稳定？
选择排序不是稳定排序，因为交换可能改变相等元素的相对位置。
冒泡排序
每一轮，通过比较，交换相邻的元素，把最大的元素”冒泡“到一端，之后开始新一轮，直到整个数组都有序
怎么看冒泡排序的时间复杂度？
最坏情况（完全逆序）：需要比较和交换所有元素→ O(n²)
怎么看冒泡排序的空间复杂度？
冒泡排序是原地排序算法，只用了少量额外空间：
不需要开新数组
只交换数据时用了一个临时变量
✅ 空间复杂度是：O(1)（常数级）
插入排序
从未排序区一个一个地取出元素，插入到前面已排序区的合适位置。
就像我们打扑克牌时，一张张插牌，每次都插到已有手牌中的合适位置。
时间复杂度分析
最坏情况—>数组完全逆序，每次都移动所有元素 O(n²)
空间复杂度
插入排序是原地排序，没有使用额外数组
只用了一个变量
key临时保存值
✅ 空间复杂度是：O(1)
是否稳定？
✅ 是稳定排序 —— 相等元素的相对位置不变。
异或运算规则
相同为 0，不同为 1
找出数组中 “出现奇数次的一个数”
解法思路（基于异或）
利用异或的特性：
a ^ a = 0
0 ^ a = a异或满足交换律、结合律
所以：所有偶数次的数都会相互抵消掉，剩下的就是那个出现奇数次的数
二分排序
归并排序的基本步骤：
分解：将待排序数组分成两半。
递归排序：分别对左半部分和右半部分递归进行归并排序。
合并：将两个已排序的子数组合并成一个有序数组。
使用master求时间复杂度
Master定理简介
master一系列子问题规模等规模的递归，都可以用master公式求时间复杂度
对于形如：
的递归式，Master定理告诉我们时间复杂度取决于：
a：子问题个数
b：子问题规模缩小倍数
f(n)：合并/分解的额外时间
归并排序的递归关系
假设数组长度为 n，归并排序把数组分成两半，对左右两部分分别递归排序，再合并两个有序子数组。
递归式是：
2T(n/2)：表示递归排序左右两个子数组，每个长度是 n/2
O(n)：合并两个已排序数组所花费的时间
归并排序的时间复杂度是
【题目】在一个有序数组中找某个数是否存在
二分查找思路：
先确定数组的左右边界，通常是
left = 0，right = n-1。取中间元素
mid = (left + right) / 2。比较中间元素和目标值：
如果相等，找到了，返回索引或存在。
如果中间元素比目标大，目标只能在左半边，更新
right = mid - 1。如果中间元素比目标小，目标只能在右半边，更新
left = mid + 1。重复步骤2和3，直到
left > right，说明数组中不存在该元素。
【题目】在一个无序数组中，相邻位置一定不相等，求局部最小
思路：
用二分查找，检查中间元素
mid和它的左右邻居。有三种情况：
如果
arr[mid]是局部最小，直接返回mid。如果
arr[mid] > arr[mid - 1]，说明左边存在局部最小（因为从mid向左，元素递减趋势导致必有局部最小），向左半边查找。如果
arr[mid] > arr[mid + 1]，说明右边存在局部最小，向右半边查找。时间复杂度：
二分查找思想，每次缩小范围一半
时间复杂度是 O(logn)
归并排序的本质是“分治思想”的应用
它通过不断分解问题，将一个大数组分成越来越小的子数组，直到每个子数组只剩一个元素（自然有序），然后逐步合并这些有序的子数组，最终合成一个整体有序的数组。
【题目】什么是小和问题？
给定一个数组，定义数组中每个元素的小和为：
比它左边所有比它小的元素的和，求整个数组的小和总和。
举个例子：
数组 [1, 3, 4, 2, 5]，
1左边没有元素，小和是 03左边比它小的元素是1，小和是 14左边比它小的元素是1, 3，小和是 42左边比它小的元素是1，小和是 15左边比它小的元素是1, 3, 4, 2，小和是 10
所以总小和是 0 + 1 + 4 + 1 + 10 = 16
高效算法：利用归并排序思想
归并排序过程中，左右两个有序子数组合并时，可以统计出当前元素对小和的贡献。
核心思路：
在归并的过程中，假设左边数组是有序的，右边数组是有序的
当右边数组的某个元素
right[j]比左边数组的元素left[i]大时，left[i]对小和的贡献是left[i] * (右边剩余元素个数)累加所有贡献，得到小和总和
总结：
小和问题实质是统计数组中，每个元素左边比它小的元素的和
归并排序合并过程中，利用左右数组的有序性，高效计算小和
时间复杂度 O(nlogn)
【题目】找到数组中逆序对的数量？
什么是逆序对？
给定数组 arr，如果存在下标 i<j，且 arr[i]>arr[j]，则 (i,j)是一个逆序对。
任务是统计数组中所有逆序对的数量。
利用归并排序优化（核心思路）
归并排序中合并两个有序子数组时，可以统计逆序对数量：
左右两个子数组都是有序的
当右边子数组的某元素小于左边子数组的某元素时，说明左边当前元素及其后面所有未合并元素都和该右边元素组成逆序对。
荷兰国旗问题
“荷兰国旗问题”是一个经典的数组划分问题，其核心思想常用于快速排序、三路快排等算法中。
给定一个数组 arr 和一个目标值 pivot（例如数组中某个数），要求将数组划分成三部分：
小于
pivot的在左边等于
pivot的在中间大于
pivot的在右边
最终数组可能不完全有序，但满足三段区域划分。
思路（双指针 + 一次遍历）
总结口诀：
指针：less、index、more
小于就交换进左边、index前进
大于就交换进右边、index不动
等于就跳过
时间 & 空间复杂度
时间复杂度：O(n)（一次遍历）
空间复杂度：O(1)（原地交换）
快排
快速排序通过选一个基准数（pivot），将数组划分为小于它、等于它、大于它的三部分，然后递归地排序左右两部分。
⏱️ 快排的时间复杂度分析
| 情况 | 时间复杂度说明 | 复杂度 |
|---|---|---|
| 最好情况 | 每次 pivot 正好把数组分成两半（平衡划分） | O(nlogn) |
| 平均情况 | 大多数情况下 | O(nlogn) |
| 最坏情况 | pivot 每次都选到最大/最小值（如已排序） | O(n^2) |
通过随机选 pivot或三路快排可有效避免最坏情况。
快排的空间复杂度分析
快速排序（Quick Sort）的空间复杂度来源主要有两个部分：
✅ 1. 递归调用栈空间（主要来源）
快速排序是递归实现的，每一次划分后都会递归调用左边和右边的子数组，这就产生了调用栈的空间消耗。
最好/平均情况：每次划分比较平衡 → 树的高度是 O(logn)
🔹 空间复杂度为：O(logn)最坏情况：每次只划分出一个元素（例如数组是有序的） → 树退化成链表
🔹 空间复杂度为：O(n)
✅ 所以快排的空间复杂度主要是递归的深度决定的。
✅ 2. 原地交换空间（忽略）
快排在排序时是原地排序，不需要额外的数组来存储数据，只用了一些变量（如 pivot, i, j），这部分空间是常数级别 O(1)
堆排
一句话理解堆排序
先建堆，再不断取出堆顶元素，形成有序序列。
(利用大根堆或小根堆，每次把最大（或最小）元素取出放到数组末尾，重复这个过程完成排序。）
✅ 堆排序的步骤如下：
建堆（heapify）：
将原始数组转化为一个最大堆。
通常通过“自底向上”的方式从最后一个非叶子节点开始进行下沉操作构造堆。
排序过程：
将堆顶元素（最大值）与最后一个元素交换，然后将堆大小减1。
对新的堆顶元素进行下沉操作，维护最大堆性质。
重复此操作直到堆大小为1。
示例（升序排序）：
原始数组：
[4, 10, 3, 5, 1]
建堆：最大堆 ->
[10, 5, 3, 4, 1]交换堆顶10和最后元素1，数组变为
[1, 5, 3, 4, 10]对
[1, 5, 3, 4]重新调整为最大堆 ->[5, 4, 3, 1]继续交换堆顶与最后 ->
[1, 4, 3, 5, 10]，重复直到有序最终排序结果：
[1, 3, 4, 5, 10]
堆结构就是用数组实现的完全二叉树结构
完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
堆结构的heaplnsert与heapify操作堆结构的增大和减少优先级队列结构，就是堆结构
堆结构本质
堆是一棵完全二叉树
用数组实现，而不是链式结构
索引规律：
父节点：
(i - 1) // 2左孩子：
2 * i + 1右孩子：
2 * i + 2
堆的动态变化
插入一个元素：用
heapInsert加入末尾，然后向上调整删除堆顶元素：
把堆顶与最后一个元素交换
减少堆大小
对新堆顶执行
heapify向下调整
建立大根堆的过程？
从最后一个非叶子节点开始，向前对每个节点执行“下沉（heapify）”操作。
直到堆顶（根节点）完成为止。
初始数组：
A = [4, 10, 3, 5, 1]步骤：
Step 1：从最后一个非叶子节点开始 —— index = 1（值为10）
其左子：index 3 → 5，右子：index 4 → 1
10 已比两个子节点都大，无需调整。
Step 2：index = 0（值为4）
左子：index 1 → 10，右子：index 2 → 3
最大的是10（左子）
交换：
A[0] <-> A[1]⇒[10, 4, 3, 5, 1]继续对 index = 1 下沉：
左子：index 3 → 5，右子：index 4 → 1
5 > 4 ⇒ 交换 ⇒
[10, 5, 3, 4, 1]✅ 结果：建堆完成
[10, 5, 3, 4, 1]
堆结构是优先级队列的最佳实现方式
使用堆实现优先级队列的操作？
我们通常使用最大堆（Max-Heap）来实现优先级队列（优先级大的元素先出队）：
1. 入队（插入元素）操作：
将新元素加入到堆的末尾（数组的最后一位）。
然后通过**上浮（heapify-up ）**操作维持堆的性质：新元素和其父节点比较，如果大于父节点就交换，直到堆有序。
时间复杂度：O(log n)，因为最坏情况下需要从叶子节点移动到根节点，路径长度与树高成正比
2. 出队（取出优先级最高的元素）操作：
将堆顶元素（即最大元素）取出。
用最后一个元素填到堆顶。
然后通过**下沉（heapify-down ）**操作恢复堆的性质。
【题目】已知一个几乎有序的数组排序？
几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
堆排序（小根堆 + 滑动窗口）
具体选择：使用小根堆（heap）优化排序
✅ 小根堆的典型应用场景
1. 几乎有序数组排序
🧩 场景描述：
数组中每个元素最多乱了 k 个位置（错位不超过 k）
✅ 为什么用小根堆：
当前位置的最小元素一定在当前及后面 k 个元素中
用小根堆维护这 k+1k+1k+1 个元素，堆顶就是当前应排入的位置值
📈 时间复杂度：O(nlogk)O(n \log k)O(nlogk)，远优于常规排序
2. 数据流中的 Top K 问题（找第 K 大/小）
🧩 场景描述：
输入数据量太大，无法一次读入内存
需要随时维护前 K 大/小元素集合
✅ 为什么用小根堆（维护前 K 大）：
用大小为 K 的小根堆存放当前最大的 K 个数
堆顶是当前第 K 大元素（最小的那个）
若新来一个数 > 堆顶 ⇒ 弹出堆顶，加入新数
📈 时间复杂度：每个数最多 O(logk)O(\log k)O(logk) 操作，适合在线处理
3. 合并 K 个有序链表/数组
🧩 场景描述：
输入是 K 个升序链表（或有序文件）
输出整体升序合并结果
✅ 为什么用小根堆：
每个链表的头节点入堆，堆顶是当前最小元素
弹出堆顶后，将该元素所属链表的下一个节点放入堆
不断弹出堆顶构建最终排序
📈 时间复杂度：O(NlogK)O(N \log K)O(NlogK)，N 是总节点数，K 是链表数
不基于比较的排序都需要根据数据状况来定质
计数排序
排序考试成绩（0~100）
性别编码（0或1）
适合离散且范围小的整数数据
基数排序
给身份证号码排序（每位数字0~9）
给手机号排序
适合位数有限的数字/字符串
桶排序
浮点数分布均匀在0~1之间
适合数据均匀分布且可以划分为多个小区间
链表题
面试时链表解题的方法论
1)对于笔试，不用太在乎空间复杂度，一切为了时间复杂度2)对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
重要技巧:
1)额外数据结构记录(哈希表等) 2)快慢指针
【题目】打印两个有序链表的公共部分
【题目】给定两个有序链表的头指针head1和head2，打印两个链表的公共部分
【要求】 如果两个链表的长度之和为N，时间复杂度要求为0(N)，额外空间复杂度要求为0(1)
双指针
核心逻辑如下：
同时遍历两个链表
如果
head1.val == head2.val，则是公共部分，打印并两个指针都向后移动如果
head1.val < head2.val，则head1向后移动如果
head2.val < head1.val，则head2向后移动直到有一个链表遍历完
【题目】判断一个链表是否为回文结构
【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构。例子】1->2->1，返回true;1->2->2->1，返回true;15->6->15，返回true;1->2->3，返回false。
【例子】如果链表长度为N，时间复杂度达到0(N)，额外空间复杂度达到0(1)。
解题思路（空间 O(1) 解法）
利用快慢指针 + 链表反转，流程如下：
使用快慢指针找链表中点（slow 每次走1步，fast 每次走2步）
反转链表后半部分
从头和从尾同时向中间遍历，比较值
恢复链表结构（可选）
返回是否回文
要点 说明 时间复杂度 O(N)，遍历一次找中点，一次反转，一次比较 空间复杂度 O(1)，只使用常量指针变量 技术关键 快慢指针找中点 + 原地反转链表
【题目】将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的数pivot。节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
这是一个经典链表面试题，类似于“链表版荷兰国旗问题”
✅ 解题思路（一次遍历 + 分区链表）
核心思想是将原链表拆分成三部分：
小于 pivot 的链表（small）
等于 pivot 的链表（equal）
大于 pivot 的链表（big）
最后把这三部分按顺序拼接起来。
✅ 实现步骤
创建 3 个虚拟头节点：
small_head,equal_head,big_head遍历原链表，将每个节点按值接到相应子链表后面
拼接三个子链表（注意 null 终止）
返回新的链表头
【题目】复制含有随机指针节点的链表
【题目】一种特殊的单链表节点类描述如下
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】时间复杂度0(N)，额外空间复杂度0(1)
步骤一：复制节点并插入原链表中
A → A' → B → B' → C → C'
步骤二：设置每个复制节点的 rand 指针
对于原节点
cur，其复制节点是cur.next步骤三：拆分链表为原链表 + 新链表
还原原链表，同时提取复制链表。
【题目】两个单链表相交（无环、有环）问题
【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null
【要求】如果两个链表长度之和为N，时间复杂度请达到0(N)，额外空间复杂度请达到0(1)。
🧠 总体解题思路（分情况讨论）
将问题拆解为两个关键部分：
第一步：判断链表是否有环
使用快慢指针，返回入环节点，也就是环的起点
可使用 Floyd 判圈法（快慢指针法）
第二步：根据链表是否有环，分三类情况讨论：
✅ 三种情况分析
情况一：两个链表都无环
✅ 如果相交，最后一个节点一定相同（尾节点地址相等）
✅ 解法：让两个指针走完相同长度，找第一个相交点
情况二：一个有环，一个无环
❌ 不可能相交（一个是无限的，一个有限）
情况三：两个链表都有环
分两种子情况：
两个环的入口相同：在环外相交
直接在入口前部分找相交点（同无环处理）
两个环的入口不同：
从 loop1 出发转一圈，如果能遇到 loop2 ⇒ 相交，返回任一环入口
否则 ⇒ 不相交
二叉树的相关概念及其实现判断
如何判断一颗二叉树是否是搜索二叉树?
方法一：中序遍历是否为严格递增序列
中序遍历（左 -> 根 -> 右）在 BST 上会得到一个严格递增序列。
方法二：递归判断每个节点是否在合法范围内
根节点可以是任意值
左子树的所有节点必须
< 根节点值右子树的所有节点必须
> 根节点值对每个子树递归设置合法的值范围
[min, max]
如何判断一颗二叉树是完全二叉树?
一棵完全二叉树满足以下两个条件：
除了最后一层，其它所有层的节点数都达到最大（即都被填满）；
最后一层的所有节点从左到右依次排列，不能有空缺。
✅ 判断思路（使用 BFS 宽度优先遍历）
我们按照 层序遍历（从左到右） 来检查：
步骤：
使用队列进行层序遍历；
对每个节点：
如果遇到某个节点：
有右孩子但没有左孩子 → 不是完全二叉树；
一旦遇到第一个不是两个孩子都存在的节点，后续节点都必须是叶子节点；
如果遍历过程中违反上述条件，说明不是完全二叉树。
如何判断一颗二叉树是否是满二叉树?
✅ 满二叉树的定义
一棵二叉树是满二叉树，当且仅当：
每一个节点要么没有子节点（即是叶子），要么正好有两个子节点；
并且所有叶子节点都在同一层；
等价于：节点总数 = 2^h - 1，其中
h是树的高度。✅ 判断方法
方法一：递归遍历所有节点，计算高度和节点数，再判断
2^h - 1 == 节点总数
实现二叉树的先序、中序、后序遍历
public void PreOrderRecursive(TreeNode root)
{
if (root == null) return;
Console.Write(root.val + " ");
PreOrderRecursive(root.left);
PreOrderRecursive(root.right);
}
【题目】如何完成二叉树的宽度优先遍历（BFS）
宽度优先遍历是按照“从上到下，从左到右”的顺序依层访问节点：
常见题目:求一棵二叉树的宽度
如何判断一颗二叉树是否是平衡二叉树?(二叉树题目套路)
任何一个节点的左右子树高度差 ≤ 1
判断思路 —— 「树型DP」套路（自底向上）
使用递归后序遍历的方式，边遍历边判断。
核心思想：
每个子树返回两个信息：
isBalanced：是否是平衡树
height：该子树的高度当前节点只需要看左右子树这两个信息是否满足：
if 左右子树都是平衡的 && |左高 - 右高| ≤ 1
⇒ 当前子树是平衡的
项目 复杂度 时间复杂度 O(N) 空间复杂度 O(H)，H 为树高（递归栈） 二叉树套路（树型 DP）
每个子树需要传回信息（高度 + 是否平衡）
自底向上（后序遍历）
每层做常数判断 ⇒ O(N) 效率
KMP算法
该算法可以高效的判断一个字符串是否包含另一个字符串
KMP 的核心优势在于：
利用已经匹配的前缀信息，避免主串回退；
在模式串中进行“智能右移”，提升效率。
✅ 步骤一：构建 next[] 数组（前缀函数）
🔍 目的：
记录模式串中每个位置之前的最长相等的前后缀长度，用于失配时跳过重复比较。
📌 定义：
next[i]表示：P[0:i]子串中，最长的“前缀 = 后缀”的长度。💡 例子：
模式串
P = "ababc"
那么next = [0, 0, 1, 2, 0]✅ 步骤二：用 next[] 进行匹配
思路：
在主串
S中扫描字符，每次比较模式串P的当前字符，遇到不匹配时，利用next[]直接跳过部分字符。完整示例讲解
主串：S =
"ababcabcacbab"模式串：P =
"abcac"
构建 next：
P: a b c a c
idx: 0 1 2 3 4
next = [0, 0, 0, 1, 2]
匹配过程：
从主串第 2 位开始成功匹配：
匹配成功，返回下标 5。
