NOTE.md

算法训练营期末总结

作为一个即将大四的科班生，我很庆幸可以在工作之前就认识到算法与数据结构的重要性，同时也感谢极客时间提供了一个很好的平台，算法训练营来进行专项针对性的训练和学习。

在算法训练营的这两个月，我学到了很多，学到了各种各样的数据结构和算法，我在学校虽然学习过数据结构与算法这门课，但是深度和广度是远远不够的，这次系统的学习，让我对递归，分治，贪心，动态规划等算法有了更深入的了解。我也在算法训练营教到了很多的朋友，从他们身上也学到了很多，覃超老师和助教的分享让我对以后的技术方向和发展有了进一步对认识。

经过两个月的学习，我的leetcode题量达到了100+，我的目标是在找工作或实习之前可以通过刻意练习不断巩固达到400+的题量

我因看到风暴而激动如大海！！

下面是一些方法和知识的总结：

方法论

• 解题步骤

  • 弄清题意，确认细节
  • 边界条件要沟通好并且考虑好
  • 思考更多的解决方法
  • 比较各方法的时间和空间复杂度
  • coding和test

• 编码时采用自顶向下的方式，先写主流程框架，再扩充细节

• 刷题方法

  “五毒神掌”

  • 第一遍不要思考过久，看题解，copy答案，理解思路
  • 第二遍及时回顾，自己把代码写出来
  • 看中国区和国际区的优秀题解，学习思路，并且将代码精简
  • 按照一定的记忆曲线复习再次写出题解。（第一天、立刻复习、隔一天、一周后...）

• 总结并记录经典的代码模板，熟记于心

• 优化的重点思路：用空间换时间

• 在平时的业务逻辑中也要注重思考有没有更好的解决办法

知识点网络

• 数据结构
  • 存储结构
    • 顺序存储：数组
    • 链式存储：链表
  • 逻辑结构
    • 线性结构
      • 栈
      • 队列
    • 非线性结构
      • 散列表（hash table）
      • 树
      • 图
• 算法
  • 复杂度
    • 时间复杂度：最好、最坏、平均；优劣对比
    • 空间复杂度：来源：开辟辅助资源空间、递归
  • 解决重复子问题
    • 贪心
    • 分治
    • 回溯
    • DP
    • 暴力枚举
  • 查找
  • 搜索
    • BFS
    • DFS
    • A*
  • 排序：基础值排序中，最好的时间复杂度O(N*LogN)
  • 位运算
  • 布隆过滤器
  • LRU Cache
  • 字符串匹配

一些要点

• 树的问题宜用递归解决，分析是否需要遍历所有节点，或者只需要水波纹式展开，考虑用BFS还是DFS
• 分析重复子问题，再根据细节考虑使用哪种方式！
• 避免人肉递归，要有数学归纳法思维。
• DP的步骤：
  1. 找最优子结构
  2. 定义存储中间状态的结构
  3. 写出递推公式（DP方程、状态方程）
• 切题眼，有一些题目中的关键词可关联到要使用的方法，例如：最小、最少、最优、全部。。。
• 熟记经典高频的代码模板！！！
• 对于常用语言中一些数据结构的API要比较熟悉。
• 没有思路时，先想暴力方法，再考虑优化方向，优化思路例如用空间换时间。
• 保持刷题习惯，加深解题记忆，同时增强写出好代码的能力。