algorithm-pattern 算法模板

简介

网上也有很多类似的算法模板可供借鉴，但我相信各有不同的特点，然后爹有娘有不如自己有，自己总结归纳的才是最好的。
写下这个的目的：
1. 为了自己的学习有所产出，对自己的做题思路进行总结
2. 为了将来的温故而知新，在遇到问题是可以回顾复习
3. 希望能够帮到有需要的朋友

内容目录

1. 基本数据结构

   • 线性结构
     1. 数组
     2. 链表以及指针
     3. 栈结构
     4. 队列
     5. 哈希表
     6. 字符串
   • 树形结构
   • 网结构

2. 高级算法

   • 动态规划
   • 贪心算法
   • 分治算法
   • 回溯算法
   • 搜索算法
   • 排序算法
   • 查找算法

面试官对你的能力判断：

• 第一个级别：我们磕磕绊绊或者靠着面试官的提示写出了正确的解法；
• 第二个级别：我们快速写出了正确的解法，能够完美应对所有的测试数据，包括可能的边角数据（Corner Case）；
• 第三个级别：我们快速写出了正确的解法，并且写出来的是最优解法，一般题目对于时间复杂度考察比较多，这里默认是最优的时间复杂度；
• 第四个级别：我们的代码风格非常优美，变量名含义清晰，过程清楚明白，有一些简单的注释。

题目练习

• 算法新手 量的话可以每一个专题完成 60% Easy 的题目，选择并完成大概 30% 左右的 Medium 题目，Hard 题目的话可以挑少量进行尝试
• 有一定算法积累
  • 对于大多数Easy题，从读题到AC不超过15分钟；
  • 对于Medium题，从读题到AC不超过30分钟
  • 刷题方式是建议每天先不停地刷 Easy，注意保持 AC 节奏和速度。然后最后做几道 Medium 收尾。
• 轻松解决 Easy 和 Medium 继续拔高的过程:接触一些高级的算法和数据结构，如线段树、矩阵乘法、网络流、代码量大的模拟题等

参加周赛

周赛难度 周赛一共有四道题目，分别对应的难度是：

• 基本不涉及任何算法，只是考察代码实现，几乎无难度。
• 考察一些简单的代码知识。
• 考察某类算法，题目一般较难。
• 考察某类算法，或者综合考察一系列算法。算法可能 超纲，题目难度浮动很大，最简单的可能是 medium 略高难度，最难的可能远超普通 hard 题目。

一般如果大家完成了数据结构部分的训练，对于周赛的前两题压力应该是不大的，某些情况下第三题也可以轻松地解出来。如果是系统地完成了算法学习的同学，顺利的情况能够完成前三道题目。对于第四道题目，在有余力的情况下也可以尽量尝试，某些题目简单的场次还是能够做出来的。小知识：第四题之所以难度浮动会大，是因为力扣实际上没有 hard 以上的难度评级，这就导致了力扣的题目只要比 medium 难都会归为 hard 难度。因此 hard 难度反而是最难区分的难度范畴。包括大家刷题时，可能觉得有的 hard 很简单， 有的 hard 很困难，也是这个原因。

周赛名次

• 顺利通过前两题，基本能稳定拿到 1000 ~ 2000 名左右的名次
• 进一步能通过三道题目，排名会来到 100 ~ 1000
• 通过四题,排名来到100～200
• 减少时间和罚时，排名挺进100
• 在20分钟以内完成四道题目，排名进入前10（前 10 名的人绝大部分都是 OI 或者 ACM 选手）

短期可行的路线

• 尝试保证通过两道题目，排名 2000 以内。
• 快速正确通过两道题目，通过第三题，排名 500 - 1500。
• 死磕前三题，保证准确率（免罚时），保证实现速度，排名 100 - 200。
• 前三题稳定通过，尝试第四题，排名偶尔能进前 100。

周赛技巧

• 语言选择：不同的语言本身执行速度也是不一样的，都是正常的。如python
• 时间复杂度：注意区分是算法复杂度高，还是常数大
• 空间复杂度：知道一些基本的压缩空间的方法

推荐方法

1. 按题型类别单独去解决，将此类题目吃透。例如在某两天内解决自己能力范围所有链表类型的题目
2. 解决一类题目时，讲究先易后难的顺序。如先完成简单难度题目，然后是中等题型，最后是困难题型 60%Easy的题目，选择并完成大概30%左右的Medium题目以及少数的hard类型题目
3. 建议简单题型10-15分钟完成，中等题型20-30分钟完成，困难题型40分钟完成。根据个人实际能力情况考虑用时
4. 如果在自己以上设定时间内无法完成，建议理解参考题目的评论区和题解，在理解的基础上解决题目。切勿死磕一道题目，效率比较低。
   • 简单题5分钟没有思路，就可以看解析
   • 中等题10分钟没有思路，就可以看解析
   • 困难题20分钟没有思路，马上看解析
5. 不要想着一次性解决所有的用例，而是能尽可能覆盖大多数用例，找到覆盖它们的通用解决办法，少部分用例通过调试解决或者直接进行判断完成
6. 在解决某一类型题目的时候，总结这类题目的一些特点和要点，记录某些题目用到的最优方法，变成自己的算法模版。例如链表中的快慢指针方法。
7. 做题的目标在于在规定时间内通过，只要满足时间和空间复杂度即可，方法可以参考，但是并不那么重要。
8. 先做简单题，再做综合题。（这里的简单题指设计算法只有一种，而综合体涉及多种算法）

刷题心得

刷题好累，难死了！