23:算法小练(3)

简单结束了数组和字符串的学习，现在来继续学习哈希表的内容

设计哈希表

设计哈希集合

哈希表精讲 - 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 赛道，发现根本不是在学算法，感觉像是在学语法