昨日回顾
昨天我们开始了哈希表的学习，讲解了哈希表的集中实现方式。并通过一道 设计哈希集合 的题目，让我们将哈希表的理论转化为实践。
今天，我们就开始正式学习哈希表在Python与Java中的使用方式。在Java中，哈希表有两个数据类型 HashMap 与 HashSet，它们对应Python中的 dict 与 set ，下面我们开始分类学习！
HashSet & set
我们在昨天的设计哈希集合题目中，对HashSet已经有了一个初步的了解。HashSet与set 是一个无序不重复的元素集，集合在我们日常算法中对数组去重、已搜索的节点记录等有很大帮助。
具体方法如下：
| 操作 | Python | Java |
| 初始化 | s = set() | HashSet<Integer> s = new HashSet<>(); |
| 增加 | s.add(1) | s.add(1) |
| 删除 | s.remove(1) 不存在报错 s.discard(2) 不存在不报错 s.pop()随机弹出并返回 |
s.remove(1) 不存在不报错 |
| 包含 | 1 in s | s.contains(1) |
| 获取长度 | len(s) | s.size() |
| 清空 | s.clear() | s.clear() |
| 查看是否为空 | if not s | s.isEmpty() |
Python针对集合还可存在update更新、difference 并可以使用 | & 等方法，但在算法中的使用频度并不高，大家下来可以自行复习。
HashMap & dict
就如力扣 twoSum 这道题中，题目要求我们在数组中查找等于 target 的两个元素，并返回这两个数字的下标。如果只是判断能否找到这两个数，我们初始化一个HashSet，在遍历数组的过程中检查target - num 是否在存在HashSet中，如果找到直接返回True，否则将当前数字保存至HashSet中。
但既然要返回下标，就需要在保存数字的同时记录该数字的下标。使用方式如下图：
让我们来看看Python和Java中HashMap 和dict 都有哪些方法吧：
| 操作 | Python | Java |
| 初始化 | d = {} d = dict() | HashMap<Integer,Integer> d = new HashMap<>(); |
| 增加键值对、已存在则修改 | d[2] = 0 | d.put(2,0); |
| 获取key对应value | d[2] | d.get(2) |
| 获取key，不存在则返回默认 | d.get(3, -1) | d.getOrDefault(3, -1) |
| 删除某个键 | del d[5] 不存在报错 d.pop(5, -1) 不存在返回默认值机 d.popitem() 随机删除一个键值对 |
d.remove(5) 不存在不报错 |
| 当key不存在时添加 | d.setdefault(9, 0) | d.putIfAbsent(9, 0) |
| 获取长度 | len(s) | s.size() |
| 包含 | 1 in s | s.contains(1) |
| 清空 | s.clear() | s.clear() |
| 查看是否为空 | if not s | s.isEmpty() |
剩余一些通用的d.keys() d.values() d.items()获取字典所有键、值、键值对等就不再赘述了，大家下来可以自行复习。
关于HashSet、set和HashMap、dict的相关知识就复习到这里。下来让我们做第一题熟悉熟悉？嗯...还是换个稍微有点难度的吧。
剑指OfferII032.有效的变位词
https://leetcode-cn.com/problems/dKk3P7/solution/shua-chuan-jian-zhi-offer-day15-ha-xi-bi-5pqx/
难度：简单
题目
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。
注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
提示:
- 1 <= s.length, t.length <= 5 * 10 ^ 4
- s and t 仅包含小写字母
示例
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 示例 3: 输入: s = "a", t = "a" 输出: false
分析
在不看进阶的情况下，这道题其实用不到哈希表，因为s和t只包含小写字母，我们在字符串和数组那章节已经讲过了这种题目的快速解法。
我们通过构造一个长度为26的数组对应26个英文字母(嗯...突然想起，谭警官的28个英文字母倒背如流，怕了怕了...)
通过字符串与ascii对应的方式完成匹配，这套路用的太多就不细讲了。
但是，进阶中说了，如果字符串包含unicode字符串怎么办？
怎么办，凉拌....直接上哈希表就行了啊！
其他操作和数据没什么区别，只是换成了哈希表的对应方法而已么。
数组解题
Python:
class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t) or s == t: return False comp = [0] * 26 for i in s: comp[ord(i) - 97] += 1 for j in t: index = ord(j) - 97 if comp[index] < 1: return False comp[index] -= 1 return True
Python:
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length() || s.equals(t)) { return false; } int[] arr = new int[26]; for (char i:s.toCharArray()) { arr[i - 97]++; } for (char j:t.toCharArray()) { arr[j - 97]--; if (arr[j - 97] < 0){ return false; } } return true; } }
哈希表解题
Python:
class Solution: def isAnagram(self, s: str, t: str) -> bool: return s != t and Counter(s) == Counter(t)
Python:
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length() || s.equals(t)) { return false; } HashMap<Character, Integer> arr = new HashMap<>(); for (char i : s.toCharArray()) { arr.put(i, arr.getOrDefault(i, 0) + 1); } for (char j : t.toCharArray()) { if (!arr.containsKey(j) || arr.get(j) == 0) return false; arr.put(j, arr.get(j) - 1); } return true; } }
不得不说Python做这种类型的题目简直是无脑啊....请恕我偷懒了，哈哈。
经过这道简单题的铺垫，再来看下面这道中等题，可以说就那会儿事儿....手速题而已！
剑指OfferII033.变位词组
https://leetcode-cn.com/problems/sfvd7V/solution/shua-chuan-jian-zhi-offer-day15-ha-xi-bi-p57n/
难度：中等
题目
给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
提示：
- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
- strs[i] 仅包含小写字母
示例
示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2: 输入: strs = [""] 输出: [[""]] 示例 3: 输入: strs = ["a"] 输出: [["a"]]
分析
这道题在难度方面并不高，思路其实剑指OfferII032类似的：
- 我们创建一个哈希表s，key 为String，value 为List
- 然后循环列表中的每个字符串，先将字符串排序
- 再看排序后的字符串是否在哈希表中，如果在则追加，如果不在单独开辟一对key:value即可
- 最终将哈希表的value值转化为列表返回即可。
但对于 Python 这里还有一个优化点的，如果按照上面的方式，我们需要创建一个哈希表嵌套列表的操作。
而且最终有需要将哈希表的value转化为列表再返回比较麻烦。
我们可以换个思路：
- 我们单独创建一个哈希表s和列表li
- 当哈希表中不存在排序后的字符串时，我们获取当前列表长度作为value(其实是列表的下标)
- 然后向哈希表中插入 key = 排序后的字符串, value = 该字符串在列表中的下标。
- 下次遇到同类型的字符串，我们直接在列表对应下标中插入该字符串即可。
解题
Python:
class Solution: def groupAnagrams(self, strs): ret = [] d = {} for i in strs: sort_i = ''.join(sorted(i)) if sort_i in d: ret[d[sort_i]].append(i) else: d[sort_i] = len(ret) ret.append([i]) return ret
Java:
class Solution { public List<List<String>> groupAnagrams(String[] strs) { HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); for (String str : strs) { char[] array = str.toCharArray(); Arrays.sort(array); String key = new String(array); ArrayList<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<List<String>>(map.values()); } }
好了，今天的哈希表学习就到这里，题目虽然基础，但是一定要练习啊！
