链表

LC206 反转链表

• head可能为Nullptr
• 三指针法，每次把current->next执行prev，然后移动三指针。需要对结束时做特殊处理
• 头插法——倒序建立链表

LCR140 倒数第n个结点

• 常规做法：计数节点数，然后遍历到该节点
• 快慢指针：快指针先走cnt-1个，然后同步走；快指针到最后时，慢指针刚好是倒数第cnt个

快慢指针可以维护一个距离

LC142 判断成环

• 哈希。到末尾前再次碰撞，则碰撞的就是那个入环结点
• 快慢指针

栈

栈常用于匹配，例如括号匹配

洛谷P4387 验证栈序列

• while栈非空且匹配就出栈

LC735 小行星碰撞

• 模拟题，很麻烦
• 多用函数抽象就好想

洛谷P5788 单调栈

• 匹配的思路ok，但是要和序列绑定就难想了——出栈的时机和序列元素的位置不一致
• 两种思路：
  1. 用一个结构体绑定出栈的时机和数据
  2. 入栈index，添加一个ans数组，利用index索引到答案和数据

LC42 接雨水

• 也是单调栈思路
• 一种做法会超时：每次匹配一个高度的雨水，这样复杂度为O(maxHeight * height.size())，会超时
• 所以我们不得不一次计算一个面积
  • s.top()需要作为底部，然后找到左边墙壁，计算面积
  • 可能出现左边没墙壁、以及左边临近出现高度相等的底部的情况，需要特殊处理

第一种做法很快能写完，但是第二种做法花了我很久，冷静想想其实也不会花那么久，还是累了、以及急了

二叉树

大多基于递归——划分为三部分：左子树、右子树、自身

注意处理递归边界与空树的情形

LCR145 判断对称二叉树

• 非传统递归
• 按中轴镜像判断

LC226 反转二叉树

• 一种思路和上题相似，但需做特殊处理
• 另一种思路直接翻转左右子树

LC236 二叉树最近公共祖先

• 如果一个节点是最近的公共祖先，那么它要么是其中的一个节点，要么两个节点在他的左右子树中

并查集

查找两个元素是否在一个(树型)集合中，一开始所有元素相互独立成树，有合并与查询操作

常用于路径压缩，具有连通性和传递性

• 路径压缩：递归到深处，然后返回根节点
• 合并并查集：

洛谷P3367 经典并查集

洛谷P1525 关押罪犯

• idea1：贪心，从冲突最大的一组开始分配

好难…能轻易想出的方法几乎一定会超时，每次考察一个人都需要检查是否和监狱中的人有冲突

暂放吧