本周知识点很多，节奏一下变快，感觉群里大多都基础颇好，每日一题里经常出现超纲的题目，照例会列出效率不同的各种解法，自己并没有参与多少讨论，主要时间都用来苦思冥想课件中提到的题目，其实倒也没什么很难想通的点，花时间想也能想出来，但是过程还是很痛苦，总是不断的想拖延拖延再拖延，好歹有个积分制度，毕业制度再督促，外加个可以兜底一切难题的群可以加强下心理建设，种种因素配齐才勉强坚持。
笔记
1.二叉树,堆
知识点
-
二叉树的概念,以及衍生出的各种概念,搜索树,平衡树,红黑树,AVL数,B树,B+树...的含义及运用场景，二叉树一般用来优化查找性能，因为不平衡的二叉树查找性能几乎和数组无异，所以会有很多方案来实现二叉树平衡。
-
堆的概念,实现原理,包括插入和查找的原理.
很多时候会结合数组或栈一起使用，常用于将结果暂存起来，再正序或反序取出，实现排序或取值，比如二叉树层级遍历，用堆就很好实现。
典型题目
- 遍历二叉树,前中后序.
- 给定前序中序,还原二叉树.
- 堆,大顶堆,插入和查找的原理及时间复杂度.(二叉堆的下潜和上升)
- 最小的k个数,滑动窗口最大值.
2.递归
知识点
- 终止条件
- 当前逻辑
- 递归函数
- 参数处理
按照以上模板书写逻辑，基本不会错，写递归明确参数在传递曾中的作用才是关键。
典型题目
- 爬楼梯，斐波拉契数列。
- 括号组合方式
3.分治、回溯
知识点
- 分治
将O(n)变为O(logn)的最佳方案，通过递归将一次查询变为多个子查询，效率倍增。典型为快排算法的内部分治逻辑。 - 回溯
- 在递归基础上增加了回退上一步或上几步的逻辑.比如用零钱凑够100元，会有很多解，但解的过程中会不断的通过回退前一步或几步的方式来达到遍历结果的最大化。
- 相关的类似题目不少, 很多穷举的问题都可以用回溯的办法来解决。
典型题目
- 全排列
- 子集
- 组合
网友评论