[leetcode] Python(20)--设计哈希集合(705)、设计哈希映射(706)、两个数组的交集(349)、快乐数(202)

    xiaoxiao2022-07-05  194

    从零开始的力扣(第二十天)~

    PS.才发现leetcode有些题只有会员才能做了,难道要弃扣从牛了吗?

    1.设计哈希集合

    不使用任何内建的哈希表库设计一个哈希集合,具体地说,你的设计应该包含以下的功能

    add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合中是否存在这个值。 remove(value):将给定值从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。

    示例: MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); // 返回 true hashSet.contains(3); // 返回 false (未找到) hashSet.add(2); hashSet.contains(2); // 返回 true hashSet.remove(2); hashSet.contains(2); // 返回 false (已经被删除)

    注意: 所有的值都在 [1, 1000000]的范围内。 操作的总数目在[1, 10000]范围内。 不要使用内建的哈希集合库。 —————————————————————————————————————————

    具体来说,设计哈希集合,将每个要存入的数值通过计算分入结果相同的桶内,在寻找时再通过计算在相应的桶内寻找是否有这个数值,这些桶的集合就是哈希集合

    class MyHashSet(object): def __init__(self): """ Initialize your data structure here. """ self.bucket = 1000#桶 self.itemperbucket = 1000000 // self.bucket + 1 #每一个桶的大小 self.hash = [[] for _ in range(self.bucket)] def add(self, key): """ :type key: int :rtype: None """ if not self.hash[key%self.bucket]: self.hash[key%self.bucket] = [0] * self.itemperbycket self.hash[key%self.bucket][key//self.bucket] = 1 def remove(self, key): """ :type key: int :rtype: None """ if self.hash[key%self.bucket]: self.hash[key%self.bucket][key//self.bucket] = 0 def contains(self, key): """ Returns true if this set contains the specified element :type key: int :rtype: bool """ return (self.hash[key%self.bucket] != []) and (self.hash[key%self.bucket][key//self.bucket] == 1) # Your MyHashSet object will be instantiated and called as such: # obj = MyHashSet() # obj.add(key) # obj.remove(key) # param_3 = obj.contains(key)

    2.设计哈希映射

    不使用任何内建的哈希表库设计一个哈希映射,具体地说,你的设计应该包含以下的功能

    put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更新这个值。 get(key):返回给定的键所对应的值,如果映射中不包含这个键,返回-1。 remove(key):如果映射中存在这个键,删除这个数值对。

    示例: MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // 返回 1 hashMap.get(3); // 返回 -1 (未找到) hashMap.put(2, 1); // 更新已有的值 hashMap.get(2); // 返回 1 hashMap.remove(2); // 删除键为2的数据 hashMap.get(2); // 返回 -1 (未找到)

    注意: 所有的值都在 [1, 1000000]的范围内。 操作的总数目在[1, 10000]范围内。 不要使用内建的哈希库。 —————————————————————————————————————————

    与上题大致相同,只是这次需要保存键值,将原来的0转换为键值就可以了

    class MyHashMap(object): def __init__(self): """ Initialize your data structure here. """ self.bucket = 1000#桶 self.itemperbucket = 1000000 // self.bucket + 1 #每一个桶的大小 self.hash = [[] for _ in range(self.bucket)] def put(self, key, value): """ value will always be non-negative. :type key: int :type value: int :rtype: None """ if not self.hash[key%self.bucket]: self.hash[key%self.bucket] = [0] * self.itemperbucket if value == 0: self.hash[key%self.bucket][key//self.bucket] = '0' else: self.hash[key%self.bucket][key//self.bucket] = value def get(self, key): """ Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key :type key: int :rtype: int """ if not self.hash[key%self.bucket]: return -1 if self.hash[key%self.bucket][key//self.bucket] != 0: return int(self.hash[key%self.bucket][key//self.bucket]) return -1 def remove(self, key): """ Removes the mapping of the specified value key if this map contains a mapping for the key :type key: int :rtype: None """ if not self.hash[key%self.bucket]: return if self.hash[key%self.bucket][key//self.bucket] != 0: self.hash[key%self.bucket][key//self.bucket] = 0 # Your MyHashMap object will be instantiated and called as such: # obj = MyHashMap() # obj.put(key,value) # param_2 = obj.get(key) # obj.remove(key)

    3.两个数组的交集

    给定两个数组,编写一个函数来计算它们的交集。

    示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2]

    示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4]

    说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。 —————————————————————————————————————————

    先去重,再判断

    class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ ans = [] nums1 = set(nums1) nums2 = set(nums2) for i in nums1: if i in nums2: ans.append(i) return ans

    4.快乐数

    编写一个算法来判断一个数是不是“快乐数”。

    一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。

    示例: 输入: 19 输出: true

    解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 —————————————————————————————————————————

    最初的想法是输入的数一共有几位,那么最后只需要考虑(10*位数)种情况,那么只需要20次循环就能判定快乐数

    class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ i = 0 while i < 20: if n == 1: return True n = sum(int(i) ** 2 for i in str(n)) i += 1 return False

    大神的解法:不是快乐数的数称为不快乐数(unhappy number),所有不快乐数的数位平方和计算,最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中

    class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ while n: if n in [4, 16, 37, 58, 89, 145, 42, 20]: return False if n == 1: return True n = sum(int(i) ** 2 for i in str(n))

    以上就是今日经验!

    最新回复(0)