入门路线

约 1305 个字 预计阅读时间 4 分钟

Warning

仅根据个人经验提供入门建议；我比较菜所以可能不够合理。如果有修改或者补充建议，欢迎随时提出QWQ！

1 基础

这一节的内容都不会单独出题，只是最基本的概念和能力。

• 语言基础
• 复杂度分析
  • 要能根据题目数据范围得知算法复杂度的 要求 或 启发。即，能够判断自己想出的算法是否能够不超时、不超空间，以及能够根据题目的数据范围猜到有哪些可能的算法。
  • 暂时不需要掌握主定理和摊还分析（势能分析）。
• 排序
  • 会用 std::sort 就行；
  • 知道 std::sort 的时间复杂度是 \(\Theta(N\log N)\)；知道 \(\Theta(N\log N)\) 是 基于比较 的排序算法的理论下界，想要突破这一下界，只能使用不基于比较的排序方法，比如计数排序；
  • 掌握 计数排序 并理解其思想。
• 栈和队列：知道概念，脑子里有这个东西记得用就行。
• 递归

2 比较常用的

Warning

学习各种算法和数据结构的时候，记得分析它们的复杂度！

算法

• 前缀和：极其常用的算法，多练习，掌握其思想。
• 贪心：重点是要能够大概判断贪心是否正确。大概的证明思路是「如果某种不用贪心策略的解是一个最优解，那么按贪心策略得到的解一定不比它差，因此贪心得到的解也是一个最优解」。
• 二分查找：掌握 std::lower_bound 和 std::upper_bound 的使用能解决大多数情况。
• 二分答案：力扣 T3 和 T4 好像出现得比较多。
• DFS 和 BFS
• 双指针：LeetCode 里比较常用的算法，有很多变化。
• 动态规划。简单的动态规划难度并不高，会出现在 LeetCode T2 难度的题目里。不过动态规划上限很高。
• 哈希：知道概念，知道 std::unordered_set 和 std::unordered_map 是用哈希做的，会用这两个容器。

图和树基础

图相关的题在 LeetCode 周赛里比较少，因此我做的也比较少QWQ

• 图的存储：邻接矩阵和邻接表表示，知道其适用场景；
• 图上的 DFS 和 BFS；
• 拓扑排序；
• 知道 树 是一种特殊的图。

数据结构

• 并查集：也比较常用，但是通常要能自己看得出来是用并查集。
• 二叉搜索树：知道概念就行，不需要自己手写；知道它在复杂度上的问题。
• 平衡二叉搜索树：知道这个东西是为了解决上述问题的就行；知道红黑树是其中一种，std::set 和 std::map 是用红黑树实现的，会用这两个容器。
• 单调栈 & 单调队列：也算常用。

3 不那么常用，但是也比较简单建议学一下的

图论

• 最短路
• 最小生成树

算法

• 离散化：有一些算法的时空复杂度和数据范围有关；在数据范围较大、数据数目相对较小，或者数据不是整数的情况下，可以使用离散化来缩小数据范围同时保持数据顺序。
• 分块思想。一个经典的例子是 块状数组。我个人的感觉是，分块一般都不是最优的正解，但是很多时候确实也能做出来这个题。
• 分治
• 高精度：比赛的时候偶尔会出现数据大得离谱的情况，这时候需要使用高精度计算。掌握基本计算能力即可。
• 快速幂：偶尔用到的快速计算 \(a^n\) 的方法；其思想比较有启发性。
• 排列组合：可以复习一下，偶尔会用到。

数据结构

• 链表
• 线段树 / 树状数组：在 LeetCode 里，应该没有上述内容解决不了的问题了。不过 线段树 / 树状数组 是两种不那么难但是比较「流氓」的数据结构，它们可以轻易解决很多问题，因此可以学一下。

4 这篇文章里没有介绍什么

我个人水平比较菜，水平基本也就限于 LeetCode Mid+/Hard-，因此上述基本上就是我掌握的全部内容了。学会「怎么用」比掌握上述数据结构、算法和思想本身更为重要和困难。

鉴于我的个人水平，我所介绍的内容 只包含 为了做 LeetCode 周赛可能需要掌握的知识和能力；但 不包含：

1. 计算机科班生应当具有的更进一步的了解和认识；
2. 超出我个人能力范围的数据结构和算法，尤其是关于图论（网络流等）、树（LCA、直径、重心等）、字符串（匹配等）、可持久化数据结构等等我可能见过题但是没学过的内容，还有计算几何等等我连题都没见过的内容。这些内容，可以自己在 OI Wiki 上找找看。

如果有什么修改或者补充建议（例如我遗漏了哪些常见的内容），请在评论区指出~感谢！

颜色主题调整

red pink purple indigo blue cyan teal green lime orange brown grey black white

评论区~

有用的话请给我个赞和 star =>
快来跟我聊天~