可视化的

数据结构与算法

使用Vue3 + Vite + TypeScript + Pinia编写开始学习

数据结构

计算机存储、组织数据的方式

经典排序算法

根据不同数据结构对无序元素进行有序化的计算方法

冒泡排序

每次循环找出目前数组中最大的数,放在当前数组末尾

鸡尾酒排序

双向冒泡,来回扫描两端收缩,尾部小元素一趟到家,零交换提前收工

双调排序

排序网络：比较器位置与数据无关、同列可并行执行，先构造双调序列再距离减半合并，深度 O(log²n)，GPU 排序思想根基

选择排序

每次循环找出目前数组中最小的数,放在当前数组头部

插入排序

顺序遍历数组每一个数字,然后和该数字前面的数组比较,将其放在适当的位置

二分插入排序

插入排序变体,在已排序前缀里折半查找插入点,比较降到对数级,搬移不变保稳定

希尔排序

核心是一个插入排序,步进数1改为数组长度的一半,每完成一次步进都减小一半

归并排序

通过递归构建二叉树结构，然进行左右两个节点的有序数组合并。

自顶向下归并

递归分治版归并,对半下钻回程合并,配递归调用栈看分治全程,与迭代版对照

快速排序

选取一个基准数,将比它小的放在前面,比它大的放在后面,左右两部分重复这一过程

三路快排

荷兰国旗划分,把数组分成小于/等于/大于基准三段,等值元素一次归位,治大量重复

双轴快排

两个基准一趟分三段,递归更浅缓存更友好,Java Arrays.sort 基本类型实际采用

堆排序

利用大顶堆性质每次找出最大的数放在末尾，然后重复构造和维护大顶堆

计数排序

在已知取值范围的情况下，按照一种萝卜一个坑的思想进行排序

基数排序

不比较大小，按位（个位→十位…）反复分配到 10 个桶再收集，线性时间

桶排序

按值域把元素撒进若干桶，桶内各自排序后按桶序合并，均匀分布时近线性

图算法

在图（点 + 边）上求解的算法，如最短路、连通性、最小生成树

Dijkstra 最短路

带权图单源最短路：每次取当前最近的点松弛邻边，逐步确定到各点的最短距离

Kruskal 最小生成树

边按权重排序 + 并查集判环，不成环就加入，逐条生成总权最小的生成树

Prim 最小生成树

从一个起点生长：每步选「一端在树、一端在树外」的最小横切边并入，同图与 Kruskal 得同一棵 MST

Bellman-Ford 最短路

反复松弛所有边 V−1 轮，能处理负权边（Dijkstra 不能）、还能检测负环

拓扑排序

有向无环图的依赖排序：反复取入度 0 的点输出（Kahn），得到满足所有先后依赖的线性顺序

Floyd 多源最短路

一张距离矩阵 + 三重循环，逐个点试作中转，一次算出任意两点间的最短路（矩阵动态规划）

强连通分量

有向图里两两互相可达的极大集合：Tarjan 一趟 DFS，用 dfn/low + 栈，low==dfn 即一个 SCC 的根，O(V+E)

2-SAT

布尔可满足性：子句 (a∨b) 翻成蕴含边 ¬a→b/¬b→a，跑 Tarjan 求 SCC，x 与 ¬x 同组即无解，否则按逆拓扑序赋值，O(V+E)

最大流

网络流 Ford-Fulkerson：残量网络反复找增广路推满瓶颈，反向边允许退流改道，直到无增广路；最大流 = 最小割

二分图匹配

匈牙利算法求最大匹配：逐个左点找增广路，空闲定下、被占问让路，成功整条翻转；O(V·E)，König 定理与指派问题的地基

LCA 倍增

最近公共祖先：预处理「跳 2^k 步」跳表（爸爸的爸爸递推），查询先对齐再高位试跳——祖先不同才跳；O(log n) 一次，树上距离的地基

欧拉路径

一笔画：奇度点 0/2 判定 + Hierholzer 边走边消——卡住弹栈进路径、栈顶余边续走子环自动插入；O(E)，七桥问题与 DNA 拼接同款

动态规划

把大问题拆成子问题、子问题的解填进表格、后面直接查表复用——「填表」范式

编辑距离

把一个词改成另一个词的最少插入/删除/替换次数：二维 DP 逐格填表，相同取左上、不同取 1+三邻最小

0-1 背包

容量有限、物品取或不取，求最大价值：二维 DP 逐格填表，装不下沿用上行、装得下取 max(不取, 取)

