赞
踩
本系列笔记主要作为笔者刷题的题解,所用的语言为Python3
,若于您有助,不胜荣幸。
哈希表[hash table]又称为散列表,它是一种通过键key
与值value
的映射关系来实现高效的增删查找操作,具体而言,我们是通过一个键key
来对哈希表进行访问,查询获得其value
。哈希表各种操作效率对比
数组 | 链表 | 哈希表 | |
---|---|---|---|
查找元素 | O ( n ) \mathcal{O}(n) O(n) | O ( n ) \mathcal{O}(n) O(n) | O ( 1 ) \mathcal{O}(1) O(1) |
添加元素 | O ( 1 ) \mathcal{O}(1) O(1) | O ( 1 ) \mathcal{O}(1) O(1) | O ( 1 ) \mathcal{O}(1) O(1) |
删除元素 | O ( n ) \mathcal{O}(n) O(n) | O ( n ) \mathcal{O}(n) O(n) | O ( 1 ) \mathcal{O}(1) O(1) |
在哈希表中进行增删查改的时间复杂度都是 O ( 1 ) \mathcal{O}(1) O(1) ,非常高效。
在哈希表中,我们将表中的每个空位称为桶[bucket],每个桶可以存储一个键值对,因此,查询操作就是找到key
对应的桶,并在桶中获取value
。在哈希表中如何对需要查询的元素进行定位呢?这里使用了一个函数来将key
映射为哈希表中的位置,这个函数被称为hash()
哈希函数,该函数的实现有许多中方式,这里不再展开。
如果哈希函数查询不同的key
,但是出现了相同的返回值这应该怎么办呢?这种情况被称为哈希冲突,针对哈希冲突有多种扩容的方式,这里也不再展开。哈希表其实就是一种牺牲了空间来换取时间的数据结构。
当我们想使用哈希法来解决问题的时候,我们一般会选择如下的三种数据结构:
在python3
中内置的数据结构dict
其实就是一种hash table
。
给定两个字符串 s
和 t
,编写一个函数来判断 t
是否是 s
的字母异位词。
**注意:**若 s
和 t
中每个字符出现的次数都相同,则称 s
和 t
互为字母异位词。
解法一:数组
使用数组我们需要手搓一个hash
函数
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
hashtable: List = [0] * 26
for char in s:
hashtable[ord(char) - ord('a')] += 1
for char in t:
hashtable[ord(char) - ord('a')] -= 1
for value in hashtable:
if value != 0:
return False
return True
其中,python3
内置函数ord()
用于获取字符的 ASCII 码值或 Unicode 码值。将获取到字符的ASCII码与a
的ASCII码相减,这样我们就获取到了在hashtable
中存放的相对应索引,这就是我们手搓的hash
函数。
解法二:使用字典
from collections import defaultdict
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
hashs: dict = defaultdict(int)
hasht: dict = defaultdict(int)
for char in s:
hashs[char] += 1
for char in t:
hasht[char] += 1
return hashs == hasht
这里需要注意defaultdict
的用法,当defaultdict
首次访问不存在的key
时,会将其的值设置为0
给定两个数组 nums1
和 nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
解法一:使用map
from collections import defaultdict
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res: set = set() # 用set来去重
hashtable: dict = defaultdict(int)
for n in nums1:
hashtable[n] = 1
for n in nums2:
if hashtable[n] == 1:
res.add(n)
return list(res)
当我们需要考虑去重的时候,我们通常使用set
数据结构来保存结果,set
不允许有重复的元素存在,利用该特性自动完成去重。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res: set = set()
hashtable: dict = {}
for n in nums1:
hashtable[n] = hashtable.get(n, 0) + 1
for n in nums2:
if hashtable.get(n, 0) != 0:
res.add(n)
return list(res)
自用内置的dict()
,方法dict.get(key, defaultvalue)
,尝试查询key
的值,如果key
不存在则返回defaultvalue
。
解法二:使用数组
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res: set = set()
hashtable: List = [0]*1001 # 开辟存储空间
for n in nums1:
hashtable[n - 1] = 1
for n in nums2:
if hashtable[n - 1] == 1:
res.add(n)
return list(res)
解法三:python的特性
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res: List = []
for num in nums1:
if num in nums2 and num not in res:
res.append(num)
return res
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
这道题的关键在于无限循环上,如果我们按照常规思维来判断的话,我们不知道需要循环多少次,如果是无限循环的话,我们就无法跳出这个循环,那么应该如何解决呢?重点在于我们可以怎么判断它是否开始循环了,如果这个快乐数的演变过程中,出现了已经出现过的数,那么就表明它已经陷入循环了,那就肯定不是快乐数。所有这就是一个典型的查询过程,我们可以用哈希法来解决。
class Solution:
def isHappy(self, n: int) -> bool:
seen: set = {1}
while n not in seen: # 当n已经出现过则退出循环
seen.add(n)
n = sum([int(s)**2 for s in str(n)])
return n == 1
解法一:使用dict作为hash table
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
record: dict = {}
for index, value in enumerate(nums):
res: int = target - value
if res in record:
return [record[res], index]
record[value] = index # 保存新元素一定要放在后面,这样可以防止当前的value和record中的key冲突
return []
解法二:使用set作为hash table
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
record: set = set() # 使用set作为hash table
for index, value in enumerate(nums):
res: int = target - value
if res in record:
return [nums.index(res), index]
record.add(value)
return []
给你四个整数数组 nums1
、nums2
、nums3
和 nums4
,数组长度都是 n
,请你计算有多少个元组 (i, j, k, l)
能满足:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
我们将四个数组分别用A,B,C,D来表示,一个具体的思路是,我们先对其中2个数组进行遍历统计其和的出现次数(如a+b)生成一个hash table,然后再遍历剩余的两个数组来进行查找(c+d的负数在其中出现的次数),如果出现了a+b+c+d=0
则符合要求,要求我们需要统计出现的次数,所以我们使用dict
作为哈希表的结构。
为什么是分为两两来进行遍历呢?因为我们分为一个数组和三个数组来进行遍历的话,时间复杂度为 O ( n 3 ) \mathcal{O}(n^3) O(n3),两两遍历的时间复杂度为 O ( n 2 ) \mathcal{O}(n^2) O(n2),这样更优。
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
record: dict = {}
count: int = 0
for value1 in nums1:
for value2 in nums2:
record[value1 + value2] = record.get(value1 + value2, 0) + 1
for value3 in nums3:
for value4 in nums4:
count += record.get(-(value3 + value4), 0)
return count
给你两个字符串:ransomNote
和 magazine
,判断 ransomNote
能不能由 magazine
里面的字符构成。
如果可以,返回 true
;否则返回 false
。
解法一:使用dict
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
record: dict = {}
for char in magazine:
record[char] = record.get(char, 0) + 1
for char in ransomNote:
if char not in record:
return False
record[char] -= 1
for times in record.values():
if times < 0:
return False
return True
解法二:使用数组
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
record: List = [0] * 26 # 因为字母一共26个
for char in magazine:
record[ord(char) - ord('a')] += 1
for char in ransomNote:
record[ord(char) - ord('a')] -= 1
return all([value >= 0 for value in record])
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请
你返回所有和为 0
且不重复的三元组。
该题使用哈希法的话,去重的处理会非常复杂,所以使用双指针法比较方便,虽然相对简单了,但是还是涉及到一些去重的细节需要考虑清楚。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 首先对nums进行排序
result: List = []
for index in range(len(nums)):
if nums[index] > 0: # 如果排序后的首元大于0,则说明不存在这样的组合
return result
if index > 0 and nums[index] == nums[index - 1]: # 对第一个元素进行去重
continue
left: int = index + 1
right: int = len(nums) - 1
while left < right:
if nums[index] + nums[left] + nums[right] > 0:
right -= 1
elif nums[index] + nums[left] + nums[right] < 0:
left += 1
else:
result.append([nums[index], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: # 对剩余两个元素进行去重
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort() # 排序
result: List = []
for i in range(len(nums)):
if nums[i] > target and nums[i] > 0 and target > 0: # 剪枝
break
if i > 0 and nums[i] == nums[i-1]: # 去重
continue
for j in range(i+1, len(nums)):
if nums[i] + nums[j] > target and target > 0: # 剪枝
break
if j > i+1 and nums[j] == nums[j-1]: # 去重
continue
left: int = j + 1
right: int = len(nums) - 1
while left < right:
s: int = nums[i] + nums[j] + nums[left] + nums[right]
if s < target:
left += 1
elif s > target:
right -= 1
else:
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return result
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。