我在大厂用算法竞赛：刷题路线 | 看完就会写

▌ 技术引导 我在这段算法竞赛的刷题路上，见过太多人把时间浪费在无效的路径上。实际训练中，算法竞赛的刷题路线不是简单地按题型分类刷题，而是要结合实战环境，建立一套能快速响应的解题框架。我见过一些人用PyTorch写题解，结果发现题目要求必须用C++，这直接导致他们卡在编译环境和模板上。刷题不是为了倒背如流，而是为了形成肌肉记忆，能直接反应出最优解法。我用的是Ubuntu系统，vi编辑器配合g++编译器，每天刷题时间控制在3-5小时。刷题时要先看题解的思路，再自己写代码，最后核对优化点。我见过很多人在时间复杂度上踩坑，尤其是动态规划和贪心算法，总是没意识到一些隐藏条件，导致代码无法通过。所以，我建议大家在刷题时不仅要关注算法本身，更要关注题目的边界条件和输入输出格式。另外，我用过的代码模板是基于标准模板库的，直接使用vector和map会比手写数组更高效。还有，我习惯在题解前先用STL的unordered_set或bitset来预处理数据，这样能节省很多时间。 我本人是在2024年秋招期间开始系统性刷题的，当时用的是LeetCode和Codeforces，结合一些内部系统的模拟赛。我做的一个关键决策是，不把所有题都做一遍，而是按分类来刷，比如排序、树、图、动态规划、贪心、字符串、数学等。每类题我都会挑出30-50道核心题，反复模拟。我见过很多人把时间花在了冷门题型上，结果在面试时遇到常见题型却不会。我有个经验是，刷题时要优先掌握题型的底层逻辑，比如动态规划要理解状态转移方程的构建方式，而不是死记硬背。另外，在刷题过程中，我坚持写测试用例，用g++ -O2编译，因为性能优化在这个领域非常重要。我还会用一些自动化工具来记录刷题进度，比如用Redis存储刷过的题号和题型，这样能快速定位薄弱点。 在实际操作中，我用了几个工具来辅助刷题，比如使用Sublime Text做代码编辑，搭配终端分屏运行。我还会在git上建立一个题解仓库，每次刷完题就提交代码，这样方便后续复盘。我知道很多人会犯的错误是，不管题目难度如何，都一股脑刷下去，结果效率低下，重复做题。我自己的习惯是，每刷完一类题，就做一次模拟测试，用Codeforces的训练模式来检验掌握情况。另外，我还会用一些在线判题系统来对比自己的代码和官方题解，比如使用AtCoder的提交日志来分析解题思路的差异。这些工具和方法是我实战过程中总结出来的，能帮助大家在刷题时少走弯路。 我见过很多算法竞赛的高手都用自己的方式管理题解，比如按题型分类、按难度分级、按时间排序。我喜欢用Markdown格式记录每道题的思路和代码，这样在面试时能快速回忆。我习惯在题解中加入一些注释，记录自己当时遇到的困难和解决方法。比如在动态规划的题目中，我常会记录状态转移的边界条件和优化方式。另外，在处理大量数据时，我习惯用C++的cin.tie(0)->sync_with_stdio(false)来加速输入输出，这在Codeforces上尤其关键。我还会在代码中加入一些调试信息，比如用cout输出当前状态，这样能更快定位错误。这些细节都是我在实战中踩坑后慢慢优化出来的，每次都能少出点问题。 我刷题时最看重的是效率，而不是数量。我用了几套模板代码，比如对于图论题，我直接用邻接表和优先队列的结构；对于字符串处理题，我习惯用KMP算法或者哈希表。这些模板代码都是根据常见的题型来设计的，能节省大量时间。我有一个小技巧是，每刷完一道题就立即将其归类到相应的题型目录下，这样后续复习时能快速找到。另外，在处理时间复杂的题目时，我习惯用基准测试来评估不同解法的性能，比如用g++ -O2编译后运行多个测试案例，找到最合适的解法。这些方法让我在刷题过程中保持节奏，避免陷入低效的循环。 ▌ 技术参考 一 在算法竞赛刷题时，分类是核心。我刷题前会将题目划分为几个大类，比如排序、搜索、贪心、动态规划、字符串、图论、数学等。每个类选5-10道经典题，先理解题意，再看题解，最后自己尝试写出代码。这里的分类不是随意的，而是基于题型的常见解法。比如动态规划题，我倾向于先理解状态转移方程，再考虑是否需要优化。在代码编写时，我会优先使用vector、map这些STL容器，避免手写数组。例如，对于背包问题，我会直接使用二维vector来存储状态，这样代码更清晰也更容易调试。 二 我用过一些辅助工具来提高刷题效率。比如，使用Sublime Text作为基础编辑器，配合终端分屏，左边写代码，右边运行测试。代码编写完成后，我会用g++ -O2编译，因为这种优化方式能显著提升代码运行速度。另外，我还会使用一些在线平台，比如Codeforces的训练模式和AtCoder的虚拟参加功能，这些能帮助我模拟真实竞赛环境。在这些平台上，我更关注时间限制，比如在Codeforces中，某些题目的时间限制是严格的，这就要求代码尽可能高效。此外，我会在GitHub上建立一个题解仓库，每次刷完题就提交代码，并加入对应的分类标签。 三 在刷题过程中，我遇到过很多坑。比如，字符串匹配类的题目，很多都要求使用KMP算法，但很多人会把预处理部分写错。我曾经在Codeforces上因为没有正确构建next数组，导致代码超时。为了避免这种情况，我习惯在代码中加入详细的注释，解释每一步的逻辑。比如，在KMP算法中，next数组的构建过程要一步步写出，而不是直接复制。另外，一些数学题会涉及到大数处理，这时候我经常会使用C++的long long类型，或者在必要时使用Python的内置大整数支持。需要注意的是，这些题型在不同平台上的表现可能不同，比如Codeforces对Python的时间限制要比LeetCode严格很多。 四 我刷题时会重点关注时间复杂度和空间复杂度的优化。比如，在动态规划题中，我了解到某些题型可以通过滚动数组来减少内存占用，而某些则需要使用bitset优化。我曾经在一道题中因为没有使用bitset，导致内存超出限制，最终被判定为错误。为了避免这类问题，我养成了在代码中加入复杂度分析的习惯，即使是简单的题型，也要先估算时间开销。此外，我还发现某些题目可以通过数学推导直接得出答案，而不是硬写算法。比如，有一道题目我用数学拆分式子，最后发现其实直接返回n即可，这大大节省了时间。 五 在实际刷题过程中，我会根据题目的难度选择不同的刷题方式。对于简单题，我倾向于只看一遍题解，然后自己写出代码；对于难题，我会反复修改，直到找到最简洁的解法。我喜欢用一种叫做“多阶段复盘”的方法，比如在刷完一道题后，我会先记录当时的思路，再去对比最优解。在这个过程中，我发现很多题目原本的思路并不最优，比如有些贪心问题其实可以通过优先队列实现，而有些动态规划题其实可以用记忆化搜索优化。这些经验让我在后续刷题中能更快地找到突破口。 六 在刷题时，我特别注意题目的边界条件和输入格式。比如，有些题目输入的字符串可能包含空格，这时候我必须用cin.ignore()来处理。还有些题目的输入是多个测试案例，这时候我需要使用while循环来逐行读取。我见过很多人在这些细节上出错，比如在Codeforces上，因为没有正确处理输入格式，导致代码被判定为错误。为了避免这类问题，我习惯在代码中加入一些调试信息，比如输出输入的总长度，或者检查是否所有输入都被正确读取。此外，我还会在代码中预留一些测试用例，比如用不同的数据规模来验证是否能通过所有案例。 七 对于算法竞赛来说，性能优化至关重要。我刷题时会优先使用C++，因为它在速度上远胜于Python。在C++中，cin和cout的使用方式会影响性能，所以我会用cin.tie(0)->sync_with_stdio(false)来加速输入输出。另外，在处理大量数据时，我习惯使用ifstream一次性读取所有数据，而不是逐行读取。例如，在Codeforces上，某些题目的输入数据量极大，这时候用逐行读取会导致超时，而一次性读取能有效提升效率。我还发现，使用vector而不是数组能减少内存碎片，提高代码稳定性。 八 我刷题时会使用一些代码规范来保证代码质量。比如，我会在每个函数前加上注释，说明其功能和参数。代码中所有变量和函数都会使用有意义的命名，比如用dp[i][j]表示动态规划的状态，而不是用a或b。此外，我还会在代码中加入一些调试变量，比如用debug变量来控制是否输出中间结果，这在调试时非常有用。我发现，那些代码结构混乱、变量命名随意的人，往往在比赛中容易出错，因此养成良好的编码习惯是提升刷题效率的关键。 九 在刷题过程中，我遇到过一些题型的特殊要求。比如，某些图论题需要使用并查集，这时候我必须用路径压缩和按秩合并的优化方式。如果只用基础的并查集实现，可能会导致超时。我曾经在LeetCode上因为没有使用这些优化，导致代码在大测试用例上无法通过。为了避免这类问题，我会在代码中先加入这些优化，然后测试是否有效。此外，某些题型需要使用位运算，比如bitset，这时候我需要提前熟悉其用法，否则可能无法写出正确的代码。 十 我在刷题时会关注题目的时间限制和内存限制。比如，在某些题目中，如果时间限制是1秒，那我必须确保代码的最坏时间复杂度不超过O(n log n)。如果时间复杂度是O(n^3)，那在n=1000的情况下就无法通过。我曾经在Codeforces上因为没有考虑时间复杂度，导致代码在大案例上超时，最终被判为错误。为了避免这些问题，我会在代码中加入一些统计时间的指令，比如在头文件中包含，然后用clock()来计算执行时间。这样能帮助我快速定位性能瓶颈。 十一 在算法竞赛中，有些题型需要手动实现一些常用的数据结构。比如，堆、拓扑排序、线段树等。这些数据结构必须熟练掌握，否则无法写出正确的代码。我习惯在每次刷题后，将常用的数据结构写成模板，这样在后续题目中可以直接使用。比如，对于堆，我直接使用priority_queue，而对于拓扑排序，我则手动实现队列和入度数组。这些模板代码是我在多次实战中整理出来的，能帮助我快速应对各种题型。 十二 我刷题时会重点关注题解的思路，而不是直接看代码。比如，在看一道动态规划题的题解时，我会先理解状态转移方程，再看代码是否符合该思路。我发现，很多题解的代码写得非常简练，但实际理解起来却需要仔细推导。所以我喜欢把题解的思路用文字记录下来，然后再尝试写出自己的代码。这种方式虽然耗时，但能帮助我真正掌握题型的解法。此外，我还会在代码中加入一些注释，解释每一步的逻辑，这样在后续复习时能更快回忆起来。 十三 在刷题过程中，我发现一些题型可以通过数学公式直接得到答案，而不需要复杂的算法。比如，有一道题目要求计算数列的第n项，我通过观察发现其实可以用斐波那契数列的递推式来解决，而不是直接模拟整个过程。这大大减少了计算量，提高了代码效率。我也遇到过一些题目，虽然看起来很复杂，但其实只需要运用一些常见的数学技巧就能解决。因此，我养成了在刷题前先思考数学方法的习惯，这能帮助我更快地找到解题思路。 十四 我刷题时会注意不同题型的解题策略。比如，在贪心类题目中，我习惯先将数据排序，再按照某种规则选择最优解；在动态规划类题目中，我则会先定义状态，再寻找状态转移方程。这些策略能帮助我更快地找到解题方向。我发现，有些题目如果按照常规思路去解，可能会陷入无法优化的困境，而有些题目则需要换一种思路，比如从后往前推导。因此，我经常会在题解后思考是否还有更优的解法，这能让我在后续刷题中避免重复踩坑。 十五 在刷题时，我会使用一些工具来辅助测试和分析。比如，在LeetCode上，我习惯用不同的测试用例来验证代码的正确性，有时甚至会手动生成数据。另外，我还会使用一些性能分析工具，比如gprof，来分析代码的执行时间。这些工具能帮助我快速发现性能瓶颈，比如某些函数调用次数过多，或者某些循环没有优化。我也发现，有些题目虽然可以用暴力解法通过，但优化后的解法往往能节省大量时间，这在大规模数据测试中尤为重要。因此，我养成了在代码中加入性能优化点的习惯，比如使用bitset代替数组，或者使用快速排序代替冒泡排序。