网上学习资料一大堆,但如果学到的知识不成体系,遇到问题时只是浅尝辄止,不再深入研究,那么很难做到真正的技术提升。
一个人可以走的很快,但一群人才能走的更远!不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人,都欢迎加入我们的的圈子(技术交流、学习资源、职场吐槽、大厂内推、面试辅导),让我们一起学习成长!
u
u
u 到 顶点
v
v
v 的边,即
u
→
v
u \to v
u→v,另一条是从顶点
v
v
v 到 顶点
u
u
u 的边,即
v
→
u
v \to u
v→u;
2、图的存储
- 对于图的存储,程序实现上也有多种方案,根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例,讲解四种存储图的方案。
1)邻接矩阵
- 邻接矩阵是直接利用一个二维数组对边的关系进行存储,矩阵的第
i
i
i 行第
j
j
j 列的值 表示
i
→
j
i \to j
i→j 这条边的权值;特殊的,如果不存在这条边,用一个特殊标记
∞
\infty
∞ 来表示;如果
i
=
j
i = j
i=j,则权值为
0
0
0。
- 它的优点是:实现非常简单,而且很容易理解;缺点也很明显,如果这个图是一个非常稀疏的图,图中边很少,但是点很多,就会造成非常大的内存浪费,点数过大的时候根本就无法存储。
- [
0
∞
3
∞
1
0
2
∞
∞
∞
0
3
9
8
∞
0
]
\left[ \begin{matrix} 0 & \infty & 3 & \infty \ 1 & 0 & 2 & \infty \ \infty & \infty & 0 & 3 \ 9 & 8 & \infty & 0 \end{matrix} \right]
⎣⎢⎢⎡01∞9∞0∞8320∞∞∞30⎦⎥⎥⎤
2)邻接表
- 邻接表是图中常用的存储结构之一,采用链表来存储,每个顶点都有一个链表,链表的数据表示和当前顶点直接相邻的顶点的数据
(
v
,
w
)
(v, w)
(v,w),即 顶点 和 边权。
- 它的优点是:对于稀疏图不会有数据浪费;缺点就是实现相对邻接矩阵来说较麻烦,需要自己实现链表,动态分配内存。
- 如图所示,
d
a
t
a
data
data 即
(
v
,
w
)
(v, w)
(v,w) 二元组,代表和对应顶点
u
u
u 直接相连的顶点数据,
w
w
w 代表
u
→
v
u \to v
u→v 的边权,
n
e
x
t
next
next 是一个指针,指向下一个
(
v
,
w
)
(v, w)
(v,w) 二元组。
- 在 C++ 中,还可以使用 vector 这个容器来代替链表的功能;
vector<Edge> edges[maxn];
3)前向星
- 前向星是以存储边的方式来存储图,先将边读入并存储在连续的数组中,然后按照边的起点进行排序,这样数组中起点相等的边就能够在数组中进行连续访问了。
- 它的优点是实现简单,容易理解;缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序,带来了时间开销,实用性也较差,只适合离线算法。
- 如图所示,表示的是三元组
(
u
,
v
,
w
)
(u, v, w)
(u,v,w) 的数组,
i
d
x
idx
idx 代表数组下标。
- 那么用哪种数据结构才能满足所有图的需求呢?
- 接下来介绍一种新的数据结构 —— 链式前向星。
4)链式前向星
- 链式前向星和邻接表类似,也是链式结构和数组结构的结合,每个结点
i
i
i 都有一个链表,链表的所有数据是从
i
i
i 出发的所有边的集合(对比邻接表存的是顶点集合),边的表示为一个四元组
(
u
,
v
,
w
,
n
e
x
t
)
(u, v, w, next)
(u,v,w,next),其中
(
u
,
v
)
(u, v)
(u,v) 代表该条边的有向顶点对
u
→
v
u \to v
u→v,
w
w
w 代表边上的权值,
n
e
x
t
next
next 指向下一条边。
- 具体的,我们需要一个边的结构体数组
edge[maxm]
,maxm
表示边的总数,所有边都存储在这个结构体数组中,并且用head[i]
来指向
i
i
i 结点的第一条边。
- 边的结构体声明如下:
struct Edge {
int u, v, w, next;
Edge() {}
Edge(int _u, int _v, int _w, int _next) :
u(_u), v(_v), w(_w), next(_next)
{
}
}edge[maxm];
- 初始化所有的
head[i] = -1
,当前边总数edgeCount = 0
; - 每读入一条
u
→
v
u \to v
u→v 的边,调用 addEdge(u, v, w)
,具体函数的实现如下:
void addEdge(int u, int v, int w) {
edge[edgeCount] = Edge(u, v, w, head[u]);
head[u] = edgeCount++;
}
- 这个函数的含义是每加入一条边
(
u
,
v
,
w
)
(u, v, w)
(u,v,w),就在原有的链表结构的首部插入这条边,使得每次插入的时间复杂度为
O
(
1
)
O(1)
O(1),所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现,空间上没有浪费,时间上也是最小开销。
- 调用的时候只要通过
head[i]
就能访问到由
i
i
i 出发的第一条边的编号,通过编号到edge
数组进行索引可以得到边的具体信息,然后根据这条边的next
域可以得到第二条边的编号,以此类推,直到 next
域为 -1 为止。
for (int e = head[u]; ~e; e = edges[e].next) {
int v = edges[e].v;
ValueType w = edges[e].w;
...
}
- 文中的
~e
等价于e != -1
,是对e
进行二进制取反的操作(-1 的的补码二进制全是 1,取反后变成全 0,这样就使得条件不满足跳出循环)。
5️⃣简单算法的入门
- 入门十大算法是 线性枚举、线性迭代、简单排序、二分枚举、双指针、差分法、位运算、贪心、分治递归、简单动态规划。
- 对于这十大算法,我会逐步更新道这个专栏里面:《LeetCode算法全集》。
- 浓缩版可参考如下文章:《十大入门算法》
🚊10、简单动态规划
数组的每个下标作为一个阶梯,第
i
i
i 个阶梯对应着一个非负数的体力花费值
c
o
s
t
[
i
]
cost[i]
cost[i](下标从 0 开始)。每当爬上一个阶梯,都要花费对应的体力值,一旦支付了相应的体力值,就可以选择 向上爬一个阶梯 或者 爬两个阶梯。求找出达到楼层顶部的最低花费。在开始时,可以选择从下标为 0 或 1 的元素作为初始阶梯。
样例输入:c
o
s
t
=
[
1
,
99
,
1
,
1
,
1
,
99
,
1
,
1
,
99
,
1
]
cost = [1, 99, 1, 1, 1, 99, 1, 1, 99, 1]
cost=[1,99,1,1,1,99,1,1,99,1]
样例输出:6
6
6
如图所以,蓝色的代表消耗为 1 的楼梯,红色的代表消耗 99 的楼梯。
a、思路分析
- 令走到第
i
i
i 层的最小消耗为
f
[
i
]
f[i]
f[i]
- 假设当前的位置在
i
i
i 层楼梯,那么只可能从
i
−
1
i-1
i−1 层过来,或者
i
−
2
i-2
i−2 层过来;
- 如果从
i
−
1
i-1
i−1 层过来,则需要消耗体力值:
f
[
i
−
1
]
c
o
s
t
[
i
−
1
]
f[i-1] + cost[i-1]
f[i−1]+cost[i−1];
- 如果从
i
−
2
i-2
i−2 层过来,则需要消耗体力值:
f
[
i
−
2
]
c
o
s
t
[
i
−
2
]
f[i-2] + cost[i-2]
f[i−2]+cost[i−2];
- 起点可以在第 0 或者 第 1 层,于是有状态转移方程:
- f
[
i
]
=
{
0
i
=
0
,
1
min
(
f
[
i
−
1
]
c
o
s
t
[
i
−
1
]
,
f
[
i
−
2
]
c
o
s
t
[
i
−
2
]
)
i
1
f[i] = \begin{cases} 0 & i=0,1\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases}
f[i]={0min(f[i−1]+cost[i−1],f[i−2]+cost[i−2])i=0,1i>1
b. 时间复杂度
- 状态数:
O
(
n
)
O(n)
O(n)
- 状态转移:
O
(
1
)
O(1)
O(1)
- 时间复杂度:
O
(
n
)
O(n)
O(n)
c. 代码详解
class Solution {
int f[1100]; // (1)
public:
int minCostClimbingStairs(vector<int>& cost) {
f[0] = 0, f[1] = 0; // (2)
for(int i = 2; i <= cost.size(); ++i) {
f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]); // (3)
}
return f[cost.size()];
}
};
- (
1
)
(1)
(1) 用f[i]
代表到达第
i
i
i 层的消耗的最小体力值。
- (
2
)
(2)
(2) 初始化;
- (
3
)
(3)
(3) 状态转移;
有没有发现,这个问题和斐波那契数列很像,只不过斐波那契数列是求和,这里是求最小值。
6️⃣刷题顺序的建议
然后介绍一下刷题顺序的问题,我们刷题的时候千万不要想着一步到位,一开始,没有刷满三百题,姿态放低,都把自己当成小白来处理。
这里以刷 LeetCode 为例,我目前只刷了不到 50 题,所以我是小白。
当我是小白时,我只刷入门题,也就是下面这几个专题。先把上面所有的题目刷完,在考虑下一步要做什么。
👨👦1、入门算法
种类 | 链接 |
---|---|
算法 | 算法入门 |
数据结构 | 数据结构入门 |
数组字符串专题 | 数组和字符串 |
动态规划专题 | 动态规划入门、DP路径问题 |
当入门的题刷完了,并且都能讲述出来自己刷题的过程以后,我们再来看初级的一些算法和简单的数据结构,简单的数据结构就是线性表了,包含:数组、字符串、链表、栈、队列 等等,即下面这些专题。
👩👧👦2、初级算法
种类 | 链接 |
---|---|
算法 | 初级算法 |
栈和队列专题 | 队列 & 栈 |
上面的题刷完以后,其实已经算是基本入门了,然后就可以开始系统性的学习了。
当然,基本如果真的到了这一步,说明你的确已经爱上了刷题了,那么我们可以尝试挑战一下 LeetCode 上的一些热门题,毕竟热门题才是现在面试的主流,能够有更好的结果,这样刷题的时候也会有更加强劲的动力不是吗!
👩👩👧👦3、中级算法
种类 | 链接 |
---|---|
算法 | 中极算法 |
二叉树专题 | 二叉树 |
热门题 | 热门题 TOP 100 |
7️⃣系统学习算法和数据结构
🚍1、进阶动态规划
文章链接 | 难度等级 | 推荐阅读 |
---|---|---|
夜深人静写算法(二)- 动态规划入门 | ★☆☆☆☆ | ★★★★★ |
夜深人静写算法(二十六)- 记忆化搜索 | ★☆☆☆☆ | ★★★★★ |
夜深人静写算法(十九)- 背包总览 | ★☆☆☆☆ | ★★★★★ |
夜深人静写算法(二十)- 最长单调子序列 | ★☆☆☆☆ | ★★★★★ |
夜深人静写算法(二十一)- 最长公共子序列 | ★☆☆☆☆ | ★★★★★ |
夜深人静写算法(二十二)- 最小编辑距离 | ★★☆☆☆ | ★★★★☆ |
夜深人静写算法(十四)- 0/1 背包 | ★☆☆☆☆ | ★★★★☆ |
夜深人静写算法(十五)- 完全背包 | ★★☆☆☆ | ★★★★☆ |
夜深人静写算法(十六)- 多重背包 | ★★☆☆☆ | ★★★★☆ |
夜深人静写算法(二十七)- 区间DP | ★★★☆☆ | ★★★★☆ |
夜深人静写算法(二十九)- 数位DP | ★★★☆☆ | ★★★★★ |
夜深人静写算法(十七)- 分组背包 | ★★★☆☆ | ★★★☆☆ |
夜深人静写算法(十八)- 依赖背包 | ★★★★☆ | ★★☆☆☆ |
夜深人静写算法(六)- RMQ | ★★★☆☆ | ★★☆☆☆ |
树形DP | 待更新 | … |
组合博弈 | 待更新 | … |
组合计数DP | 待更新 | … |
四边形不等式 | 待更新 | … |
状态压缩DP/TSP | 待更新 | … |
斜率优化的动态规划 | 待更新 | … |
插头DP | 待更新 | … |
🪐2、强劲图论搜索
1、深度优先搜索
文章链接 | 难度等级 | 推荐阅读 |
---|---|---|
夜深人静写算法(一)- 搜索入门 | ★☆☆☆☆ | ★★★☆☆ |
夜深人静写算法(八)- 二分图最大匹配 | ★★☆☆☆ | ★★☆☆☆ |
最大团 | 待更新 | … |
最小生成树 | 待更新 | … |
树的分治 | 待更新 | … |
迭代加深 IDA* | 待更新 | … |
有向图强连通分量和2-sat | 待更新 | … |
无向图割边割点 | 待更新 | … |
带权图的二分图匹配 | 待更新 | … |
哈密尔顿回路 | 待更新 | … |
最近公共祖先 | 待更新 | … |
欧拉回路圈套圈 | 待更新 | … |
最小费用最大流 | 待更新 | … |
最小树形图 | 待更新 | … |
2、广度优先搜索
文章链接 | 难度等级 | 推荐阅读 |
---|---|---|
夜深人静写算法(十)- 单向广搜 | ★★☆☆☆ | ★★★★☆ |
夜深人静写算法(二十三)- 最短路 | ★★★☆☆ | ★★★★☆ |
夜深人静写算法(二十五)- 稳定婚姻 | ★★☆☆☆ | ★★☆☆☆ |
夜深人静写算法(二十四)- 最短路径树 | ★★★☆☆ | ★☆☆☆☆ |
K 短路 | 待更新 | … |
差分约束 | 待更新 | … |
拓扑排序 | 待更新 | … |
A* | 待更新 | … |
双向广搜 | 待更新 | … |
最大流 最小割 | 待更新 | … |
0️⃣3、进阶初等数论
文章链接 | 难度等级 | 推荐阅读 |
---|---|---|
夜深人静写算法(三)- 初等数论入门 | ★★☆☆☆ | ★★★★☆ |
夜深人静写算法(三十)- 二分快速幂 | ★☆☆☆☆ | ★★★★★ |
夜深人静写算法(三十一)- 欧拉函数 | ★★★☆☆ | ★★★★★ |
夜深人静写算法(三十二)- 费马小定理 | ★★☆☆☆ | ★★★☆☆ |
夜深人静写算法(三十三)- 扩展欧拉定理 | ★★★☆☆ | ★★★★☆ |
夜深人静写算法(三十四)- 逆元 | ★★★☆☆ | ★★★★☆ |
夜深人静写算法(三十五)- RSA 加密解密 | ★★★☆☆ | ★★★★★ |
夜深人静写算法(三十六)- 中国剩余定理 | ★★☆☆☆ | ★★★☆☆ |
夜深人静写算法(三十七)- 威尔逊定理 | ★★☆☆☆ | ★★★☆☆ |
夜深人静写算法(三十八)- 整数分块 | ★★☆☆☆ | ★★★★☆ |
卢卡斯定理 | 待更新 | … |
狄利克雷卷积 | 待更新 | … |
莫比乌斯反演 | 待更新 | … |
容斥原理 | 待更新 | … |
拉宾米勒 | 待更新 | … |
Pollard rho | 待更新 | … |
莫队 | 待更新 | … |
原根 | 待更新 | … |
大步小步算法 | 待更新 | … |
二次剩余 | 待更新 | … |
矩阵二分快速幂 | 待更新 | … |
Polya环形计数 | 待更新 | … |
🛑4、进阶计算几何
📏5、字符串的匹配
🎄6、高級数据结构
🙉饭不食,水不饮,题必须刷🙉
C语言免费动漫教程,和我一起打卡!
LeetCode 太难?先看简单题!
数据结构难?不存在的!
既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,涵盖了95%以上大数据知识点,真正体系化!
由于文件比较多,这里只是将部分目录截图出来,全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频,并且后续会持续更新
国剩余定理](https://bbs.csdn.net/topics/618545628) | ★★☆☆☆ | ★★★☆☆ |
| 夜深人静写算法(三十七)- 威尔逊定理 | ★★☆☆☆ | ★★★☆☆ |
| 夜深人静写算法(三十八)- 整数分块 | ★★☆☆☆ | ★★★★☆ |
| 卢卡斯定理 | 待更新 | … |
| 狄利克雷卷积 | 待更新 | … |
| 莫比乌斯反演 | 待更新 | … |
| 容斥原理 | 待更新 | … |
| 拉宾米勒 | 待更新 | … |
| Pollard rho | 待更新 | … |
| 莫队 | 待更新 | … |
| 原根 | 待更新 | … |
| 大步小步算法 | 待更新 | … |
| 二次剩余 | 待更新 | … |
| 矩阵二分快速幂 | 待更新 | … |
| Polya环形计数 | 待更新 | … |
🛑4、进阶计算几何
📏5、字符串的匹配
🎄6、高級数据结构
🙉饭不食,水不饮,题必须刷🙉
C语言免费动漫教程,和我一起打卡!
LeetCode 太难?先看简单题!
数据结构难?不存在的!
[外链图片转存中…(img-jUnfHDQd-1715635251113)]
[外链图片转存中…(img-vwn8Cn5n-1715635251113)]
[外链图片转存中…(img-D5mX3gRp-1715635251113)]
既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,涵盖了95%以上大数据知识点,真正体系化!
由于文件比较多,这里只是将部分目录截图出来,全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频,并且后续会持续更新