1 遇见
基础课是去年年底购入的,当时购入的动机主要有两点:
1. 笔试面试:这个原因显而易见的。如果这世界上有哪家互联网公司笔试面试你的时候,面试官一道算法题也不问,那你可以直接考虑换一家公司了。
2. 编程能力:之前上南大 OS 公开课时听 JYY 讲过一句话。“编程这个东西你如果没有好的学习资料,自己瞎几把学一般是不行的”。于是想着自己在学算法的时候有个真正的大佬能带带我就好了,于是就找到了 AcWing。
2 知识点总结
基础课内容很多,前前后后学习了总共 1 个多月,其中“数学知识”一章完全跳过去了,理由是对我而言暂时还不是很急着学习这一章节的内容。“数学知识”相关的算法题的题目都有一定的难度,且对笔试面试题而言已经算是比较偏的内容了。我想如果花很多时间去琢磨那些数学公式,短期内对我的回报可能远远不如我的付出。因此等以后有时间了,再好好攻克这部分的内容(说白了就是太菜了所以先暂时不看了)。在正式进入提高课内容之前,很有必要对基础课的内容做一个大的总结,好让知识和题目成块成体系,y 总已经总结地很好了,我能做的工作就是把他的话再重复一遍。
总的来讲,基础课的内容排版可分为:基础算法、基础数据结构、图论、搜索、动态规划和贪心。基础算法和基础数据结构都是模板,没什么太多的思想可言,学习的重点当然是模板的记忆,但更重要的是思考这种算法和数据结构的特性使其可以适用于哪种类型的问题。图论中的三大问题分别是最短路、最小生成树和二分图,重点是我们如何将一个现实问题抽象为一个图论的问题,然后再应用这些经典问题中的算法去解决。搜索、动态规划和贪心是常用的三个算法思想,没有比较固定的模板可言,需要对问题的解空间树有一个清晰的概念。
- 基础算法:
- 快排:三路划分。
- 归并:分治思想的应用。将一个区间从中点处划分为两个子区间,再进行归并统计。
- 二分:区间的左半边的元素都满足一定的性质,而右半边的元素都不满足这样的性质,算法返回左半边与右半边相交的分界点。
- 高精度:因为 C++ 无法处理大整数的运算,所以要用代码模拟四则运算的过程。
- 前缀和:解决区间中某一子区间的和的问题。
- 差分:解决给区间中某一子区间上的所有元素加上某一个常数 c 的问题。
- 位运算:k & j, j | k, x & -x, ~i, cnt & 1, !p, i >> j & 1, (1 << n) - 1
- 离散化:区间元素都很大且均处在十分离散的大小范围,我们通过排序、去重和二分查找的方式,让这些元素保持原有的大小关系的同时,将它们映射到了较小的连续的大小范围中。
- 双指针:先用暴力算法求解原问题,然后注意到问题的解一定满足某一性质,所以在问题的求解过程中就不用计算那些不满足这一性质的状态了,从而达到优化时间复杂度的目的。
- 数据结构:
- 链表:对数据的添加和删除比较高效,对数据的查询和修改效率一般,如若涉及到遍历操作就无所谓了。
- 栈、队列:先进后出和先进先出。
- 堆:高效地查询集合中最小/大的元素。
- 单调栈:高效解决一个元素的左边/右边第一个比它大/小的元素的问题。
- 单调队列:模拟滑动窗口。
- 哈希表:高效地查询、插入元素。区间哈希可以高效查询子区间的哈希值。
- KMP:高效解决区间 P 是否是区间 S 的子区间的问题。
- Trie 树:高效存储和查询大量的线性数据,采用多叉链表来实现。
- 并查树根:高效判断两个节点是否在同一个集合,并且可以高效维护节点之间的普遍关系,还可以维护集合本身的信息。
- 图论:
- 图的实现:稠密图 g[N][N], 稀疏图 h[N], e[M], w[M], ne[M], idx;
- 单源汇最短路问题:Dijkstra(维护集合 S,仅适用于非负权边)、Bellman-Ford(k 次迭代遍历所有边,可求解边数限制的最短路问题)、SPFA(Bellman-Ford 的优化版,可判负环)
- 多源汇最短路问题:Floyd(三重循环)
- 最小生成树问题:Prim(与 Dijkstra 思想类似)、Kruskal(按权重从小到大遍历所有边)
- 二分图问题:染色法判二分图、匈牙利算法求二分图的最大匹配
- 搜索:暴搜问题的解空间树,主要有 DFS 和 BFS 这两种方式。
- 动态规划:发现了最优子结构,计算的子问题无后效性,而且记录计算每一个子问题时对应的解。
- 数据规模反推算法内容:能够粗略确定动态规划所需要的维数,进而去辅助集合的定义。
- 闫氏 DP 分析法:集合定义、集合属性和集合的划分。要求集合定义必须能够不重不漏地对应到问题的任意一种状态。集合划分时通常会采取“不重不漏”和“变动倒数第二步”的策略。
- 边界和初始化:当集合属性是最值时,一般都初始化成无穷大;当集合属性是次数时,一般都初始化成 0 或 1。
- 遍历顺序:观察问题的拓扑序列,确保计算当前状态时所需依赖的状态都已经计算完成。
- 记忆化搜索:降低代码复杂度。
- 贪心算法:
- 贪心算法与动态规划的区别:主要体现在状态转移方程上,动态规划一般需要计算可能存在最优解的所有可能状态才能完成一次转移,而贪心会根据某种测略只需计算某一个特定状态即可完成状态的转移。
- 贪心算法的设计步骤:根据自己的经验和直觉,先设计一个可行的贪心策略,然后找几个例子进行验证,感觉没太大问题就可以直接交了。
- 常见的简单的贪心问题:大部分区间问题(推公式)、哈夫曼树、排序不等式、绝对值不等式等。
👍