第二周

总结：

本周在数组的基础之上学习多种高级的数据结构，由一下几种组成

• 哈希表，集合
• 树，二叉树，二叉搜索树
• 堆，二叉堆

这几种特殊的数据结构都是通过最基本的数据结构，例如数组，通过函数以进行实现，例如哈希表是通过哈希函数实现。为什么要抽象出不同的数据类型呢？最主要的目的就是为了提高运行时间，以空间换时间。

而树的结构其实是由数学，或者生活中其他的常见的现象得出来的，覃超老师讲的一个很有意思的点其实是：每一个树的节点可以理解为时间轴上面不同选择而变成了某一个状态。每一个节点是一种状态。

哈希表 - Set

• 在 python 里面，哈希表的实现就是通过 dict, key-value pair, 一个字典里面只有的 key 是不会重复的。
• Set 具体实现的方式和哈希表类似，每个 set 里面的值是唯一的，同比 dict 里面的 key

树 - 二叉树 - 二叉搜索树：

• 之前的数据结构，基本都是一维结构，一条直线。
• 树结构已经升维成了二维的数据结构，Node, Child Node, Sibling, Root.
• 二叉树，就是一个 Node，有左右子树。无序的数其实要遍历整棵树。
• 遍历方式组成可以分成为前序，中序，后续遍历。
• 二叉搜索树：左子树所有的节点的值都小于根节点的值。右子树的所有节点的值都大于根节点的值。-- 但是中序遍历的时候，这是一个升序的遍历。
• 查询和插入操作都是 logn

堆 heap 和 二叉堆 binary heap:

• 特性，能够快速找到一堆数中最大值或者最小值
• 入门级的堆是二叉堆，delete, insert = logn find-min/max = O(1)
• 二叉堆 通过完全二叉树实现的，除了叶子节点都是满的
• 假设第一个元素在数组中索引为 0，左孩子的索引是 2*i +1, 右孩子是 2 * i + 2, 索引为 i 的父节点索引是 floor((i-1)/2)
• 模拟插入，删除。heapify up and heapify down. 用优先队列进行实现。

周作业题解

题号	名称	Github 链接	解题心得	已经刷遍数	难度
49	丑数		一个数如果只是 2，3，5 的相乘所得。一般的想法是从 1 开始遍历，然后用 n 除 2,3,5 判判断是否合法。但是因为随着 n 增大，丑数会变得很稀疏，有很多数不需要判断。DP 的解法等学到 DP 再回来看一下。这道题可以通过 set 和 heap 来进行实现：把每一个新进的丑数放到 heap。每一个循环把最小数弹出。当循环换成之后，弹出的就是最大的那个数。	1	难
144	二叉树的前序遍历		老朋友了，用递归进行 dfs 进行前序遍历	2	中等
94	二叉树的中序遍历		类比了中序遍历，但是用栈进行。先把左边的所有子节点的推进如栈中。然后出栈，把右边节点所有子节点的加入到栈中，不断重复。	2	中等
1	两数之和		使用了 Hash 表进行实现，用 target 减去新来的数。看下 residual 的是否存在。	3	简
	有效的字母异位