完全背包

0-1 背包的变体，同一物品可无限次取：递推只改一处——「取」从上一行 dp[i-1] 改看本行 dp[i]，取完还能再取

最长公共子序列

两串最长公共子序列：二维 DP 相同取左上+1、不同取上左最大，填表求长度后从右下角回溯恢复出 LCS 串

最长递增子序列

一串里最长的严格递增子序列：一维 DP，dp[i] 回看前面所有 dp[j] 取最大 +1，max(dp) 即答案，回溯恢复

硬币找零方案数

每种面额无限枚，凑出目标金额有多少种组合：计数 DP，把完全背包的取 max 换成方案数相加、边界 dp[0][0]=1

石子合并

区间 DP 模板题：相邻合并代价为和，dp[i][j]=min_k(dp[i][k]+dp[k+1][j])+sum，区间由短及长枚举分割点 O(n³)；贪心会错的经典

旅行商 TSP

Held-Karp 状压 DP：把「去过哪些城」压成二进制 mask，dp[mask][i] 枚举上一站转移，O(n!) 降到 O(2ⁿ·n²)；集合当下标的灵魂

树形 DP

打家劫舍 III：状态挂节点（选/不选两态）、子树即子问题、后序即拓扑，一趟 DFS O(n)；舞会/树上背包/换根 DP 的地基

数位 DP

按位走上界数天文数字：自由分支（填小于上界位 × 9^k）+ 贴着走，禁数字撞上界位 tight 断裂；O(位数)，dp(pos,tight,state) 模板

换根 DP

二次扫描把「以每个点为根」摊成 O(n)：后序算子树内、前序换根 ans[v]=ans[u]−size+(n−size)——近远两笔账；树中距离之和

回溯与搜索

一步步做选择、错了就退回重来——递归试探 + 剪枝 + 回溯地搜索解空间

N 皇后

在 N×N 棋盘放 N 个互不攻击的皇后：逐列试探，冲突就剪枝换行，一列走投无路就回溯挪子

子集生成

枚举集合的全部 2^n 个子集：对每个元素「选/不选」构成二叉决策树，DFS 走到底记录、回退换分支

全排列

枚举 n! 个排列：每个位置从剩余未用元素挑一个，构成多叉决策树，used 标记剪枝、回溯换选择

组合总和

从一组数选若干个凑目标和：决策树上逐个加数，当前和超过目标就剪枝砍支，演示回溯剪枝的威力

迷宫寻路

在带墙网格里用 DFS 从起点找到终点：沿一个方向深入，撞死路就回退换方向，回溯的网格搜索形态

岛屿数量

数网格里有几片相连的陆地：逐格扫描，遇到新陆地就 Flood Fill 把整片淹掉、计数 +1，连通分量的入门形态

单词搜索

在字母网格里沿相邻格拼出目标词：DFS 匹配字母就深入、失配换方向、四方向不通就撤销回退，同格不复用

数独

给空格填数使行/列/宫不重复：约束回溯，试填 1..n 冲突就换、死路就撤销回退，棋盘约束的名场面

A* 寻路

给搜索装方向感：每格 f=g+h（实际步数+曼哈顿估计），每次扩展 f 最小格；h 不高估即保证最优，扩展远少于 BFS——游戏寻路/导航标配

字符串

在文本里查找、比对、处理模式串——编辑器查找、grep、DNA 比对的底层算法

KMP 字符串匹配

在文本里找模式串：预处理出部分匹配表，失配时文本指针不回退、模式串聪明滑动，O(n+m)

Rabin-Karp

滚动哈希匹配：把窗口压成一个哈希数，滑动 O(1) 更新，每格只比一个数、哈希相等才逐字符验证

Boyer-Moore

实践最快的串匹配：从模式末尾往左比，失配用坏字符规则大步右移，常常跳过整段，平均亚线性

Manacher

最长回文子串 O(n)：插 # 统一奇偶，维护最右回文用对称性复用镜像半径、只扩展超出部分，避免重复

后缀数组

把所有后缀按字典序排好（sa 数组）：倍增法每轮用上一轮 rank 拼关键字、比较长度翻倍，O(n log²n)

LCP / height 数组

相邻后缀最长公共前缀：Kasai O(n)，按原始下标处理、h 去首字符至多减 1，一趟求最长重复子串/不同子串数

AC 自动机

