LeetCode刷题笔记——HashTable

705/706. Design HashSet/HashMap

这里主要是参考了python源码中对dict的实现，可以参考我的博客中对python内建dict的相关文章。这里主要采用的策略是：

1. 使用开放寻址法解决冲突
2. 使用与python内部一致的二次哈希函数
3. 桶数按照实际使用量“used”进行控制
4. 负载因子的阈值设置为2/3
5. 因为元素都是数字，所以使用字符串“dummy”表示dummy态的桶

看了一下提交中最快的方法是封装了python自己的dict的接口，这个不予比较，也肯定比不过。另外的实现方法是固定的桶数，每个桶是一个动态数组，不出意外，在数据量远大于桶数的时候，这种方法实现的哈希表的时间复杂度会变成平方级别。因此使用随机数据进行测试，方法是随机产生1:3:1的插入、查找与删除操作，操作次数与时间的关系如下：

	100	200	500	1000	10000	20000	40000	80000	160000	320000	500000
动态哈希表	0.00043133900180691853	0.0009461890003876761	0.0026909899970632978	0.00474665700312471	0.05380460600281367	0.1239928860013606	0.3027137169992784	0.9117266799948993	3.3329256319993874	14.875687354004185	30.45249983100075
静态哈希表	0.0016315299944835715	0.002342113002669066	0.005659467999066692	0.01336817800620338	0.1381508459962788	0.2928399669981445	0.5868546249985229	1.156653906997235	2.358773715001007	5.801840243002516	8.933496708006714

136. Single Number (bangbang)

使用哈希表解决这道题的话再简单不过了。但是题目中的额外要求是不使用额外空间。这个想起来就有点费劲了，看所属的类别有“Bit Manipulation”，以为是用BitMap但是这个实际上也是会随着空间的增长而增长的啊……死活就没想到异或操作，答案也是十分的简单。具体看位操作的相关文章。

49. Group Anagrams

这道题的目标是把属于“Anagrams”的词分组，“Anagrams”是指颠倒字母而成的词。因此“Anagram”实际上是定义了一种等价关系。现在要做的就是给我一个字符串，我能计算出一个哈希函数，同一个等价类的哈希函数要一样，不同的等价类的一定不能一样。官方给了一个思路是利用排序后的字符串。但是这样效率有些低，我感觉利用数学性质应该也可以找到一个好的哈希函数，我自己往位图的方向想了想，没想出来比较好的。看到评论区中给了一个叫好的思路，就是利用质数的性质。任何一个数的因式分解是唯一的，因此没有两种不同构成的因式分解可以计算出一个数。利用这个性质可以在线性时间计算一个字符串的键。

36. Valid Sudoku

需要三个类型set，分别保证同一个数字不出现在同一行、同一列和同一个3*3的格子中。

652. Find Duplicate Subtrees (bangbang)

这道题想要快速判断一个子树是否已经出现，最好的方法就是想一个函数，可以将同一个子树映射为相同的key，不同的子树不会映射到同一个key。我一开始想的方法是利用质数，具体方法是一个树的id等于（左子树的id×质数a+右子树的id×质数2+根节点的值×质数3），这个没有啥理论依据，但是我感觉看起来可行。然而实际的提交结果不对，会比答案中的多找到一些重复子树。这也就意味着一些不同的树计算出了相同的id。然后看了solution的思路，倒是很简单的……也是利用递归的思路，不过一个树的id等于（左子树的id，右子树的id，根节点的值）构成的元组。我想利用质数相乘的方法就是想把这三者结合，这个方法直接就不结合，简单粗暴而有效！并且维护一个map负责将三元组映射为一个数字，找到没有的三元组就分配一个新的数字就行。直接维护三元组行吗？不行的，因此必须在每一步把三元组压缩为一个id才能保证每一个节点都可以用一个三元组表示，要是只用三元组会导致复杂的树会被表示为一个多层嵌套的三元组，得不偿失。
另外代码中参考别人的实现用了两个Counter和defaultdict的小技巧。前者可以不把未见元素初始化为零，Counter会自己做这个工作；后者可以把defaultdict的工厂函数设置为自身的__len__方法完成自动分配递增id的功能。

3. Longest Substring Without Repeating Characters (bangbang)

这道题重新做比我之前的时间效率大大提高……这次的思路是这样的：首先要维护当前的最长子串，然后因为遇到一个新的字符的时候要判断是否已经出现过，因此这个子串用 map 来存，这个map负责把字符关联到他的下标。用 map 又有一个问题，就是map是无序的，我知道了一个字符重复了，那么我需要把在这个字符之前出现的字符全部从子串中删掉。这个问题其实也好解决，因为我知道当前子串的长度，也知道被重复的字符的下标，也是到新遇到的字符的下标，这样我就可以知道要被删除的部分的下标范围，然后就更新就可以了。看Solution中管这个叫sliding window方法，我也没仔细看……

454。4Sum II

把两个列表的和的所有可能性存为集合是效率最高的。因为第一个步骤————建集合的时间复杂度是平方，第二个步骤————遍历另外两个的复杂度是平方，此时总的复杂度是最小的。如果减小任意一个步骤的复杂度，势必会导致另一个步骤的复杂度上升，使得总的复杂度上升。

347. Top K Frequent Elements

一看见top k，就想到要用堆，这里不详细写了。我是用的Counter.most_common取得巧。

380. Insert Delete GetRandom O(1)

我的思路是一个数组A存元素的值，一个map存倒排索引，将元素映射至A中的位置，插入时在尾端插入，更新map，删除时需要走点心，利用数组的无序性，把被删除的元素和最后的元素交换就可以安全的缩小数组长度。