从零开始的力扣（第二十天）~

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))

以上就是今日经验！