【021-毕业总结】如人饮水 难易自知

[swelily]

优先队列不是线性数据结构，是由二叉堆实现的
哈希表提供了键和值的映射关系，给出一个键，查到到它所匹配的值的时间复杂度是O(1)，解决哈希冲突的方法主要有两种，开放寻址法和链表法
二叉树的遍历分为深度优先和广度优先，其中深度优先又分为前序、中序和后序遍历
树的问题首选递归方法解决
堆，全称二叉堆，是一种特殊的完全二叉树，分为最大堆和最小堆。
在最大堆中，任何一个父节点的值都≥左右孩子节点的值
在最小堆中，任何一个父节点的值都≤左右孩子节点的值
堆排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，空间复杂度O(1)，是不稳定排序
深度优先和广度优先遍历不限于二叉树，更是一种抽象的算法思想。
贪心算法最难的一块是如何将要解决的问题抽象成贪心算法模型，只要这一步搞定之后，贪心算法的编码一般都很简单。贪心算法解决问题的正确性虽然很多时候都看起来是显而易见的，但是要严谨地证明算法能够得到最优解，并不是件容易的事。所以，很多时候，我们只需要多举几个例子，看一下贪心算法的解决方案是否真的能得到最优解就可以了。
分治算法用四个字概括就是“分而治之”，将原问题划分成 n 个规模较小而结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。这个思想非常简单、好理解。
回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。
适合用动态规划解决的问题可以总结概括为“一个模型三个特征”。其中，“一个模型”指的是，问题可以抽象成分阶段决策最优解模型。“三个特征”指的是最优子结构、无后效性和重复子问题