Day5 哈希表part01

哈希表理论基础

哈希表的意义

比如说，数组["小王", "小李", "小张", "小赵"]，我要找小李，那么就需要一个一个遍历，时间复杂度为O(n)，但是哈希表，是寻找哈希值，然后直接寻找对应的值，这个只需要O(1)

所以比如说我们需要找一个内容是否在里面，使用哈希相关的数据结构，比如说字典/集合，只需要使用if "小张" in students:就可以直接找到

数组作为哈希表

数组可以作为一个哈希表，但是只能是简单的，比如说nums = [1, 2, 3, 4, 5] 这样子，可以利用F(x)= x， 然后我们判断nums[n]存不存在，就能知道这个值在不在这个数组里面。但是有缺陷，比如说一个很大的数，就需要一个很大的数组，或者一个字符串，你没办法给他设置对应的值，所以哈希表就出现了。

哈希表是什么

哈希表需要一个哈希函数，将一个元素转化成哈希表里的位置

比如说，hash("小王") → 13528，我们先计算出来哈希值，然后看哈希表的大小，比如说，哈希表只有10个位置，那么13528 % 10 = 8，于是“小王”被放到索引8。

哈希碰撞

因为哈希表大小比如10，那么必然会出现两个元素在同一个哈希表的位置里面，这就叫做哈希碰撞

解决哈希碰撞的方法

1. 拉链法：索引8 → 小王 → 小李 → 小张。

如果元素分布比较均匀，每个位置中的元素很少，查找依然很快。如果大量元素都挤在同一个位置，查找速度就会下降。

┌─────────┐ │ 桶 0 │ → NULL ├─────────┤ │ 桶 1 │ → ["小李"] → NULL ├─────────┤ │ 桶 2 │ → ["小张"] → ["小章"] → NULL ← 碰撞！两个元素挂在同一个桶 ├─────────┤ │ 桶 3 │ → ["小王"] → NULL └─────────┘

2. 线性探测法

如果目标位置已经有人了，就继续向后寻找空位。找到空位就放进去

线性探测示例：插入 "小章"，hash=2，但桶2已有"小张" → 检查桶3：已被"小王"占用 → 检查桶4：空！存入"小章" ┌──────┬──────┬──────┬──────┬──────┐ │ 桶0 │ 桶1 │ 桶2 │ 桶3 │ 桶4 │ │ NULL │"小李"│"小张"│"小王"│"小章"│ ← 被挤到了这里 └──────┴──────┴──────┴──────┴──────┘

数组/ set/ map

数组

当数据范围比较小、比较固定，并且能转换成数组下标时，可以使用数组。

数组的优点：

• 访问速度快；
• 内存结构简单；
• 在范围较小时很适合。

缺点：

• 必须知道数据范围；
• 数据范围很大时，可能浪费空间；
• 字符串、复杂对象不能直接作为下标。

set

set是集合，只保存元素，不保存次数或者其他附加信息。

特点：

• 元素不能重复；
• 查询速度通常很快；
• 无法通过下标访问；
• 不保证按照插入顺序完成算法逻辑。

map

不仅要判断是否出现，还要记录次数、位置或对应关系时，使用dict。

如何选择数组、set、dict

数组：通过下标访问数据
set：只记录某个元素是否存在
map：记录一个元素对应的其他信息

242. 有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。 示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 提示: 1 <= s.length, t.length <= 5 * 104 s 和 t 仅包含小写字母

思路

1. 因为是26个小写字母，并不大，所以我们采用数组作为哈希表来做，这个字母的大小作为列表的第n个

代码

1. 使用的是数组作为哈希表

class Solution: def isAnagram(self, s: str, t: str) -> bool: record = [0] * 26 for i in s: #并不需要记住字符a的ASCII，只要求出一个相对数值就可以了 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: #record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。 return False return True

2. 使用defaultdict作为哈希表

class Solution: def isAnagram(self, s: str, t: str) -> bool: from collections import defaultdict s_dict = defaultdict(int) t_dict = defaultdict(int) for x in s: s_dict[x] += 1 for x in t: t_dict[x] += 1 return s_dict == t_dict

defaultdict

defaultdict是 Python 里一种“带默认值的字典”，普通dict在访问一个不存在的键时会报错；defaultdict可以自动给这个键创建一个默认值。

普通字典和defaultdict的区别

假设我们要统计字母出现次数，count={}, count['a'] += 1, 此时a还不在字典里面，会报错，需要先初始化，然后再进行+1操作。而defaultdict不会，因为当"a"不存在时，defaultdict 会自动帮你创建，他会先判断有没有这个元素，没有会赋值为0，又一个内置函数int()

传参和初始化

初始化：

from collections import defaultdict count = defaultdict(int)

传参：

from collections import defaultdict count = defaultdict(int)

可以传入int，list，set，都是可以的

defaultdict和普通dict的对比

普通字典：

count = {}

for ch in "apple":
count[ch] = count.get(ch, 0) + 1

