简单结束了数组和字符串的学习，现在来继续学习哈希表的内容
设计哈希表
设计哈希集合
哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
不使用任何内建的哈希表库设计一个哈希集合（HashSet），实现 MyHashSet 类：
- void add(key) 向哈希集合中插入值 key 。
- bool contains(key) 返回哈希集合中是否存在这个值 key 。
- void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
class MyHashSet(object):
def __init__(self):
self.capacity = 1e5
self.bucket = dict()
def add(self, key:int)->None:
if self.contains(key):
return
if key%self.capacity in self.bucket.keys():
self.bucket[key%self.capacity].append(key)
else:
self.bucket[key%self.capacity] = [key]
def remove(self, key:int)->None:
if not self.contains(key):
return
if key%self.capacity in self.bucket.keys():
if key in self.bucket[key%self.capacity]:
self.bucket[key%self.capacity].remove(key)
def contains(self, key:int)->bool:
if key % self.capacity in self.bucket.keys():
if key in self.bucket[key%self.capacity]:
return True
else:
return False
else:
return False
实际上这里是使用python的字典方法替代了链表的使用
设计哈希映射
哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
不使用任何内建的哈希表库设计一个哈希映射（HashMap），实现 MyHashMap 类，MyHashMap() 用空映射初始化对象
- void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
- int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
- void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。
class MyHashMap(object):
def __init__(self):
self.capcity = 1e5
self.bucket = dict()
def put(self, key:int, value:int)->None:
if not key%self.capcity in self.bucket.keys():
self.bucket[key%self.capcity] = {key:value}
else:
self.bucket[key%self.capcity][key] = value
def get(self, key:int)->int:
if key%self.capcity in self.bucket.keys():
if key in self.bucket[key%self.capcity].keys():
return self.bucket[key%self.capcity][key]
return -1
def remove(self, key:int)->None:
if not key%self.capcity in self.bucket.keys():
return
if key%self.capcity in self.bucket.keys():
if key in self.bucket[key%self.capcity].keys():
del self.bucket[key%self.capcity][key]
这里同样是使用字典实现的hash映射，要注意python中常见的用于处理字典的函数操作
哈希集合
哈希集合实际上是一个不包含重复元素的集合数据结构。它只存储元素本身，不存储与元素相关联的值。我们可以用python中的set()和dict()实现，他们实际上都是使用的hash存储结构
快乐数
哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1，那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
class Solution(object):
def isHappy(self, n:int)->bool:
temp = set()
while n!=1: # 用于确定计算新的平方和
next = 0
while n!=0:
first = n%10
next += first**2
n //=10
if next in temp: # 用于检查是否存在，如果存在说明不是快乐数
return False
else:
temp.add(next)
n = next # 记得要更新n的值
return True
这里的考察实际上是对于hash存储结构的使用的考察，我们在这里用的是set()
两个数组的交集
哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序
class Solution(object):
def intersection(self, nums1:List[int], nums2:List[int])->List[int]:
set1 = set(nums1)
set2 = set(nums2)
return [x for x in set1 if x in set2]
由于python的for ... in ...查找操作相当于对hash表的查找操作，所以直接快捷方式结束了
哈希映射
哈希映射是用于存储键值对结构的，也就是python中的字典结构
同构字符串
哈希表精讲 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
class Solution(object):
def isIsomorphic(self, s:str, t:str)->bool:
st,ts = {},{}
for x,y in zip(s,t):
if x in st and st[x] != y or y in ts and ts[y] != x:
return False
else:
st[x],ts[y] = y,x
return True
这里的zip()用于将多个可迭代对象（列表，数组等）打包成同一个对象，这里是将其打包为了一个字典对象
第一个唯一字符
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
class Solution:
def firstUniqChar(self, s: str) -> int:
frequency = collections.Counter(s)
for i, ch in enumerate(s):
if frequency[ch] == 1:
return i
return -1
？？？内置函数
我突然后悔了，我本来学算法是希望能学一点相关的算法知识，但是我报了Python 赛道，发现根本不是在学算法，感觉像是在学语法