3.搜索与图论
3.1 最短路问题
地图
最短路问题{单源最短路{所有边权为正{朴素Dijkstra算法:稠密图(m∼n2)−O(n2)堆优化版Dijkstra算法:稀疏图(m∼n)−O(mlogn)存在负权边{Bellman−Ford算法:O(nm)SPFA算法:平均:O(m),最坏O(nm)多源汇最短路 Floyd算法:O(n3)最短路问题\begin{cases}
单源最短路
\begin{cases}
所有边权为正
\begin{cases}
朴素Dijkstra算法:稠密图(m \sim n^2) - O(n^2)\\
\\
堆优化版Dijkstra算法:稀疏图(m \sim n) - O(mlogn)\\
\end{cases} \\
\\
存在负权边
\begin{cases}
Bellman-Ford算法:O(nm)\\
\\
SPFA算法:平均:O(m),最坏O(nm)\\
...
EggCampus所需配置环境
1. 在github上将项目clone到本地，创建自己的分支，pull build2 分支
(1)首先需要安装Git
(2)创建文件夹，并在编辑器(如vscode)上新建终端
(3)git clone url 将github上的项目克隆到本地
(4)git checkout -b branch_name 创建并切换到branch_name这个分支
(5)git pull origin build2 将项目中的build2分支拉到本地
2. 配置node.js环境，全局安装npm，全局安装pnpm
(1)nodejs配环境见这篇博客：node,js的安装和全局配置，如果node -v和npm -v都能执行的话说明配置成功
(2)npm install -g pnpm全局安装pnpm，如果pnpm -v能够执行的话说明配置成功。如果终端报错无法加载文件因为在此系统上禁止运行脚本，说明是权限有问题，需要修改权限，我通过set-ExeutionPolicy RemoteSigned修改权限之后可以执行pnpm -v
3. 用pnpm生成文件用微信开发者工具打开
(1)环境配置好之后进入项 ...
1.基础算法
1.1 快速排序
思想：分治
(1)确定分界点(中点)
(2)调整区间(≤x\leq x≤x的放在左边，≥x\geq x≥x的放在右边)
(3)递归处理左右两段
暴力的方法
扫描q[l−r]q[l-r]q[l−r]:把≤x\leq x≤x的存到a[ ]a[\ ]a[ ], 把≥x\geq x≥x的存到b[ ]b[\ ]b[ ]
把a[ ]a[\ ]a[ ],b[ ]b[\ ]b[ ]合并成q[ ]q[\ ]q[ ]
优美的方法:双指针
两个指针一头一尾，如果左右两边都符合条件，那么往中间挪
1234567891011121314void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1; int x = q[(l + r) / 2]; while (i < j) { do i ++; while (q[i] < x); do j --; while (q[j] > x) ...