2024年最全《算法和数据结构》题海战术篇_刷了 3333 道算法题(1)，零基础学习大数据开发

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化资料的朋友，可以戳这里获取

一个人可以走的很快，但一群人才能走的更远！不论你是正从事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∞8​320∞​∞∞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、简单动态规划

LeetCode 746. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第

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语言免费动漫教程，和我一起打卡！

🌞《光天化日学C语言》🌞

LeetCode 太难？先看简单题！

🧡《C语言入门100例》🧡

数据结构难？不存在的！

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取

国剩余定理](https://bbs.csdn.net/topics/618545628) | ★★☆☆☆ | ★★★☆☆ |
| 夜深人静写算法（三十七）- 威尔逊定理 | ★★☆☆☆ | ★★★☆☆ |
| 夜深人静写算法（三十八）- 整数分块 | ★★☆☆☆ | ★★★★☆ |
| 卢卡斯定理 | 待更新 | … |
| 狄利克雷卷积 | 待更新 | … |
| 莫比乌斯反演 | 待更新 | … |
| 容斥原理 | 待更新 | … |
| 拉宾米勒 | 待更新 | … |
| Pollard rho | 待更新 | … |
| 莫队 | 待更新 | … |
| 原根 | 待更新 | … |
| 大步小步算法 | 待更新 | … |
| 二次剩余 | 待更新 | … |
| 矩阵二分快速幂 | 待更新 | … |
| Polya环形计数 | 待更新 | … |

🛑4、进阶计算几何

📏5、字符串的匹配

🎄6、高級数据结构

---

🙉饭不食，水不饮，题必须刷🙉

C语言免费动漫教程，和我一起打卡！

🌞《光天化日学C语言》🌞

LeetCode 太难？先看简单题！

🧡《C语言入门100例》🧡

数据结构难？不存在的！

[外链图片转存中…(img-jUnfHDQd-1715635251113)]
[外链图片转存中…(img-vwn8Cn5n-1715635251113)]
[外链图片转存中…(img-D5mX3gRp-1715635251113)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取