使用get：

count = {}

for ch in "apple":
count[ch] = count.get(ch, 0) + 1

使用defaultdict

from collections import defaultdict

count = defaultdict(int)

for ch in "apple":
count[ch] += 1

defaultdict的一个特点

from collections import defaultdict

data = defaultdict(int)

print(data["a"])

而且访问之后，字典中真的会出现：

{"a": 0}

所以他的一个容易忽略的特点就是只进不出，就会有几个缺点：1. 脏数据污染，因为创建了{"a": 0}，算是脏数据 2. 内存泄漏，不断的查，就会不断地插入，就会有很多无用的数据占据空间

defaultdict常用情况

1. 统计字数

2. 数据分类

{'北京': ['张三', '李四'], '上海': ['王五']}按城市把人分到不同的“桶”里。

总结

1. 学会ASCII法，就是用ord(i) - ord("a")

2. 了解defaultdict

题目链接

242. 有效的字母异位词 - 力扣（LeetCode）

349. 两个数组的交集

题目

给定两个数组nums1和nums2，返回它们的 交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]解释：[4,9] 也是可通过的

思路

1. 还没看题解：直接把其中一个变成defaultdict，然后另外一个去判断，同时这个变成set去重，在不在里面，在里面就提出来，不在里面就算了

2. 首先判断大小，如果数值很多，就用set或者map，值不多用列表即可

代码

我写的代码

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: set1 = set(nums1) set2 = set(nums2) set3 = set() for i in set2: if i in set1: set3.add(i) return list(set3)

官方代码

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: # 使用哈希表存储一个数组中的所有元素 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)

题目链接

349. 两个数组的交集 - 力扣（LeetCode）

202. 快乐数

题目

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

「快乐数」定义为：

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

如果n是快乐数就返回true；不是，则返回false。

示例 1：

输入：n = 19输出：true解释：1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2输出：false

思路

1. 没看题解之前： 没思路

2. 思路就是，看有没有重复，比如说我用一个set，每次都添加进入，比如说82，68，100...，然后下一个数字看有没有在set里面，如果有，就是不快乐数，如果为1，就为快乐数

代码

1. 自己写的

class Solution: def isHappy(self, n: int) -> bool: set1 = set() while True: if n == 1: return True elif n != 1 and n not in set1: set1.add(n) elif n in set1: return False n = self.getSum(n) def getSum(self, n: int) -> int: temp = 0 sum = 0 while n >= 1: temp = n % 10 sum += temp ** 2 n = (n - temp) / 10 return sum

2. 官方代码

class Solution: def isHappy(self, n: int) -> bool: record = set() while True: n = self.get_sum(n) if n == 1: return True # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数 if n in record: return False else: record.add(n) def get_sum(self,n: int) -> int: new_num = 0 while n: n, r = divmod(n, 10) new_num += r ** 2 return new_num

学习的点

1. 内置函数：n, r = divmod(n, 10) 用于计算整除结果和余数，n是商，r是余数

题目链接

202. 快乐数 - 力扣（LeetCode）

两数之和

题目

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6输出：[0,1]

思路

1. 还没看题解：我觉得用一个字典，然后每次提出来一个数字，然后去掉这个数-1，然后用target剪掉这个数，然后看看结果在不在里面

代码

from collections import defaultdict class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: count = defaultdict(int) num = 0 list1 = [0] * 2 list2 = [9] * 2 flag = 0 for i in nums: count[i] += 1 print(count) for key, value in count.items(): print("key") print(key) print("value") print(value) count[key] -= 1 print(count) num = target - key print(num) if num in count and count[num] != 0: print("in") list1[0] = key list1[1] = num break now = 0 if list1[0] == list1[1]: for i in nums: if i == list1[0] and flag == 0: list2[0] = now flag += 1 elif i == list1[1] and flag == 1: list2[1] = now now += 1 now = 0 if list1[0] != list1[1]: for i in nums: if i == list1[0]: list2[0] = now elif i == list1[1]: list2[1] = now now += 1 return list2

运行结果不对，没有通过那个数据集大小，因为太多无效的东西了，整体思路问题不大，但是代码实现比较差

2. 看了官方解析，需要dict来记录我们已经看过的元素，要记录元素和位置。然后我们计算target-当前数字，看看结果在不在dict里面，如果在说明在之前记录过，这样就不会出现连续两个相同的数字，在dict里面不能有两个相同的保存在里面

from collections import defaultdict class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict1 = {} for i in range(len(nums)): diff = target - nums[i] if diff in dict1: return [dict1[diff], i] else: dict1[nums[i]] = i

3. 官方代码

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: # 遍历当前元素，并在map中寻找是否有匹配的key return [records[target- value], index] records[value] = index # 如果没找到匹配对，就把访问过的元素和下标加入到map中 return []

总结

1. 主要就是要想到需要一个dict来保存数字和位置，并且很重点的是保存的是浏览过的，而不是把整个数组保留进去，这很重要