算法导论总结(五)散列表

LeetCode刷了两百多题,再来一波总结,题目刷多了很多不做笔记就忘记了,这里也算是巩固一下。这一节主要总结散列表类型的题目。散列表、桶排序等算法最大的特点就是时间复杂度是O(1)。这对于需要考虑算法时间复杂度的题目来说提升是常常需要考虑的方法。这篇博客没有太多原理的解释,都是对着题目做的随手笔记 ,比较乱,请见谅。

散列表直接查找

典型的题目就是第一题,TwoSum(1题、170题、202题开心数记录重复),还有后面的ThreeSum, FourSum等都可以类推,如果需要从一堆数中知道你需要那个是否存在,那么利用Hash Table就可以轻易实现O(1)的时间复杂度。

在FourSum的题目中需要额外注意的是,如果需要枚举(18题),那么还是推荐先排序,然后二指针遍历来实现O(n^3)的时间复杂度的(这里还有重复处理等细节)。如果不需要枚举,只需要给出个数(454题),四个数字的和也可以轻易实现O(n^2)的时间复杂度,因为四个数字可以拆分成两两组合,最后两个Table再次组合。

不仅数字可以查表,字符串也可以查表。在PalindromePairs(336题)中,需要拼凑回文串,也是逐个位置切割,剩余部分查散列表的方式来实现的。

利用散列表处理字符串

因为散列表依赖了内存空间的地址编码,所以对于有些情况特别适合散列表处理,比如字符串中的每个字符,将其作为地址可以保证其范围在0-127(255)之间,那么可以利用散列表直接统计字符串中每个字符的出现次数 (3题、30题将子串当做key、49题等都使用了统计字符数量的能力,205同构字符串存储对应关系,242题等,244题等)。

在题目MininumWindowSubstring(76题)中结合滑动窗口和HashTable的字符统计能力来寻找包含指定字符的最短子串。

利用散列表存储对应关系

在STL中散列表有unordered_set和unordered_map,set是单值的,map是存储一对值的,对于键值可以使用Hash索引。

在题目CopyListWithRandomPointer(138题)中,对于这种奇异数据结构的拷贝,使用Hash表存储对应结点关系,重构时直接查表建立连接关系。

在题目MaxPointsOnALine(149题)中,利用HashMap存储double类型的斜率 和 该斜率对应的点的数量来实现统计。事实上,这道题double存储斜率是不妥的,即使是double精度也是有限的,这里最正确的方式是通过辗转相除来除以最大公约数,将这一对数作为斜率。

一对数合并为一个数作为键值

上面讲到(149题)存储一对数的问题,但是STL的Map不支持pair作为键值,那么两个int合并为一个long long就可以存储了

  long long key = key1 + ((long long)key2 << 32);

这种方式及转化的思想在很多题目中都有用到。

比如在RepeatedDNASequence(197题)中,为了防止内存超出,将连续十个字符存储在一个int32中,因为只有四种字符,总共只需要二十个位。

 

 

发表评论