多模式匹配 Aho-Corasick：所有模式塞进 Trie + fail 指针（KMP 的 π 的多模式推广），一趟扫文本报出所有命中含重叠，O(n+m+z)

Z 函数

每个后缀跟开头像多久：Z-box 区间内抄镜像、达界才右扩，r 只增不减 O(n)；P#T 拼接即模式匹配，KMP π 的孪生兄弟

数学与数论

与整数、素数、模运算打交道的算法——从「把大问题拆成数的性质」出发

埃氏筛

埃拉托斯特尼筛求素数：从 2 起，每个没被划掉的数是素数，划掉它从 p² 起的倍数，筛到 √N 即停，O(N log log N)

线性筛

欧拉筛：外层遍历所有数，每个合数只被它的最小质因子划一次（i%p==0 即停），严格 O(N)，顺带得最小质因子表

欧几里得算法

辗转相除求最大公约数：gcd(a,b)=gcd(b,a mod b)，取模到余 0；几何上是用最大正方形铺满 a×b 矩形，最小正方形边长即 gcd

快速幂

二进制取幂求 aⁿ：指数拆二进制、底数反复平方 a¹→a²→a⁴→a⁸，位为 1 就乘入结果，O(log n)；模幂是 RSA 的核心

扩展欧几里得

在辗转相除回程上带货：基例 (1,0)，逐层 (x,y)=(y′, x′−q·y′)，求出 ax+by=gcd 的 Bézout 系数——模逆元与 RSA 解密的钥匙

中国剩余定理

孙子算经：模两两互质时，Mᵢ=M/mᵢ 只在本条同余「有声音」，扩欧求逆校准成 1，专属项相加 mod M 得唯一解——RSA-CRT 拆大为小的合并器

欧拉函数

φ(n) 数与 n 互质的个数：按比例划掉含质因子 p 的数，φ(n)=n·∏(1−1/p)；欧拉定理 a^φ≡1 给指数打折，RSA 的 φ(pq)=(p−1)(q−1)

米勒-拉宾

概率判素：n−1=2^s·d 从 a^d 连续平方，撞 −1 通过、非平凡平方根现形即合数；单轮误报 ≤1/4，卡迈克尔数 561 当场识破

FFT

多项式乘法 O(n log n)：换点值表示逐点乘，取点值用单位根折叠对称——位反转重排 + log n 层蝶形 (u,v)→(u±ωv)；NTT 同款骨架

Pollard's Rho

大数分解：伪随机序列在未知因子的世界里 O(n^¼) 步入环（ρ 形），gcd(|龟−兔|, n) 把因子显影；配米勒-拉宾成完整流水线

计算几何

在平面/空间上用坐标和向量处理点、线、多边形——「几何问题代数化」的算法

凸包

Andrew 单调链求凸包：按坐标排序，叉积判左转/右转，非左转就弹栈，下凸壳 + 上凸壳套住所有点，O(n log n)

旋转卡壳

两块平行卡板夹凸包转一圈求直径：每条边的对踵点只单调前移（面积比较），每边查两候选距离，O(n) 得最远点对

线段相交

跨立试验判两线段相交：四个叉积两两异号即规范相交，D=0 补包围框查端点相触；零除法零精度陷阱，O(1)

扫描线求交

Bentley-Ottmann 求 n 线段全部交点：事件队列驱动扫描线、状态结构按 y 有序，「相交前必相邻」只查新相邻对，O((n+k) log n)

查找

在有序或结构化数据里高效定位目标——每一步扔掉不可能的区域

二分查找

有序数组维护候选区间 [lo,hi]，每步和中点比、扔掉一半，O(log n)：10 亿元素 30 次比较；边界/旋转/二分答案变体的地基

二分边界

半开区间 [lo,hi) 两分支模板：lower_bound 第一个 ≥t、upper_bound 第一个 >t，等值区间 [lb,ub) 计数 = ub−lb，不存在时优雅退化

旋转数组搜索

断崖上的二分：mid 切开的两半至少一半完好有序，看目标在不在有序半范围决定去留，仍 O(log n)；重复元素退化 O(n) 的坑

二分答案

数组没了也能二分：候选答案排成一排，可行性单调 ✗✗✗✓✓✓ 找第一个 ✓；最小化最大值一族的通用降维打击，O(check·log 答案空间)

三分查找

单峰找峰顶：二分失灵（不知在上坡还是下坡），双探针 m1/m2 对决——谁小丢谁外侧 1/3，每轮区间 ×2/3；坡度二分与实数三分同族

算法可视化