数据结构与算法
2025-11-10 17:03:26 0 举报AI智能生成
这篇文章将提供深入浅出的解释，辅以适当的编程示例，使用易于理解的语言，并加入注释来增强可读性，旨在为初学者或有兴趣深入了解算法和数据结构的读者提供清晰且详尽的指导。
作者其他创作
大纲/内容
数据结构
定义
理论教学
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。强调 “关系”，突出逻辑结构层面。
工程实践
数据结构是在计算机中组织、存储和管理数据的一种方式，使得数据可以高效地被访问和修改。强调 “方式/效率”，突出存储和操作的实现层面。
两者结合
数据结构是由数据元素及其相互关系组成的集合，同时包括在这些数据上执行操作的函数或方法。
分类
逻辑结构（Logical Structure）
集合结构 (Set Structure)
集合（Set）
哈希集合 (HashSet)
有序集合 (TreeSet)
多重集合 (Multiset)
字典 / 映射 (Dictionary / Map)
哈希表 (HashMap)
有序映射 (TreeMap)
多重映射 (Multimap)
LRU / LFU 缓存 (LRU / LFU Cache)
其他
布隆过滤器 (Bloom Filter)
Cuckoo 哈希 (Cuckoo Hashing)
线性结构 (Linear Structure)
字符串(String)
静态字符串 (Flat String)
动态字符串 (Dynamic String)
特殊实现（如 Rope、Gap Buffer）
例题
字符串匹配算法
BF算法
时间复杂度为O(m*n)
KMP算法 (Knuth-Morris-Pratt)
时间复杂度为O(m+n)
242. 有效的字母异位词
定义一个长度为26的数组，填充0， s 中所有字母将对应数组中的值加1，t 中的所有字母减1，最后判断数组是否都为0
LCR 122. 路径加密（替换空格）
split join / replace 正则替换 / 库函数 replaceAll / 循环
时间：O(n)
空间：O(n)
在 JavaScript 中，字符串是不可变（immutable）的，这意味着每次字符串拼接（如 result += char）实际上都会创建一个新的字符串，而不是在原有字符串上直接修改。最坏情况下：如果原字符串 path 没有 .（如 "abc"），则 result 会逐步增长为长度 n 的新字符串，期间共产生 n 次拼接，临时字符串占用的总空间是 O(n^2)（1 + 2 + 3 + ... + n）。现代 JavaScript 引擎（如 V8）会对连续字符串拼接进行优化（类似 Java 的 StringBuilder），使得实际空间复杂度接近 O(n)
LCR 169. 招式拆解 II（第一个只出现一次的字符）
哈希存储（如果字符已存在，计数+1，否则初始化为1；循环Map，判断 values 是否为1）
时间：O(n)
空间：O(1)
Map 最多存储 26 个小写字母的计数，与输入规模 n 无关，因此是 O(1)。
LCR 182. 动态口令（左旋转字符串）
substring / 列表遍历拼接
时间：O(n)
其中 n 是字符串 password 的长度。切片操作的时间复杂度为 O(n)，因为需要复制字符串的部分内容。
空间：O(n)
因为切片操作会创建新的字符串，存储原字符串的部分内容，最坏情况下需要与原字符串相同的空间。
415. 字符串相加
核心
从最低位开始计算（即字符串的末尾），使用双指针 l1 和 l2 遍历两个数字字符串。
维护进位 carry，每次计算当前位的和（包括进位），更新进位值，并将个位数存入结果数组。
最终反转结果数组，因为计算顺序是从低位到高位。
维护进位 carry，每次计算当前位的和（包括进位），更新进位值，并将个位数存入结果数组。
最终反转结果数组，因为计算顺序是从低位到高位。
方法
双指针倒序遍历：初始化指针指向字符串末尾，逐步前移，确保所有位数被处理。
进位处理：通过 sum >= 10 判断是否进位，carry = sum / 10（实际简化为 1 或 0）。
边界处理：当两字符串长度不同时，短的数字高位补 0；最终若仍有进位，需添加到结果（如 "999" + "1" = "1000"）。
结果拼接：用数组存储每位结果，最后反转并拼接成字符串，避免频繁字符串操作的低效问题。
进位处理：通过 sum >= 10 判断是否进位，carry = sum / 10（实际简化为 1 或 0）。
边界处理：当两字符串长度不同时，短的数字高位补 0；最终若仍有进位，需添加到结果（如 "999" + "1" = "1000"）。
结果拼接：用数组存储每位结果，最后反转并拼接成字符串，避免频繁字符串操作的低效问题。
时间：O(max(n, m))
其中 n 和 m 分别是 num1 和 num2 的长度。我们需要遍历较长的字符串的每一位。
空间：O(max(n, m))
结果数组的长度最多为 max(n, m) + 1（如果有进位）
43. 字符串相乘
核心
两层遍历+调用 字符串相加 的代码
注意点
carry 别忘记+
要记得补0
数组 (Array)
动态数组 (ArrayList)
环形数组 (Circular Array)
例题
数组中重复的数字
核心
用hash存入已经存在的
队列 (Queue)
普通队列 (Queue)
循环队列 (Circular Queue)
双端队列 (Deque)
优先队列 (Priority Queue)
例题
239. 滑动窗口最大值
双端队列 q 里按从大到小存着“有潜力”当老大的元素位置，最前面那个就是当前窗口的老大
栈 (Stack)
顺序栈 (Array-based Stack)
链式栈 (Linked Stack)
例题
232. 用栈实现队列
LCR 125. 图书整理 II（用两个栈实现队列）
核心
两个只能用 push 和 pop 的数组（栈）实现队列的 appendTail（其实就是 push） 和 deleteHead（其实就是 shift）
方法
appendTail 的时候，把参数塞到 栈1 就可以了
deleteHead 有以下几种情况：
- 栈1 为空，栈2 也为空，return -1
- 栈2 有成员，return 栈2.pop()
- 栈2 为空，栈1 有成员，则通过循环，把 栈1 倒序到 栈2 中，然后 return 栈2.pop()
- 栈1 为空，栈2 也为空，return -1
- 栈2 有成员，return 栈2.pop()
- 栈2 为空，栈1 有成员，则通过循环，把 栈1 倒序到 栈2 中，然后 return 栈2.pop()
LCR 147. 最小栈（包含min函数的栈）
核心
创建两个栈，一个栈是主栈 stackstack，另一个是辅助栈 minStackminStack
方法
当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
20. 有效的括号
739. 每日温度
链表 (Linked List)
单向链表 (Singly Linked List)
双向链表 (Doubly Linked List)
循环链表 (Circular Linked List):
例题
206. 反转链表
92. 反转链表 II
25. K 个一组翻转链表（字节2025.3.20一面、腾讯2025.4.28一面）
876. 链表的中间结点
141. 环形链表
143. 重排链表（2023.3.23 腾讯一面、2024.4.3 美团一面，2025.4.2 temu二面、2025.05.28 作业帮社招一面）
234. 回文链表
83. 删除排序链表中的重复元素
82. 删除排序链表中的重复元素 II
203. 移除链表元素
3217. 从链表中移除在数组中存在的节点
2487. 从链表中移除节点
LCR 123. 图书整理 I（从尾到头打印链表）
核心
利用栈的“后进先出”特性反转输出顺序。
方法
顺序遍历链表，节点值存入数组；
反向返回数组（或直接使用 unshift 插入）。
LCR 154. 复杂链表的复制
核心
利用 哈希表 建立原节点与新节点的一对一映射，通过两次遍历完成复制
方法
首次遍历：顺序克隆每个节点并存入 Map（仅复制值，不处理指针）；
二次遍历：通过 Map 快速查询，为新节点正确设置 next 和 random 指针（自动处理 null 边界），最终返回 map.get(原头节点) 即复制后的链表头。
LCR 023. 相交链表
核心
双指针通过路径互补消除链表长度差，使两指针必然同步到达交点（或同时走完）。
路径设计：
指针 A 走：链表A → 链表B
指针 B 走：链表B → 链表A
指针 A 走：链表A → 链表B
指针 B 走：链表B → 链表A
长度抵消：
设链表A独有部分长为 a，链表B独有部分长为 b，公共部分长为 c。
A 的总路径：a + c + b
B 的总路径：b + c + a
路径等长 → 两指针必定在交点相遇（或同时走到 null）。
设链表A独有部分长为 a，链表B独有部分长为 b，公共部分长为 c。
A 的总路径：a + c + b
B 的总路径：b + c + a
路径等长 → 两指针必定在交点相遇（或同时走到 null）。
方法
指针 A 和 B 分别从 headA 和 headB 出发；
每次同步移动一步，到达末尾时切换链表头部继续；
终止条件：两指针指向同一节点（交点）或同时为 null（无交点）。
LCR 141. 训练计划 III（反转链表）
核心
通过调整节点指针方向，将链表从「顺序」变为「逆序」，无需额外空间，直接修改原链表关系。
方法
初始化指针：
pre = null（标记已反转部分的头节点）
cur = head（当前待反转节点）
pre = null（标记已反转部分的头节点）
cur = head（当前待反转节点）
遍历反转：
暂存 cur.next（防止断链）；
反转指针：cur.next = pre（当前节点指向已反转部分）；
移动指针：pre = cur，cur = 暂存节点（推进至下一节点）。
暂存 cur.next（防止断链）；
反转指针：cur.next = pre（当前节点指向已反转部分）；
移动指针：pre = cur，cur = 暂存节点（推进至下一节点）。
终止条件：当 cur 为 null 时，pre 即为新链表头节点。
LCR 025. 两数相加 II
核心
模拟加法运算，注意进位和位数对齐。
方法
反转两链表（低位对齐）；
逐位相加，记录进位；
个位数：sum % 10
进位：Math.floor(sum / 10)
反转结果链表（恢复原顺序）。
21. 合并两个有序链表
核心
通过比较节点值，按顺序串联成新链表。
方法
递归
迭代
初始化哑节点（dummy）简化头节点处理；
循环比较 l1 和 l2，将较小节点接入新链表；
剩余链表直接拼接（无需继续比较）。
注意：若用递归，需注意栈空间限制（链表过长可能溢出）
LCR 077. 排序链表
核心
分治思想，递归合并有序链表。
方法
快慢指针找中点，分割链表为两部分；
递归排序左右子链表；
合并两个有序链表。
86. 分隔链表
树形结构 (Tree Structure)
基本树结构 (Basic Tree)
二叉树 (Binary Tree)
完全二叉树 (Complete Binary Tree)
满二叉树 (Full Binary Tree)
平衡二叉树 (AVL Tree, Red-Black Tree)
搜索树 (Search Tree)
二叉搜索树 (Binary Search Tree, BST)
B树 (B-Tree)、B+树 (B+ Tree)、B树 (B Tree)
Trie 树 (Trie Tree, Prefix Tree)
堆 (Heap)
二叉堆 (Binary Heap)
d 叉堆 (d-ary Heap)
斐波那契堆 (Fibonacci Heap)
高级树结构 (Advanced Tree Structures)
线段树 (Segment Tree)
树状数组 (Fenwick Tree)
AVL 树 (AVL Tree)、红黑树 (Red-Black Tree)、Treap（随机二叉搜索树）
自平衡树 (Self-balancing Tree)
范围树 (Range Tree)、区间树 (Interval Tree)
图形结构 (Graph Structure)
无向图 (Undirected Graph)
有向图 (Directed Graph)
带权图 (Weighted Graph)
无权图 (Unweighted Graph)
物理结构
（Physical Structure / Storage Structure）
（Physical Structure / Storage Structure）
顺序存储（Sequential Storage）
把逻辑上相邻的数据存储在物理位置上相邻的存储单位里，用物理位置上的相邻来体现逻辑上的相邻，此种存储结构的又在于节省了存储空间，因为分配给数据的存储单元完全用于了数据的存储，数据之间的逻辑关系没有占用存储空间，可以实现对数据的随机存取，每个节点对应一个序号，由这个序号可以计算出数据的存储地址，缺点在于不变于数据的修改，对数据的插入和删除可能要移动一系列的数据。
字符串（String）
数组（Array）
基于数组实现的栈（Stack）、队列（Queue）
堆（Heap）
数组（Array）
基于数组实现的栈（Stack）、队列（Queue）
堆（Heap）
链式存储（Linked Storage）
逻辑上相邻的两个数据元素不一定在物理位置上也要相邻，数据元素之间的相邻是用添加的指针来标识的，优点在于由于不要求在物理上的相邻，所以在进行插入，删除等时，只需要改变相邻节点的指针域，不必移动数据的位置，相对于顺序结构，链式的缺点在于存储空间利用率太低，因为存储数据的一部分单元用于了存储数据之间的逻辑关系，由于相邻的节点在物理位置上不一定相邻，所以不能进行随机存在。
链表（Linked List）
基于链表实现的栈（Stack）、队列（Queue）
树（Tree）
图（Graph）
基于链表实现的栈（Stack）、队列（Queue）
树（Tree）
图（Graph）
索引存储（Indexed Storage）
该结构在存储数据元素的同时，还建立了一个附加的索引表，索引表中的每一项称为索引项(关键字，地址），关键字唯一标识一个数据元素 ，地址是指向数据元素的指针，采用了索引的存储结构可以所及存取数据元素，在进行插入，删除等时，只需要移动相应索引表中的地址，不必移动数据，故而大大提高了数据的查找速度，缺点在于添加了索引表，降低了存储空间的利用率
数据库索引（B+树）
倒排索引（搜索引擎）
倒排索引（搜索引擎）
散列（哈希）存储（Hashing Storage）
就是根据数据元素的关键字通过哈希函数计算出一个数值用做数据元素的存储地址，优点在于查找速度快，只需要给出关键字可立即计算出该数据元素的地址 特点是指存储数据元素不存储数据之间的逻辑关系，只适合进行快速查找和插入的场合
哈希表（Hash Table）
集合（Set）
映射（Map）
集合（Set）
映射（Map）
算法
定义
是解决特定问题或完成特定任务的一系列明确、有限的步骤
算法的优劣通过其时间和空间复杂度来衡量
算法的优劣通过其时间和空间复杂度来衡量
传统算法
1. 搜索和排序
搜索（Search）
概念
无序数据
有序数据
二分查找 (Binary Search)
核心
在一个具有单调性或可分性的问题空间中，通过不断地将搜索范围对半分割，利用中间点的判断来排除一半的搜索空间，从而高效地逼近或找到目标解的方法。
如果找的是第一个大于target的数, 判断条件就是nums[mid] > target，如果是找第一个大于等于target的数，那么判断条件就是nums[mid] >= target，最后返回left（因为在染色的过程中，符合条件的值在右侧，也就是right区域，那么在不符合循环条件那一刻时，left进入的正好是右侧蓝色区的第一个值）
如果找的是第一个小于target的数，判断条件就是nums[mid]< target，如果是找第一个小于等于target的数，那么判断条件就是nums[mid]<= target，最后返回right（因为染色过程中，符合条件的值在左侧，也就是left区域，那么不符合循环规则那一刻时，right进入的刚好是左侧蓝色区域的最后一个值）
如果找的是第一个小于target的数，判断条件就是nums[mid]< target，如果是找第一个小于等于target的数，那么判断条件就是nums[mid]<= target，最后返回right（因为染色过程中，符合条件的值在左侧，也就是left区域，那么不符合循环规则那一刻时，right进入的刚好是左侧蓝色区域的最后一个值）
时间复杂度 O(logn)
例题
34. 在排序数组中查找元素的第一个和最后一个位置
2529. 正整数和负整数的最大计数
LCR 172. 统计目标成绩的出现次数
核心
查找数字的左右的两个边界
LCR 173. 点名
LCR 128. 库存管理 I
2300. 咒语和药水的成功对数
时间复杂度 O(log(n))
每进行一次迭代时会将搜索区域一分为二
哈希
本质
通过预存储数据（空间开销），将查找/插入时间从O(n)降至O(1)
例题
1. 两数之和
补数是否在哈希表中，存在则返回；不存在则存入当前数及其索引
时间 O(n)
空间 O(n)
空间 O(n)
49. 字母异位词分组
初始化数组为 26 个 0，对应字母的数量，(字母-a)++。将该数组作为对象的 key，如果存在则 push，不存在设置为 [word]
时间 O(nk)：元素数量（n），单个元素的大小（k）
空间 O(nk)：
空间 O(nk)：
注意点
Object 的 key 会自动调用 toString()，但 Map 必须显式处理 key，直接使用数组会失败（因为引用不同），需转为字符串。
使用 Map 可以 通过 [...map.values()] 或 Array.from(map.values())，展开为数组
使用 Object 可以使用 Object.values(obj)
使用 Object 可以使用 Object.values(obj)
128. 最长连续序列
注意点
使用 Set 去重，同时通过 new Set(nums)，快速生成哈希表, 可使用 for of 遍历 Set
树形结构
二叉树查找
广度优先搜索 (BFS)
深度优先搜索 (DFS)
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
AVL树查找
B-树
B+树
图结构
Dijkstra算法
用于寻找最短路径
A*算法
启发式搜索算法，常用于路径规划
Kruskal算法
用于最小生成树
Prim算法
用于最小生成树
拓扑排序 (Topological Sort)
用于有向无环图 (DAG)
线性表查找
顺序查找
一种在列表中查找目标值的方法。它按顺序检查列表中每个元素的目标值，直到找到匹配或所有元素都搜索完为止。
时间复杂度 O(n)
在最坏的情况下，只会检查每个元素一次。
双指针
分块查找
Z字型
二维数组中的查找
排序 (Sort)
冒泡排序 (Bubble Sort)
是一种基于交换的简单排序算法，其核心思想是通过相邻元素的反复比较和交换，将较大的元素逐步“浮”到数组的末端（或较小的元素“沉”到前端），类似于水中气泡上浮的过程。
时间：O(n²)
空间：O(1)
空间：O(1)
插入排序(Insertion Sort)
直接插入排序
对于给定的一组记录，初始时假定第一个记录自成一个有序的序列，其余的记录为无序序列；
从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列为止。
希尔排序
（缩小增量排序）
（缩小增量排序）
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
归并排序(Merge Sort)
是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)
递归深度为log2n
递归深度为log2n
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
基数排序 (Radix Sort)
快速排序 (Quick Sort)
(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中
（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
不从最高位开始排序的原因，主要是出于空间的考虑，
因为如果按照最高位开始排序，则之后的地位都需要创建一个完整的基数排序空间，空间占用量成指数增长
因为如果按照最高位开始排序，则之后的地位都需要创建一个完整的基数排序空间，空间占用量成指数增长
拓扑排序（Topological Sort）
将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。
堆排序 (Heap Sort)
桶排序（Bucket Sort）
选择排序(Selection Sort)
简单选择排序
对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮排序，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。
堆排序
将序列构造成一棵完全二叉树 ；
把这棵普通的完全二叉树改造成堆，便可获取最小值 ,输出最小值 ；
删除根结点，继续改造剩余树成堆，便可获取次小值 ,输出次小值 ；
重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序 。
把这棵普通的完全二叉树改造成堆，便可获取最小值 ,输出最小值 ；
删除根结点，继续改造剩余树成堆，便可获取次小值 ,输出次小值 ；
重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序 。
计数排序 (Counting Sort)
交换排序
冒泡排序
快速排序
使用分治法策略
选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
遍历（Traversal）
线性结构
树形结构
图结构
递归
通用步骤
function dfs(参数) {
// 1. 终止条件（必须，最简单的情况）
// 2. 处理当前层（如：找中间元素）
// 3. 递归调用处理子问题（必须）
// 4. 组合结果并返回
}
// 1. 终止条件（必须，最简单的情况）
// 2. 处理当前层（如：找中间元素）
// 3. 递归调用处理子问题（必须）
// 4. 组合结果并返回
}
2. 双指针（Two Pointers）
同向指针
滑动窗口
题目特征：求连续子数组/子字符串
核心：固定扩展右边界，按条件收缩左边界，即：右扩 + 左缩
核心：固定扩展右边界，按条件收缩左边界，即：右扩 + 左缩
标准模板
function slidingWindow(nums, k) {
let left = 0;
let result = 0;
for (let right = 0; right < nums.length; right++) {
// 1. 将nums[right]纳入窗口
updateWindow(nums[right]);
// 2. 检查窗口是否满足条件
while (windowInvalid()) {
// 3. 不满足条件时收缩左边界
removeFromWindow(nums[left]);
left++;
}
// 4. 更新结果（此时窗口必然有效）
result = updateResult();
}
return result;
}
function slidingWindow(nums, k) {
let left = 0;
let result = 0;
for (let right = 0; right < nums.length; right++) {
// 1. 将nums[right]纳入窗口
updateWindow(nums[right]);
// 2. 检查窗口是否满足条件
while (windowInvalid()) {
// 3. 不满足条件时收缩左边界
removeFromWindow(nums[left]);
left++;
}
// 4. 更新结果（此时窗口必然有效）
result = updateResult();
}
return result;
}
209. 长度最小的子数组
时间：O(n)
空间：O(1)
空间：O(1)
3. 无重复字符的最长子串
核心
以 s[i] 为结尾的最长无重复子串的长度
使用 滑动窗口 + 数组 维护当前无重复字符的子串，遇到重复字符时直接截断数组左侧，始终保持窗口内无重复字符，并记录最大长度。
方法
用两个指针 left 和 right 表示窗口的左右边界。
用哈希表记录字符最后一次出现的位置。
当遇到重复字符时，移动 left 到重复字符的下一个位置。
每次移动 right 时更新最大长度。
用哈希表记录字符最后一次出现的位置。
当遇到重复字符时，移动 left 到重复字符的下一个位置。
每次移动 right 时更新最大长度。
时间：O(n)
空间：O(1)：虽然有 map，但最多是128个
空间：O(1)：虽然有 map，但最多是128个
713. 乘积小于 K 的子数组
2958. 最多 K 个重复元素的最长子数组
2730. 找到最长的半重复子字符串
2779. 数组的最大美丽值
2962. 统计最大元素出现至少 K 次的子数组
2302. 统计得分小于 K 的子数组数目
1658. 将 x 减到 0 的最小操作数
1234. 替换子串得到平衡字符串
76. 最小覆盖子串（2025.2.13 字节一面，2025.4.21深信服笔试）
438. 找到字符串中所有字母异位词
时间：O(n+m)
空间：O(1)
空间：O(1)
快慢指针
283. 移动零
核心
left 指向下一个非零元素应该存放的位置
right 探索新的非零元素
right 探索新的非零元素
时间：O(n)
空间：O(1)
空间：O(1)
876. 链表的中间结点
27. 移除元素
141. 环形链表
142. 环形链表 II
143. 重排链表
234. 回文链表
对向指针（左右指针）
function twoPointers(nums, target) {
nums.sort((a, b) => a - b); // 大多数情况需要先排序
let left = 0;
let right = nums.length - 1;
let result = 0;
while (left < right) {
// 核心逻辑：根据条件决定移动 left 或 right
if (condition) {
// 以 left 为基准，统计所有符合条件的 right
result += right - left;
left++; // 基准点移动
} else {
right--; // 调整右端点
}
}
return result;
}
nums.sort((a, b) => a - b); // 大多数情况需要先排序
let left = 0;
let right = nums.length - 1;
let result = 0;
while (left < right) {
// 核心逻辑：根据条件决定移动 left 或 right
if (condition) {
// 以 left 为基准，统计所有符合条件的 right
result += right - left;
left++; // 基准点移动
} else {
right--; // 调整右端点
}
}
return result;
}
9. 回文数
核心
将数字转为字符串后，用左右指针从两端向中间逐对比较字符，快速判断回文性质。
167. 两数之和 II - 输入有序数组
时间：O(logn)
空间：O(1)
15. 三数之和
核心
利用排序后的数组特性，通过外层循环固定一个数，内层双指针在剩余区间内快速定位另外两个数，同时通过跳过重复元素避免重复解
方法
排序数组：预处理数组使其有序，便于双指针移动和去重。
外层循环固定一个数：遍历数组，跳过重复的起始数以避免重复解。
内层双指针搜索：用左右指针在剩余区间内寻找两数之和与当前数互补的组合，根据和的大小动态调整指针位置。
严格去重：每次移动指针后跳过所有相邻重复值，确保结果唯一性。
收集结果：当找到有效组合时记录，并继续搜索直至指针相遇。
外层循环固定一个数：遍历数组，跳过重复的起始数以避免重复解。
内层双指针搜索：用左右指针在剩余区间内寻找两数之和与当前数互补的组合，根据和的大小动态调整指针位置。
严格去重：每次移动指针后跳过所有相邻重复值，确保结果唯一性。
收集结果：当找到有效组合时记录，并继续搜索直至指针相遇。
时间：O(n²)
空间：O(n)
18. 四数之和
四数之和需要多一层 j 循环，因此需额外对 j 去重（j > i + 1 时跳过重复值）。
注意
需要弄清什么时候 break，什么时候 continue
时间：O(n²)
空间：O(1)
空间：O(1)
2824. 统计和小于目标的下标对数目
最关键的是以哪边为基准来做，在符合条件的那个判断中，如果是left++，就是以左端点为基准查所有符合条件的右端点，反之亦然。
count += right - left 是因为当前 left 和 right 之间的所有数（left+1 到 right）与 nums[left] 的和都满足条件
count += right - left 是因为当前 left 和 right 之间的所有数（left+1 到 right）与 nums[left] 的和都满足条件
16. 最接近的三数之和
记得剪枝，同三数之和
611. 有效三角形的个数（网易、百度、B站）
排序，固定最长边 循环i从2到最后，查找能以 right 和 i 为边的三角形的个数
11. 盛最多水的容器
核心
从数组的两端向中间移动，每次移动较短边的指针，计算当前容器的水量并更新最大值。
方法
初始化左指针 left 在数组起始位置，右指针 right 在数组末尾。
计算当前容器的水量：min(height[left], height[right]) * (right - left)。
移动较短边的指针（因为移动较长边不会增加水量）。
重复直到指针相遇，返回最大水量。
计算当前容器的水量：min(height[left], height[right]) * (right - left)。
移动较短边的指针（因为移动较长边不会增加水量）。
重复直到指针相遇，返回最大水量。
时间：O(n)
空间：O(1)
空间：O(1)
42. 接雨水
时间：O(n)
空间：O(1)
空间：O(1)
分离指针（多序列遍历）
3. 分治算法 (Divide and Conquer)
归并排序 (Merge Sort)
大整数乘法 (Karatsuba Algorithm)
4. 动态规划（Dynamic Programming）
What ：Dynamic programming，简称 DP，通过把原问题分解成相对简单的子问题的方式来求解复杂问题的方法
When
如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。
如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等
How
穷举分析
确定边界
确定最优子结构
状态转移方程
例题
53. 最大子数组和
斐波那契数列
青蛙跳台阶问题
股票的最大利润
连续子数组的最大和
礼物的最大价值
96. 不同的二叉搜索树
核心
利用二叉搜索树的特性，即对于每个节点，左子树节点值小于该节点，右子树节点值大于该节点。通过选取不同节点作为根节点，将问题分解为左子树和右子树的构建问题，而左子树和右子树的构建相互独立，不同根节点的选择会产生不同的树结构，所有可能根节点的组合数之和即为最终结果。
方法
定义 dp[i] 表示 i 个节点能构建的不同二叉搜索树的数量。首先初始化 dp[0] 和 dp[1] 为 1，分别对应空树和单个节点的情况。然后通过两层循环，外层循环遍历节点数从 2 到 n，内层循环遍历所有可能的根节点。对于每个节点数 i 和根节点 j，根据状态转移方程 dp[i] += dp[j - 1] * dp[i - j] 计算不同根节点下的组合数并累加，最终得到 dp[n]，即 n 个节点能构建的不同二叉搜索树的数量。这种方法将大问题逐步分解为小问题，避免了重复计算，时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(n)\)。
背包问题 (Knapsack Problem)
最长公共子序列 (Longest Common Subsequence)
最长递增子序列 (Longest Increasing Subsequence)
矩阵链乘法 (Matrix Chain Multiplication)
5. 贪心算法 (Greedy Algorithms)
例题
121. 买卖股票的最佳时机
遍历每一天，算出到当前天为止的最大利润
55. 跳跃游戏
遍历每一格，算出是否可以到达当前位置（每一格都应该能被达到，才能到达最后）
45. 跳跃游戏 II
6. 回溯算法（Backtracking）
7. 随机化算法（Randomized Algorithm）
8. 近似算法（Approximation Algorithm）
9. 其他
前缀和
本质：任意子数组的和，都可以表示为两个前缀和的差
560. 和为 K 的子数组
const map = { 0: 1 }; // 前缀和为 0 出现 1 次
同时处理两种边界情况：
当前缀和直接等于 k 时（即 sum - k == 0）
当子数组从数组开头开始时（即 prefix[i] - 0 == k）
同时处理两种边界情况：
当前缀和直接等于 k 时（即 sum - k == 0）
当子数组从数组开头开始时（即 prefix[i] - 0 == k）
哈希
机器学习算法
补充
JS
定义时确定：箭头函数的 this 在函数创建时从外层作用域继承，且永不改变。
词法作用域：逐层向外查找 this，直到找到普通函数或全局作用域。
词法作用域：逐层向外查找 this，直到找到普通函数或全局作用域。
误区 1：箭头函数作为对象方法时，this 会指向对象。
纠正：箭头函数的 this 与对象无关，始终继承自外层作用域。
误区 2：bind 可以改变箭头函数的 this。
纠正：箭头函数忽略 bind/call/apply 的 this 参数。
纠正：箭头函数的 this 与对象无关，始终继承自外层作用域。
误区 2：bind 可以改变箭头函数的 this。
纠正：箭头函数忽略 bind/call/apply 的 this 参数。
常见面试题
深拷贝
function deepCopy(obj, hash = new WeakMap()) {
// 基本类型和null/undefined
if (obj === null || typeof obj !== 'object') return obj;
// 循环引用检查
if (hash.has(obj)) return hash.get(obj);
// 特殊对象处理
switch (obj.constructor) {
case Date: return new Date(obj);
case RegExp: return new RegExp(obj);
case Map: return new Map(deepCopy([...obj], hash));
case Set: return new Set(deepCopy([...obj], hash));
case ArrayBuffer: return obj.slice(0);
default:
if (ArrayBuffer.isView(obj)) {
return new obj.constructor(
deepCopy(obj.buffer, hash),
obj.byteOffset,
obj.byteLength
);
}
}
// 普通对象/数组
const copy = Array.isArray(obj) ? [] : Object.create(Object.getPrototypeOf(obj));
hash.set(obj, copy);
// 统一处理所有属性（包括Symbol）
Reflect.ownKeys(obj).forEach(key => {
if (Object.hasOwn(obj, key)) {
copy[key] = deepCopy(obj[key], hash);
}
});
return copy;
}
// 基本类型和null/undefined
if (obj === null || typeof obj !== 'object') return obj;
// 循环引用检查
if (hash.has(obj)) return hash.get(obj);
// 特殊对象处理
switch (obj.constructor) {
case Date: return new Date(obj);
case RegExp: return new RegExp(obj);
case Map: return new Map(deepCopy([...obj], hash));
case Set: return new Set(deepCopy([...obj], hash));
case ArrayBuffer: return obj.slice(0);
default:
if (ArrayBuffer.isView(obj)) {
return new obj.constructor(
deepCopy(obj.buffer, hash),
obj.byteOffset,
obj.byteLength
);
}
}
// 普通对象/数组
const copy = Array.isArray(obj) ? [] : Object.create(Object.getPrototypeOf(obj));
hash.set(obj, copy);
// 统一处理所有属性（包括Symbol）
Reflect.ownKeys(obj).forEach(key => {
if (Object.hasOwn(obj, key)) {
copy[key] = deepCopy(obj[key], hash);
}
});
return copy;
}
Promise
EventBus
运算符
^ 异或
136. 只出现一次的数字
使用位运算中的异或(XOR)操作。因为：
任何数和0异或都是它本身
任何数和自身异或都是0
异或满足交换律和结合律
var singleNumber = function(nums) {
let result = 0;
for (let num of nums) {
result ^= num;
}
return result;
};
& 按位与
231. 2 的幂
在判断 n 是否是 2 的幂时，我们利用了 n & (n - 1)：
2 的幂的二进制形式：1 后面跟着 0（如 8 → 1000）。
n - 1 的二进制形式：0 后面跟着 1（如 7 → 0111）。
n & (n - 1)：
如果 n 是 2 的幂，n & (n - 1) 会得到 0（如 8 & 7 → 1000 & 0111 = 0000）。
如果不是 2 的幂，结果不会为 0（如 6 & 5 → 0110 & 0101 = 0100）。
2 的幂的二进制形式：1 后面跟着 0（如 8 → 1000）。
n - 1 的二进制形式：0 后面跟着 1（如 7 → 0111）。
n & (n - 1)：
如果 n 是 2 的幂，n & (n - 1) 会得到 0（如 8 & 7 → 1000 & 0111 = 0000）。
如果不是 2 的幂，结果不会为 0（如 6 & 5 → 0110 & 0101 = 0100）。
做题步骤
快速澄清边界条件
说清解法
边写边解释
算法扩展 + 性能分析
API
Map 遍历
for([key,value of map])
0 条评论
下一页
