力扣数据结构部分的一些笔记

哈希表#

用空间换时间

哈希表一般有三种：数组、set(map[T]struct{}模拟) 和 map

数组： 数据规模较小或者有连续的要求.

使用数组来做哈希的题目，是因为题目都限制了数值的大小。
**Set： **数据规模大、无序，或者跨度极大。只需判断元素“存不存在”。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
**Map(最全面)： **不仅要判断元素存不存在，还需要记录该元素的附带信息（如出现次数、数组下标等）。

一些哈希表的易错点：#

Map 未初始化直接使用

1
var m map[int]int //此时 m 是 nil
2

3
m[1] = 1 //❌会panic崩溃
4
m := make(map[int]int) //✅

切片类似

s[0] = 1不行，append可以
map遍历是无序的

有序需要数组

矩阵#

矩阵主要有三种类型的题目:

边界收缩法（应对“复杂轨迹遍历”类题目）
- 核心思想： 遇到要在矩阵里绕圈圈、走蛇形、走对角线的题目，直接定义上、下、左、右四个物理边界（top, bottom, left, right），走完一条边，就把对应的边界往里缩一格。
- 适用场景： 顺时针打印矩阵、逆时针打印矩阵、按对角线打印矩阵。
- **易错点：**要记得判断“长方形矩阵”中，某一个维度提前耗尽的情况。
就地标记法（应对“状态更新与空间压榨”类题目）
- 核心思想： 当题目要求你根据矩阵当前的状态，去大规模修改矩阵本身，且要求 O(1)空间复杂度时，直接拿矩阵的第一行、第一列，或者利用数字的特殊位（比如把状态存在二进制的高位里），当成你的“记事本”。
- 适用场景： 矩阵置零、生命游戏等状态同步更新问题。
- 易错点： 拿第一行/列当记事本时，一定要记得最开始先单独记录它们原本的状态，并且在最后才去修改它们。
降维组合翻转（应对“几何旋转/对称”类题目）
- 核心思想： 把“旋转”拆解成两次最简单的“翻转”（对角线翻转 + 水平/垂直翻转）。
- 适用场景： 顺时针旋转图像、逆时针旋转图像。
- 易错点： 翻转时，内层循环的边界控制极其重要。

链表#

链表主要有这几个方法：

1. 虚拟头节点 (Dummy Head)：

本质：用一个毫无意义的假节点挡在真实数据前面，充当“前驱节点”。
适用场景：所有涉及头节点可能被修改、删除或重新分配的题目（如：移除元素、合并两个有序链表）。

2. 快慢指针（Fast & Slow Pointers)：

利用两个指针的速度差来探测链表的物理结构。

本质：慢指针每次走 1 步，快指针每次走 2 步。
适用场景：寻找中点、判断循环闭环。
适用题目：
- 环形链表 I & II（141、142题，判断有没有环）
- 链表的中间结点（876题，快指针走到 nil，慢指针刚好停在正中间）
- 回文链表（234题，O(1) 空间复杂度的核心，先找中点，再反转后半段）
- 排序链表（148题，归并排序“分而治之”里切断链表的那一刀）

**3.双指针有距离差 **

不改变速度，而是让两个指针在出发时间或所走路径上做文章。

本质：让指针多走一段特定距离，或者互相走对方走过的路。
适用场景：找倒数节点、找两个无关链表的交点。
适用题目：
- 删除链表的倒数第 N 个结点（19题，让 fast 先跑 N 步，然后 slow 和 fast 齐头并进，fast 到底时 slow 刚好停在目标前面）
- 相交链表（160题，走你来时路）

4.指针重排 (反转/交换)

本质：多指针协同 (pre, cur, next)。next := cur.Next; cur.Next = pre; pre = cur; cur = next。永远记住要先暂存下一个节点，防止断链！
适用场景：原地掉头、局部结构逆转。
适用题目：
- 反转链表 I & II（206题全量反转，92题局部反转）
- K 个一组翻转链表（25题，内部反转配合外部 Dummy 头插法缝合）

二叉树#

其实二叉树基本上都是用递归实现的，只不过是直接调用自身、还是重新设立一个辅助函数或设立一个包内全局变量，这就要看题目了。下面就简单地分类一下

