网站申请建设,网站开发 微信收款,百度号码认证,湖南省郴州市北湖区1. 哈希表 文章目录 1. 哈希表写在前面1.1 理论基础1.2 有效的字母异位词1.3 两个数组的交集1.4 快乐数1.5 两数之和1.6 四数相加||1.7 赎金信1.8 三数之和#xff08;哈希法梦碎的地方#xff09;1.9 四数之和 Reference 写在前面
本系列笔记主要作为笔者刷题的题解#x…1. 哈希表 文章目录 1. 哈希表写在前面1.1 理论基础1.2 有效的字母异位词1.3 两个数组的交集1.4 快乐数1.5 两数之和1.6 四数相加||1.7 赎金信1.8 三数之和哈希法梦碎的地方1.9 四数之和 Reference 写在前面
本系列笔记主要作为笔者刷题的题解所用的语言为Python3若于您有助不胜荣幸。
1.1 理论基础
哈希表[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但是出现了相同的返回值这应该怎么办呢这种情况被称为哈希冲突针对哈希冲突有多种扩容的方式这里也不再展开。哈希表其实就是一种牺牲了空间来换取时间的数据结构。
当我们想使用哈希法来解决问题的时候我们一般会选择如下的三种数据结构
数组set集合map映射/ dict字典
在python3中内置的数据结构dict其实就是一种hash table。
1.2 有效的字母异位词
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
**注意**若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
解法一数组
使用数组我们需要手搓一个hash函数
class Solution:def isAnagram(self, s: str, t: str) - bool:hashtable: List [0] * 26for char in s:hashtable[ord(char) - ord(a)] 1for char in t:hashtable[ord(char) - ord(a)] - 1for value in hashtable:if value ! 0:return Falsereturn 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] 1for char in t:hasht[char] 1return hashs hasht 这里需要注意defaultdict的用法当defaultdict首次访问不存在的key时会将其的值设置为0
1.3 两个数组的交集
349. 两个数组的交集
给定两个数组 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] 1for 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) 1for 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] 1for 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 resclass Solution:def intersection(self, nums1: List[int], nums2: List[int]) - List[int]:return list(set(nums1) set(nums2))1.4 快乐数
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 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 11.5 两数之和
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 - valueif 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 tablefor index, value in enumerate(nums):res: int target - valueif res in record:return [nums.index(res), index]record.add(value)return []1.6 四数相加||
454. 四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
我们将四个数组分别用ABCD来表示一个具体的思路是我们先对其中2个数组进行遍历统计其和的出现次数如ab生成一个hash table然后再遍历剩余的两个数组来进行查找cd的负数在其中出现的次数如果出现了abcd0则符合要求要求我们需要统计出现的次数所以我们使用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 0for value1 in nums1:for value2 in nums2:record[value1 value2] record.get(value1 value2, 0) 1for value3 in nums3:for value4 in nums4:count record.get(-(value3 value4), 0)return count1.7 赎金信
383. 赎金信
给你两个字符串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) 1for char in ransomNote:if char not in record:return Falserecord[char] - 1for times in record.values():if times 0:return Falsereturn 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)] 1for char in ransomNote:record[ord(char) - ord(a)] - 1return all([value 0 for value in record])1.8 三数之和哈希法梦碎的地方
给你一个整数数组 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 resultif index 0 and nums[index] nums[index - 1]: # 对第一个元素进行去重continueleft: int index 1right: int len(nums) - 1while left right:if nums[index] nums[left] nums[right] 0:right - 1elif nums[index] nums[left] nums[right] 0:left 1else:result.append([nums[index], nums[left], nums[right]])while left right and nums[left] nums[left 1]: # 对剩余两个元素进行去重left 1while left right and nums[right] nums[right - 1]:right - 1left 1right - 1return result1.9 四数之和
18. 四数之和
给你一个由 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: # 剪枝breakif i 0 and nums[i] nums[i-1]: # 去重continuefor j in range(i1, len(nums)):if nums[i] nums[j] target and target 0: # 剪枝breakif j i1 and nums[j] nums[j-1]: # 去重continue left: int j 1right: int len(nums) - 1while left right:s: int nums[i] nums[j] nums[left] nums[right]if s target:left 1elif s target:right - 1else:result.append([nums[i], nums[j], nums[left], nums[right]])while left right and nums[left] nums[left1]:left 1while left right and nums[right] nums[right-1]:right - 1left 1right - 1return resultReference
[1] Hello 算法 [2] 代码随想录
