哈希表
常见的三种哈希结构
当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。
- 数组
- set (集合)
- map(映射)
这里数组就没啥可说的了,我们来看一下 set。
在 C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:
集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
std::multiset | 红黑树 | 有序 | 是 | 否 | O(log n) | O(log n) |
std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set 底层实现为哈希表,std::set 和 std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以 key 值是有序的,但 key 不可以修改,改动 key 值会导致整棵树的错乱,所以只能删除和增加。
映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::map | 红黑树 | key 有序 | key 不可重复 | key 不可修改 | O(log n) | O(log n) |
std::multimap | 红黑树 | key 有序 | key 可重复 | key 不可修改 | O(log n) | O(log n) |
std::unordered_map | 哈希表 | key 无序 | key 不可重复 | key 不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表,std::map 和 std::multimap 的底层实现是红黑树。同理,std::map 和 std::multimap 的 key 也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。
当我们要使用集合来解决哈希问题的时候,优先使用 unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用 set,如果要求不仅有序还要有重复数据的话,那么就用 multiset。
那么再来看一下 map ,在 map 是一个 key value 的数据结构,map 中,对 key 是有限制,对 value 没有限制的,因为 key 的存储方式使用红黑树实现的。
其他语言例如:java 里的 HashMap ,TreeMap 都是一样的原理。可以灵活贯通。
虽然 std::set 和 std::multiset 的底层实现基于红黑树而非哈希表,它们通过红黑树来索引和存储数据。不过给我们的使用方式,还是哈希法的使用方式,即依靠键(key)来访问值(value)。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。std::map 也是一样的道理。
242.有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
解答:
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
int[] str1 = new int[128];
int[] str2 = new int[128];
for(int i = 0;i < s.length();i++){
str1[s.charAt(i)]++;
str2[t.charAt(i)]++;
}
if(Arrays.equals(str1,str2)) return true;
else return false;
}
}
49.字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]
仅包含小写字母
解答:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map= new HashMap<>();
for(String s : strs){
char[] ss = s.toCharArray();
Arrays.sort(ss);
String key = new String(ss);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(s);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
438. 找到字符串中所有字母异位词
给定两个字符串 s
和 p
,找到 s
中所有 p
的
异位词
的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词 。
解答:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] str1 = new int[128];
for(char c : p.toCharArray()) str1[c]++;
int left = 0,right = 0;
while(right < s.length()){
str1[s.charAt(right)]--;
while(str1[s.charAt(right)] < 0){
str1[s.charAt(left)]++;
left++;
}
if(right - left + 1 == p.length()) res.add(left);
right++;
}
return res;
}
}
349. 两个数组的交集
题意:给定两个数组,编写一个函数来计算它们的交集。
说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
解答:
import java.util.Set;
import java.util.HashSet;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1.length == 0 || nums2.length == 0) return new int[0];
Set<Integer> res = new HashSet<>();
Set<Integer> set1 = new HashSet<>();
for(int i : nums1) set1.add(i);
for(int i = 0;i < nums2.length;i++){
if(set1.contains(nums2[i])){
res.add(nums2[i]);
}
}
int[] arr = new int[res.size()];
int j = 0;
for(int i : res){
arr[j++] = i;
}
return arr;
}
}
给你两个整数数组 nums1
和 nums2
,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
解答:
import java.util.Map;
import java.util.HashMap;
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
Map<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < nums1.length; i++){
map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1);
}
for(int i = 0; i < nums2.length; i++){
if(map.getOrDefault(nums2[i], 0) > 0){
list.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i]) - 1);
}
}
int[] arr = new int[list.size()];
int j = 0;
for(int i : list) arr[j++] = i;
return arr;
}
}
第 202 题. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 True ;不是,则返回 False 。
示例:
输入:19 输出:true 解释: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
解答:
class Solution {
public boolean isHappy(int n) {
Set<Integer> set1 = new HashSet<>();
while(n != 1 && !set1.contains(n)){
set1.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {
int temp = n%10;
int sum = temp*temp;
while(n/10 > 0){
n = n / 10;
temp = n%10;
sum += temp * temp;
}
return sum;
}
}