1. 后序遍历（大部分可以直接调用自身）

本质： 当前节点“做不了主”，必须等左子树和右子树把各自的结果算出来并“归还”给自己，自己才能整合出最终结果并向上一级汇报。
适用场景： 求树的深度/高度、求最大路径和、寻找公共祖先。
适用题目：
- 二叉树的最大深度（104题）： 问左边有多深，问右边有多深，取两者的最大值 + 1（加上自己这一层）。
- 二叉树的最近公共祖先（236题）： 如果左子树传来发现 p 的信号，右子树传来发现 q 的信号，那我（当前节点）绝对就是它俩的最近公共祖先！
- 二叉树的直径（543题）& 二叉树中的最大路径和（124题）： 递归函数只负责向上汇报“单边最大收益”，但在当前节点内部，偷偷用一个全局变量记录 左收益 + 右收益 + 自己 的最大值（暗度陈仓）。

2. 前序遍历（大部分需要另设辅助函数）

本质： 视角在“下去的路上”。父节点拿到数据后，先在自己身上动刀子（处理逻辑），或者把自己的状态当做参数传给子节点，然后再叫子节点去干活。
适用场景： 修改/翻转树的物理结构、依据给定序列重构二叉树、路径匹配。
适用题目：
- 翻转二叉树（226题）： 先把自己的左手和右手互换（node.Left, node.Right = node.Right, node.Left），然后再让儿子们去换他们自己的手。
- 从前序与中序遍历序列构造二叉树（105题）： 前序数组的第一个必定是根！拿着这个根去中序数组里找一刀切开，左边就是左子树的全部节点，右边就是右子树的全部节点，然后递归切割。
- 路径总和 III（437题）： 配合前缀和思想，把当前一路走来累加的路径和作为参数，不断传给下一代去匹配目标值。

3. 二叉搜索树 (BST)

本质： 利用 BST “左 < 根 < 右” 的天然物理结构。BST 的中序遍历（左 -> 根 -> 右）必定输出一个严格递增的有序序列。
适用场景： 所有带“二叉搜索树”字眼的题目（验证、查找第 K 小、转成有序结构）。
适用题目：
- 验证二叉搜索树（98题）： 核心就是中序遍历。用一个变量 pre 记录上一个访问的节点值，必须保证每次访问的新节点值都严格大于 pre。
- 二叉搜索树中第K小的元素（230题）： 最直观的降维打击。顺着中序遍历走，搞个计数器，数到第 K 个直接返回，这就是第 K 小。
- 将有序数组转换为二叉搜索树（108题）： 反向利用有序性。找数组最中间的数当根节点，左半段数组递归构建左子树，右半段递归构建右子树，天然保证高度平衡。

4. 层序遍历 (BFS)

**本质：**BFS的应用。借助Queue 的先进先出特性。永远记住在每层开始前获取 size := len(queue)，用这个 size 把这一层的节点全掏出来，并把它们下一层的儿子们塞进去。
适用场景： 按层处理、找最短层级、求各类“视图”。
适用题目：
- 二叉树的层序遍历（102题）： 纯正模板题，按 size 分批次出队，将同一层的值收集进一个数组。
- 二叉树的右视图（199题）： 层序遍历的微调版。每一层有 size 个节点，我只把 i == size - 1（当前层的最后一个节点）抓出来塞进结果集里。

图论#

栈#

栈的题目类型还是比较少的，大致有下面三类

1. 消除与配对

适用题目：[20. 有效的括号]、[1047. 删除字符串中的所有相邻重复项]
适用场景：题目包含“对称”、“消除”、“最近匹配”等字眼。

2. 嵌套与现场恢复

适用题目：[394. 字符串解码]、[71. 简化路径]
适用场景：题目涉及括号嵌套、递归逻辑的迭代实现。
逻辑特征：遇到 [ 或进入子层级时，将当前状态（前缀、倍数等）压栈；遇到 ] 时，弹出栈顶状态与当前结果合并。

3. 单调栈

适用题目：[739. 每日温度]、[84. 柱状图中最大的矩形]、[42. 接雨水]
适用场景：寻找“下一个更大/更小元素”、“左/右侧第一个极值”。
逻辑特征：维护栈内元素单调递增或递减。新元素打破单调性时，触发“批量结算”。