代码随想录算法训练营Day6

哈希表理论基础 Hash Table

当我们要快速判断一个元素是否出现在及合理的时候,就要考虑哈希表.

枚举的时间复杂度是O(N),哈希表是O(1)

哈希函数Hash function, 哈希碰撞Collisions

哈希法也是牺牲了空间换取了时间, 因为我们要使用额外的数组, set或者是map来存放数据, 才能实现快速的查找.

哈希表的三种形式:Array,Set,Map

Python Hash Table

初始化:

c = Counter() # a new, empty counter

c = Counter('gallahad') # a new counter from an iterable

c = Counter({'red': 4, 'blue': 2}) # a new counter from a mapping

c = Counter(cats=4, dogs=8) # a new counter from keyword args

元素操作:

c = Counter(s)

print(c.values) # [2,3,1]

print(c.keys) # [A, B, C]

print(c.items) # [(A, 2), (B, 3), (C, 1)]

del c[“egg”] # 删除指定元素

对空元素的处理:

Counter对象有一个字典接口,如果引用的键没有任何记录,就返回一个0,而不是弹出一个KeyError

c = Counter(['eggs', 'ham'])

print(c['bacon']) # 返回0,而不是KeyError # count of a missing element is zero

elements()方法

返回一个迭代器, 其中每个元素将重复出现计数值所指定次。元素会按首次出现的顺序返回。如果一个元素的计数值小于1, elements()将会忽略它

c = Counter(a=4, b=2, c=0, d=-2)

sorted(c.elements())

['a', 'a', 'a', 'a', 'b', 'b']

most_common([n])方法

返回一个列表, 其中包含 n 个最常见的元素及出现次数, 按常见程度由高到低排序。 如果 n 被省略或为 None, most_common()将返回计数器中的所有元素。计数值相等的元素按首次出现的顺序排序

Counter('abracadabra').most_common(3)

[('a', 5), ('b', 2), ('r', 2)]

subtract([iterable-or-mapping])方法

从 迭代对象 或 映射对象 减去元素。像dict.update()但是是减去, 而不是替换。输入和输出都可以是0或者负数

c = Counter(a=4, b=2, c=0, d=-2)

d = Counter(a=1, b=2, c=3, d=4)

c.subtract(d)

c

Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

数学操作

提供了几个数学操作, 可以结合 Counter 对象, 以生产multisets (计数器中大于0的元素)。

加和减, 结合计数器, 通过加上或者减去元素的相应计数。

交集和并集返回相应计数的最小或最大值。

每种操作都可以接受带符号的计数, 但是输出会忽略掉结果为零或者小于零的计数

sum(c.values()) # total of all counts

c.clear() # reset all counts

list(c) # list unique elements

set(c) # convert to a set

dict(c) # convert to a regular dictionary

c.items() # convert to a list of (elem, cnt) pairs

Counter(dict(list_of_pairs)) # convert from a list of (elem, cnt) pairs

c.most_common()[:-n-1:-1] # n least common elements

+c # remove zero and negative counts

注意点

1. 计数器主要是为了表达运行的正的计数而设计；但是, 小心不要预先排除负数或者其他类型.
2. Counter 类是一个字典的子类,不限制键和值。值用于表示计数, 但你实际上可以存储任何其他值
3. most_common()方法在值需要排序的时候用.
4. 原地操作比如 c[key] += 1, 值类型只需要支持加和减。所以分数,小数,和十进制都可以用, 负值也可以支持。这两个方法update()和subtract()的输入和输出也一样支持负数和0.
5. Multiset多集合方法只为正值的使用情况设计。输入可以是负数或者0, 但只输出计数为正的值。没有类型限制, 但值类型需要支持加, 减和比较操作.
6. elements()方法要求正整数计数。忽略0和负数计数.

242.有效的字母异位词 (Valid anagram)

哈希表,2mins代码搞定

1-ACSII码 ord(“a”)

2-根据数组元素上限,自制哈希表;

class Solution:def isAnagram(self, s: str, t: str) -> bool:# Sol1 哈希表# cs = Counter(i for i in s)# ct = Counter(i for i in t)# return True if cs ==ct else False# SC: O(N)# TC: O(1)# Sol2 一行流# return sorted(s) == sorted(t)# Sol3 数组做哈希表 ASCIIlist = [0]*26for i in s:list[ord(i)-ord("a")] += 1for j in t:list[ord(j)-ord("a")] -= 1return True if list == [0]*26 else False# SC: O(1)# TC: O(N)

349. 两个数组的交集

用set的数据形式作为哈希表.

return list(set(nums1) & set(nums2))    # 两个数组先变成集合，求交集后还原为数组

第202题. 快乐数

根据提示Set做哈希表,很快解决.

class Solution:def isHappy(self, n: int) -> bool:mSum = sum(int(ii)**2 for ii in str(n))mSet = {mSum}while mSum != 1: mSum = sum(int(ii)**2 for ii in str(mSum))if mSum in mSet:return Falseelse:mSet.add(mSum)return True

Python定义Set:

mSet = {}

add() Adds an element to the set
clear() Removes all the elements from the set
copy() Returns a copy of the set
difference() Returns a set containing the difference between two or more sets
difference_update() Removes the items in this set that are also included in another, specified set
discard() Remove the specified item
intersection() Returns a set, that is the intersection of two other sets
intersection_update() Removes the items in this set that are not present in other, specified set(s)
isdisjoint() Returns whether two sets have a intersection or not
issubset() Returns whether another set contains this set or not
issuperset() Returns whether this set contains another set or not
pop() Removes an element from the set
remove() Removes the specified element
symmetric_difference() Returns a set with the symmetric differences of two sets
symmetric_difference_update() inserts the symmetric differences from this set and another
union() Return a set containing the union of sets
update() Update the set with the union of this set and others

1. 两数之和

需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。