我要评论代码随想录训练营 day6打卡 哈希表part01
一、 哈希表理论基础
哈希表（hash table）是一种基于哈希函数的高效数据结构，用于快速存储和查找数据。哈希表通过将键（key）映射到一个索引位置来实现，这个索引位置在哈希表的底层数组中存储值（value）。
哈希函数
哈希函数（hash function）是哈希表的核心，它接受输入（键）并返回一个整数（哈希值），这个整数通常是数组的索引。理想的哈希函数应当：
- 均匀分布：不同的输入应均匀分布到不同的索引位置，避免碰撞。
- 确定性：相同的输入必须始终返回相同的哈希值。
- 高效计算：哈希函数应快速计算，以保持插入和查找的高效性。
碰撞解决
由于哈希函数的输出范围有限，不同的输入可能映射到同一个索引位置，称为碰撞（collision）。解决碰撞的方法有多种：
- 链地址法（chaining）：在每个索引位置存储一个链表（或其他结构）来处理多个键值对。
- 开放地址法（open addressing）：在碰撞发生时，查找表内的下一个空位置来存储值。
python中的哈希表
在python中，哈希表由内置的dict类型和set类型实现。
python中的dict类型
字典（dictionary）是python内置的哈希表类型，它以键值对（key-value pair）的形式存储数据。字典的键必须是可哈希的（即具有__hash__方法和可比较性）。
# 创建字典
my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
# 添加元素
my_dict['date'] = 4
# 访问元素
print(my_dict['apple']) # 输出: 1
# 删除元素
del my_dict['banana']
# 检查键是否存在
if 'cherry' in my_dict:
print('cherry is in the dictionary')
# 遍历字典
for key, value in my_dict.items():
print(f'{key}: {value}')
python中的set类型
集合（set）也是一种基于哈希表的数据结构，它仅存储键而不存储值，用于高效的成员检测和去重操作。
# 创建集合
my_set = {'apple', 'banana', 'cherry'}
# 添加元素
my_set.add('date')
# 删除元素
my_set.remove('banana')
# 检查元素是否存在
if 'cherry' in my_set:
print('cherry is in the set')
# 遍历集合
for item in my_set:
print(item)
哈希表的性能
-
时间复杂度：
平均情况下，哈希表的插入、删除和查找操作的时间复杂度为o(1)。
在最坏情况下（哈希冲突严重），时间复杂度可能退化为o(n)。 -
空间复杂度：
哈希表需要额外的存储空间来存储键值对和处理冲突的结构（如链表）。
使用哈希表的注意事项
- 选择合适的哈希函数：确保哈希函数能均匀分布输入，减少冲突。
- 避免过度装填：装载因子（load factor）应适中，过高的装载因子会导致冲突增多，影响性能。
- 处理不可哈希类型：字典和集合的键必须是不可变的可哈希类型，如数字、字符串、元组等。
二、力扣242.有效的字母异位词
算法思路
为了判断两个字符串s和t是否为字母异位词，我们采用基于计数数组的算法。首先，定义一个大小为26的数组record，用于统计s中字符’a’到’z’的出现次数。通过s[i] - 'a’计算每个字符的数组下标，遍历s时在对应位置增加计数。
接着，同样遍历t，但在record数组的对应位置减少计数。最后，检查record数组所有元素是否为0，如果是，说明s和t字符出现次数一致，是异位词，返回true；否则，返回false。
时间复杂度为o(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为o(1)。
版本一 使用数组作为哈希表
代码思路
- 创建一个长度为26的数组record，用于记录每个字母出现的次数。
- 遍历字符串s，增加对应字母的计数。
- 遍历字符串t，减少对应字母的计数。
- 最后检查数组record，如果所有元素都为0，说明s和t是字母异位词，否则不是。
class solution:
def isanagram(self, s: str, t: str) -> bool:
record = [0] * 26 # 创建一个长度为26的数组记录字母出现的次数
for i in s:
record[ord(i) - ord("a")] += 1 # 增加对应字母的计数
for i in t:
record[ord(i) - ord("a")] -= 1 # 减少对应字母的计数
for i in range(26):
if record[i] != 0:
return false # 如果有元素不为0，说明字符串s和t的字母出现次数不一致
return true # 所有元素都为0，说明s和t是字母异位词
版本二 使用defaultdict
代码思路
- 使用defaultdict创建两个字典，分别记录字符串s和t中每个字母出现的次数。
- 遍历字符串s，增加对应字母的计数。
- 遍历字符串t，增加对应字母的计数。
- 最后比较两个字典，如果相等，说明s和t是字母异位词，否则不是。
class solution:
def isanagram(self, s: str, t: str) -> bool:
from collections import defaultdict
s_dict = defaultdict(int) # 创建用于记录字符串s中每个字母出现次数的字典
t_dict = defaultdict(int) # 创建用于记录字符串t中每个字母出现次数的字典
for x in s:
s_dict[x] += 1 # 增加s_dict中对应字母的计数
for x in t:
t_dict[x] += 1 # 增加t_dict中对应字母的计数
return s_dict == t_dict # 比较两个字典是否相等
版本三 使用counter
代码思路
- 使用counter类分别统计字符串s和t中每个字母出现的次数。
- 比较两个counter对象，如果相等，说明s和t是字母异位词，否则不是。
class solution(object):
def isanagram(self, s: str, t: str) -> bool:
from collections import counter
a_count = counter(s) # 统计字符串s中每个字母出现的次数
b_count = counter(t) # 统计字符串t中每个字母出现的次数
return a_count == b_count # 比较两个counter对象是否相等
方法一：使用数组作为哈希表，时间复杂度为o(n)，空间复杂度为o(1)，适用于字符集较小（如仅包含小写字母）的情况。
方法二：使用defaultdict，时间复杂度为o(n)，空间复杂度为o(n)，代码简洁，适用于字符集较大的情况。
方法三：使用counter，时间复杂度为o(n)，空间复杂度为o(n)，代码更简洁，适用于所有情况。
三、力扣349. 两个数组的交集
当题目明确说明输出结果中的每个元素一定是唯一的，并且可以不考虑输出结果的顺序时，暴力解法的时间复杂度为o(n^2)。使用哈希法可以进一步优化。
版本一 使用字典和集合
代码思路
- 使用字典存储nums1中的所有元素。
- 使用集合存储结果，遍历nums2，如果元素在字典中，则加入集合，并从字典中删除。
- 最终返回集合的列表形式。
class solution:
def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
# 使用哈希表存储nums1中的所有元素
table = {}
for num in nums1:
table[num] = table.get(num, 0) + 1
# 使用集合存储结果
res = set()
for num in nums2:
if num in table:
res.add(num)
del table[num] # 从哈希表中删除已找到的元素
return list(res) # 将集合转换为列表返回
版本二 使用数组
代码思路
- 创建两个长度为1001的数组count1和count2，分别记录nums1和nums2中元素的出现次数。
- 遍历nums1和nums2，更新对应数组的计数。
- 遍历0到1000，如果对应位置的两个数组计数都大于0，则说明该元素在两个数组中都出现过，加入结果列表。
class solution:
def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
count1 = [0]*1001 # 初始化计数数组
count2 = [0]*1001
result = []
for num in nums1:
count1[num] += 1 # 记录nums1中的元素出现次数
for num in nums2:
count2[num] += 1 # 记录nums2中的元素出现次数
for i in range(1001):
if count1[i] > 0 and count2[i] > 0: # 如果元素在两个数组中都出现过
result.append(i)
return result # 返回结果列表
版本三 使用集合
代码思路
- 使用集合记录nums1和nums2中的元素。
- 计算两个集合的交集并返回其列表形式。
class solution:
def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
return list(set(nums1) & set(nums2)) # 计算两个集合的交集并转换为列表返回
四、力扣202. 快乐数
版本一 使用集合检测循环
代码思路
- 使用一个集合 seen 来记录出现过的数字。如果一个数字再次出现，说明陷入了循环。
- 每次将数字替换为其各位数字平方和。
- 如果数字变为1，则返回 true；如果数字在集合中再次出现，则返回 false。
class solution:
def ishappy(self, n: int) -> bool:
seen = set() # 创建一个集合记录出现过的数字
while n != 1:
n = sum(int(i) ** 2 for i in str(n)) # 计算数字每位平方和
if n in seen: # 如果数字在集合中再次出现，说明陷入循环
return false
seen.add(n) # 将当前数字加入集合
return true # 数字变为1，返回true
版本二 使用列表检测循环
代码思路
- 使用一个列表 seen 来记录出现过的数字。如果一个数字再次出现，说明陷入了循环。
- 每次将数字替换为其各位数字平方和。
- 如果数字变为1，则返回 true；如果数字在列表中再次出现，则返回 false。
class solution:
def ishappy(self, n: int) -> bool:
seen = [] # 创建一个列表记录出现过的数字
while n != 1:
n = sum(int(i) ** 2 for i in str(n)) # 计算数字每位平方和
if n in seen: # 如果数字在列表中再次出现，说明陷入循环
return false
seen.append(n) # 将当前数字加入列表
return true # 数字变为1，返回true
版本三 快慢指针法检测循环
代码思路
- 使用快慢指针法检测数字序列是否存在循环（类似于链表中的环检测）。
- 快指针每次移动两步，慢指针每次移动一步。
- 如果两个指针相遇，说明存在循环，返回 false。
- 如果快指针变为1，返回 true。
class solution:
def ishappy(self, n: int) -> bool:
slow = n # 慢指针初始化为n
fast = n # 快指针初始化为n
# 使用快慢指针法检测循环
while self.get_sum(fast) != 1 and self.get_sum(self.get_sum(fast)) != 1:
slow = self.get_sum(slow) # 慢指针每次移动一步
fast = self.get_sum(self.get_sum(fast)) # 快指针每次移动两步
# 如果快慢指针相遇，说明存在循环，不是快乐数
if slow == fast:
return false
# 如果快指针遇到1，说明是快乐数
return true
def get_sum(self, n: int) -> int:
new_num = 0 # 初始化新数值为0，用于存储各位数字平方和
while n:
n, r = divmod(n, 10) # 使用divmod函数同时计算n除以10的商和余数
new_num += r ** 2 # 将当前位数字的平方累加到new_num中
return new_num # 返回所有位数字平方和的结果
版本一：使用集合检测循环。通过记录已经出现过的数字，检测是否陷入循环。空间复杂度为o(n)，时间复杂度为o(log n)。
版本二：使用列表检测循环。原理与方法一相同，只是使用列表记录出现过的数字。空间复杂度为o(n)，时间复杂度为o(log n)，但查找时间复杂度较高。
版本三：使用快慢指针法。通过快慢指针检测循环，空间复杂度为o(1)，时间复杂度为o(log n)。适合大数据量的情况。
五、力扣1. 两数之和
版本一 使用字典
代码思路
- 使用一个字典 records 来存放访问过的元素及其对应的下标。
- 遍历数组 nums，对于每个元素 value，计算其对应的补数 target - value。
- 如果补数存在于 records 中，说明找到了两个数的和为 target，返回它们的下标。
- 如果补数不存在，则将当前元素 value 及其下标 index 存入字典 records 中。
class solution:
def twosum(self, nums: list[int], target: int) -> list[int]:
records = dict() # 创建一个字典来记录访问过的元素及其下标
for index, value in enumerate(nums):
if target - value in records: # 在字典中寻找是否有匹配的key
return [records[target - value], index] # 找到匹配对，返回下标
records[value] = index # 将访问过的元素和下标加入到字典中
return [] # 如果没有找到匹配对，返回空列表
版本二 使用集合
代码思路
- 使用一个集合 seen 来存储已经访问过的数字。
- 遍历数组 nums，对于每个元素 num，计算其对应的补数 target - num。
- 如果补数存在于集合 seen 中，说明找到了两个数的和为 target，返回它们的下标。
- 如果补数不存在，则将当前元素 num 加入集合 seen 中。
class solution:
def twosum(self, nums: list[int], target: int) -> list[int]:
seen = set() # 创建一个集合来存储访问过的数字
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # 在集合中寻找是否有匹配的数字
return [nums.index(complement), i] # 找到匹配对，返回下标
seen.add(num) # 将当前元素加入集合
return [] # 如果没有找到匹配对，返回空列表
版本三 使用双指针
代码思路
- 对输入列表 nums 进行排序，生成一个新的有序列表 nums_sorted。
- 使用双指针 left 和 right，分别指向排序后列表的头和尾。
- 计算双指针指向元素的和 current_sum。
- 如果 current_sum 等于 target，则找到两个数，返回它们在原列表中的下标。
- 如果 current_sum 小于 target，将左指针右移。
- 如果 current_sum 大于 target，将右指针左移。
class solution:
def twosum(self, nums: list[int], target: int) -> list[int]:
nums_sorted = sorted(nums) # 对输入列表进行排序
left = 0
right = len(nums_sorted) - 1
while left < right:
current_sum = nums_sorted[left] + nums_sorted[right]
if current_sum == target:
# 找到和等于目标数的两个数，返回它们在原列表中的下标
left_index = nums.index(nums_sorted[left])
right_index = nums.index(nums_sorted[right])
if left_index == right_index: # 处理相同元素的情况
right_index = nums[left_index+1:].index(nums_sorted[right]) + left_index + 1
return [left_index, right_index]
elif current_sum < target:
left += 1 # 总和小于目标，左指针右移
else:
right -= 1 # 总和大于目标，右指针左移
return [] # 如果没有找到匹配对，返回空列表
版本一：使用字典：时间复杂度为o(n)，空间复杂度为o(n)，适用于数值范围较大的情况。
版本二：使用集合：时间复杂度为o(n)，空间复杂度为o(n)，代码简洁，但在返回下标时需要额外处理。
版本三：使用双指针：时间复杂度为o(nlogn)，因为需要先排序，空间复杂度为o(n)，适用于需要排序并找到匹配对的情况。
发表评论