跳至主要內容

算法大师兄

LincZero大约 3 分钟

算法大师兄

参考：

  • https://space.bilibili.com/1784235102，这里主要记的是《合集 · 热血编程》系列
  • https://space.bilibili.com/319521269，主要参考《合集 · 夜深人静写算法》、《合集 · 面试离谱题集》

一分钟记住所有算法

  1. 顺序表。顺序表和顺序表相关的算法主要有：
    • 线性枚举
    • 前缀
    • 双指针
    • 二分枚举
    • 三分枚举
    • 离散化
    • 排序：冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序、堆排序、基数排序、计数排序
    • 模拟
    • 贪心
  2. 链表
    • 单向链表
    • 双向链表
  3. 栈
    • 后进先出栈（LIFO栈，Last Input, First Output）
    • 单调栈
  4. 队列
    • 先进先出队列（FIFO队列，First Input, First Output）
    • 双端队列
    • 单调队列
  5. 字符串
    • kmp
    • 字典树
    • 马拉车
    • AC自动机
    • 后缀数组
    • BM
  6. 树
    • 二叉树
    • 二叉搜索树
    • AVL树
    • 线段树
    • 霍夫曼树
    • 堆
    • 红黑树
    • 伸展树
    • 左偏树
    • Treap
    • B+树
    • 树链剖分
  7. 图
    • 二分图
    • 最短路
    • 最小生成树
    • 最近公共祖先
    • 深度优先搜索
    • 强连通分量
    • 双连通分量
    • 2-sat（读two-sat）
    • 欧拉回路
    • 哈米尔顿回路
    • 迭代加深
    • 广度优先搜索
    • 拓扑排序
    • A*
    • 稳定婚姻
    • 双向广搜
    • 差分约束
    • 并查集
    • 哈希表
    • 跳跃表
    • 树状数组
    • 最大流
  8. 动态规划（DP，Dynamic Programming）
    • 递归
    • 线性DP
    • 记忆化搜索
    • 背包问题
    • 树形DP
    • 区间DP
    • 数位DP
    • 状压DP
  9. 其他网友补充
    • 图卷积、遗传算法、蚁群算法、粒子群算法、随机森林、XGBOOST、LightGBM、退火
    • 斐波那契堆，cdq分治，kd树，扩展欧几里得，线性规划（单纯形算法）。还有计算机几何的一些算法（比如求求凸包直径的旋转卡壳）
    • 重链剖分，长链剖分，实链剖分，Splay树，link cut tree，间隔打表，插头dp

枚举算法的优化

2552. 统计上升四元组open in new window

image-20240217141214769
image-20240217141214769

即找类似 1324 这样的四元组，ijkl

版本一：O(n^4)：

image-20240217141138347
image-20240217141138347

版本二：O(n^3)：先找位于中间k和j，再往外找i和l

image-20240217141450248
image-20240217141450248

版本三：O(n^2)，看不太懂，等学完其他再回来看

cnt记录类似132的三元组（利用空间，加速时间）。找类似 1324 这样的四元组，ijkl。

先定jl，再找ik。j，枚举第二个数再枚举第一个数

评论区好像说：

  • 树状数组随便弄就行
  • 有说能用归并排序统计二元组然后标记看作一个整体进行枚举或者离散化再来统计（可加前缀和优化）
  • 有低于n^2的做法，线段树
  • 用类似于KMP算法的原理解题，把已经获取到的4个数先缓存起来
image-20240217141650000
image-20240217141650000

英雄哪里出来 - 合集·面试离谱题集

(01) 两数之和，如何不断优化你的代码效率？

https://leetcode.cn/problems/two-sum/

image-20240217150011199
image-20240217150011199

方案一，暴力枚举，O(n^2)，500ms

image-20240217145948617
image-20240217145948617

方案二，二分查找，但需要数组有序，这里用了一个vector（排序可能需要O(NlogN)，后续二分logN），12ms

image-20240217150354041
image-20240217150354041

方案三：代码太长了，换用map，直接给桶排

方案三点一：Map是红黑树，增删改查复杂度O(logN)，反而更慢，8ms

image-20240217150525225
image-20240217150525225

方案三点二：应使用unordered_map，变成哈希表，时间复杂度O(1)，但还是12ms。然后变成从后往前找，就4ms了

(15) 三数之和

方法一，暴力枚举，O(n^3)

image-20240218193525231
image-20240218193525231

方法二，Map

image-20240218193852720
image-20240218193852720

方法三，双指针

image-20240218194310547
image-20240218194310547