week02

哈希表 哈希碰撞 Hash解决冲突的方法： 1、 开放定址法， 当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者 碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。 2、 再哈希法 3、 链地址法 4、 建立公共溢出区 经常抽象出来的就是map和set java的TreeMap和TreeSet底层是红黑树

树、 树和图的差别，主要看是不是有环 linked list就是特殊化的tree tree就是特殊化的Graph

树的遍历，前(根左右)、中(左中右)、后(左右中) 无序的话，查询一个数，只能遍历 二叉搜索树，插入查询删除都是o(logn)，空树也是BST

二叉搜索树的删除： 找其左子树最大的节点（最右面的），或者其右子树最小的节点（最左边的）。直接替换。 如果有子树，就直接按在他父节点上 树的面试题一般都是递归的，为什么？因为其结构导致的，只有左右指针，

递归算法的话，要有必要的缓存。 递归效率差，一般在调用栈的开辟上。层不深的话，和循环的效率差不多

堆Heap 工业级应用一般用斐波拉契堆，或者严格的斐波那契数列，用多叉树实现，空间时间复杂度更好 二叉堆只是堆的一种实现，并不是最优的实现。只是一种常见及简单的实现。 find-min时间复杂度一定是o(1)的

（两个子节点没有大小关系，只要比根小就行） 用二叉搜索树，很慢，因为最小值在最左边，时间复杂度就不是o(1)

插入： 放入最后，再依次和他的父节点比较，他比较大就往上移，o(logn) 删除： 只能删除0节点，将最后一个元素放到0节点，依次从根节点往下比较，将自己的最大儿子和自己替换，o(logn)

heap[heapSize++]=5,分两步，heap[heapSize]=5, 再heapSize++ https://shimo.im/docs/Lw86vJzOGOMpWZz2/read，，，java的二叉堆（ BinaryHeap ）的源码

主要面试题： 最小的个数----------------- 滑动窗口----------------- 双端队列 优先级队列 前K个高频元素----------------- o(n)遍历一遍数组，放map里 用优先级队列对map里的数据排序，只存最大的k个值 输出结果

图 有点，有边，，， 度，就是这个点连了多少个边。 权重也可以表示损耗，

两种表示方法（都是二维的） 邻接矩阵：没有权重就用1、0表示， 有权重就表示两点间边的权重， 无向图，就会以谢对角线，对称。有向图，就不对称 邻接表：

图的考题： 深度、广度优先遍历：不要忘记加visited集合。这是和树的遍历的最大区别，树可以保证没有环路，不会重复 通用结构，用递归的，代码模板要背下来

图相关参考： * 连通图个数： https://leetcode-cn.com/problems/number-of-islands/ * 拓扑排序（Topological Sorting）： https://zhuanlan.zhihu.com/p/34871092 * 最短路径（Shortest Path）：Dijkstra https://www.bilibili.com/video/av25829980?from=search&seid=13391343514095937158 * 最小生成树（Minimum Spanning Tree）： https://www.bilibili.com/video/av84820276?from=search&seid=17476598104352152051

面试时解题4件套： 1、和面试官一起吧题目过一下 2、从中找出一个最优的，时间和空间复杂度最好的 3、写代码 4、测试样例的阐述