简洁的门户网站,四川鼎能建设集团网站,python 做网站,网站进行规划与设计【LeetCode 面试经典150题】详细题解之哈希表篇 1 哈希表的基础1.1 基础概念及实现1.2.1 哈希表的工作原理1.2.2 705.设计哈希集合1.2.3 706.设计哈希映射 1.2 HashMap相关1.2.1 基本操作1.2.2 遍历 1.3 Hashtable1.4 LinkedHashMap1.5 HashSet**1.5.1基本特性**1.5.2 基本方法… 【LeetCode 面试经典150题】详细题解之哈希表篇 1 哈希表的基础1.1 基础概念及实现1.2.1 哈希表的工作原理1.2.2 705.设计哈希集合1.2.3 706.设计哈希映射 1.2 HashMap相关1.2.1 基本操作1.2.2 遍历 1.3 Hashtable1.4 LinkedHashMap1.5 HashSet**1.5.1基本特性**1.5.2 基本方法1.5.3 注意事项 2 383.赎金信2.1 思路2.2 代码 3 205.同构字符串3.1 思路3.2 代码 4 290.单词规律4.1 分析4.2 代码 5 242.有效的字母异位词5.1 思路5.2 代码 6 49. 字母异位词分组6.1 思路6.2 代码 7 1.两数之和7.1 思路7.2 代码 8 202.快乐数 需要复习8.1 思路8.2 代码 9 219.存在重复元素II9.1 思路9.2 代码 10 128.最长连续序列10.1 思路10.2 代码 1 哈希表的基础
12.23 一刷
哈希表是一种基于哈希算法实现的键值对集合提供了快速的数据插入、删除和查找功能。Java提供了HashMap、Hashtable和LinkedHashMap等实现哈希表的类。以下是Java哈希表的一些基础概念和操作
1.1 基础概念及实现
1.2.1 哈希表的工作原理
哈希表通过哈希函数将键Key映射到哈希表的索引上然后通过这个索引来访问值Value。如果两个键的哈希值相同哈希冲突则通过链表或其他方法来解决冲突。
1.2.2 705.设计哈希集合
705. 设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合HashSet。
实现 MyHashSet 类
void add(key) 向哈希集合中插入值 key 。bool contains(key) 返回哈希集合中是否存在这个值 key 。void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值什么也不做。
class MyHashSet {/**hash函数用于将key映射到数组中用链表法来解决哈希冲突当两个不同的数映射到数组的同一位置时将该数接到数组位置的链表后面*///定义hash表的长度为769private static final int BASE 769;private LinkedList[] list;public MyHashSet() {//初始化哈希表list new LinkedList[BASE]; //初始化LinkedListfor(int i 0;iBASE;i){list[i] new LinkedListInteger();}}public void add(int key) {int h hash(key);//找到key映射到hash表中的位置IteratorInteger iter list[h].iterator();while(iter.hasNext()){Integer element iter.next();if(element key){return;}}list[h].offerLast(key);}public void remove(int key) {int h hash(key);IteratorInteger iter list[h].iterator();while(iter.hasNext()){Integer element iter.next();if(element key){list[h].remove(element);return;}}}public boolean contains(int key) {int h hash(key);IteratorInteger iter list[h].iterator();while(iter.hasNext()){int element iter.next();if(element key){return true;}}return false;}private static int hash(int key){return key % BASE;}
}/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet obj new MyHashSet();* obj.add(key);* obj.remove(key);* boolean param_3 obj.contains(key);*/1.2.3 706.设计哈希映射
706. 设计哈希映射
已解答
不使用任何内建的哈希表库设计一个哈希映射HashMap。
实现 MyHashMap 类
MyHashMap() 用空映射初始化对象void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中则更新其对应的值 value 。int get(int key) 返回特定的 key 所映射的 value 如果映射中不包含 key 的映射返回 -1 。void remove(key) 如果映射中存在 key 的映射则移除 key 和它所对应的 value 。
class MyHashMap {/**感觉和上一个哈希表的题差不多根据key映射到哈希表数组中的位置。只是此时哈希表中的每个元素都应该后面还跟着value不再是Integer了*///定义一个Pairprivate class Pair{private int key;private int value;public Pair(int key,int value){this.key key;this.value value;}public int getKey(){return key;}public int getValue(){return value;}public void setValue(int value){this.value value;}}private static final int BASE 769;LinkedList[] list ;public MyHashMap() {list new LinkedList[BASE];for(int i 0;iBASE;i){list[i] new LinkedListPair();}}public void put(int key, int value) {int h hash(key);IteratorPair iter list[h].iterator();while(iter.hasNext()){Pair pair iter.next();if(pair.getKey()key){pair.setValue(value);return;}}list[h].offerLast(new Pair(key,value));}public int get(int key) {int h hash(key);IteratorPair iter list[h].iterator();while(iter.hasNext()){Pair pair iter.next();if(pair.getKey()key){return pair.getValue();}}return -1;}public void remove(int key) {int h hash(key);IteratorPair iter list[h].iterator();while(iter.hasNext()){Pair pair iter.next();if(pair.getKey()key){list[h].remove(pair);return;}}}private int hash(int key){return key % BASE;}
}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj new MyHashMap();* obj.put(key,value);* int param_2 obj.get(key);* obj.remove(key);*/1.2 HashMap相关
HashMap是Java中使用最广泛的哈希表实现它基于Map接口允许键值对中的键Key和值Value为null并且不保证映射的顺序。
HashMapString, Integer map new HashMap();
map.put(key1, 1);
map.put(key2, 2);
Integer value map.get(key1); // 返回1
map.remove(key2);1.2.1 基本操作
put(K key, V value)将指定的值与此映射中的指定键关联。get(Object key)返回指定键所映射的值。remove(Object key)如果存在一个键的映射关系则将其从映射中移除。keySet()返回映射中包含的键的Set视图。values()返回映射中包含的值的Collection视图。entrySet()返回映射中包含的键值映射关系的Set视图
1.2.2 遍历
使用 entrySet()
entrySet() 方法返回哈希表中所有键值对的 Set 视图。这个集合中的每个元素都是一个 Map.Entry 对象其中包含键和值。
HashMapString, Integer map new HashMap();
map.put(key1, 1);
map.put(key2, 2);
map.put(key3, 3);for (Map.EntryString, Integer entry : map.entrySet()) {String key entry.getKey();Integer value entry.getValue();System.out.println(key value);
}使用 keySet()
keySet() 方法返回哈希表中所有键的 Set 视图。通过这个集合遍历所有的键然后使用每个键来获取对应的值。
for (String key : map.keySet()) {Integer value map.get(key);System.out.println(key value);
}使用 values()
如果你只对值感兴趣可以使用 values() 方法获取哈希表中所有值的 Collection 视图。
for (Integer value : map.values()) {System.out.println(value);
}使用 forEach 增强型 for 循环Java 8
Java 8 引入了 forEach 方法它允许使用增强型 for 循环的语法来遍历 Collection。
map.forEach((key, value) - System.out.println(key value));使用迭代器 Iterator
使用迭代器 Iterator 来遍历哈希表可以避免在遍历时修改集合导致的 ConcurrentModificationException。
IteratorMap.EntryString, Integer iterator map.entrySet().iterator();
while (iterator.hasNext()) {Map.EntryString, Integer entry iterator.next();System.out.println(entry.getKey() entry.getValue());
}注意事项
当遍历哈希表时如果需要修改哈希表增加或删除元素推荐使用迭代器 Iterator 的 remove 方法或者在外部使用 removeIf 方法。entrySet()、keySet() 和 values() 返回的视图反映了哈希表的当前状态如果哈希表被修改视图也会相应地变化。遍历哈希表的时间复杂度是 O(n)其中 n 是哈希表中的元素数量。
1.3 Hashtable
Hashtable是遗留类也实现了Map接口但它是同步的不允许键或值为null并且它的性能通常不如HashMap。
HashtableString, Integer htable new Hashtable();
htable.put(key1, 1);
htable.put(key2, 2);
Integer value htable.get(key1); // 返回1
htable.remove(key2);1.4 LinkedHashMap
LinkedHashMap是HashMap的一个子类它维护了元素的插入顺序或者访问顺序取决于构造函数的参数。
LinkedHashMapString, Integer lmap new LinkedHashMap();
lmap.put(key1, 1);
lmap.put(key2, 2);
Integer value lmap.get(key1); // 返回1
lmap.remove(key2);1.5 HashSet
HashSet 是 Java 中的一个集合类它实现了 Set 接口不允许集合中有重复的元素。HashSet 的行为是由 HashMap 实现的它使用哈希表来存储元素因此具有很高的添加、删除和搜索效率。以下是 HashSet 的一些基础知识和遍历方法
1.5.1基本特性
不允许重复HashSet 不允许存储重复元素。无序HashSet 中的元素是无序的这意味着元素插入和取出的顺序不一定相同。非线程安全HashSet 是非线程安全的如果需要线程安全可以使用 Collections.synchronizedSet 或 CopyOnWriteArraySet。
1.5.2 基本方法
// 创建
HashSetString set new HashSet();
//添加
set.add(element1);
set.add(element2);
//删除
boolean removed set.remove(element1); // 返回 true 如果元素被移除false 如果元素不存在// 判断元素是否存在
boolean contains set.contains(element1); // 返回 true 如果元素存在false 否则// 遍历1
for (String element : set) {System.out.println(element);
}// 遍历2
IteratorString iterator set.iterator();
while (iterator.hasNext()) {String element iterator.next();System.out.println(element);
}// 遍历3
set.forEach(element - System.out.println(element));// 遍历4
set.stream().forEach(System.out::println);
1.5.3 注意事项
HashSet 中的元素顺序不可预测如果你需要有序的集合可以考虑使用 TreeSet。由于 HashSet 依赖于哈希函数某些情况下可能会遇到哈希冲突但 Java 的实现已经足够高效冲突通常不会影响性能。当遍历或迭代 HashSet 时如果需要修改集合应该使用迭代器的 remove 方法或者在外部使用 removeIf 方法。
2 383.赎金信
383. 赎金信
简单
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1
输入ransomNote a, magazine b
输出false示例 2
输入ransomNote aa, magazine ab
输出false示例 3
输入ransomNote aa, magazine aab
输出true提示
1 ransomNote.length, magazine.length 105ransomNote 和 magazine 由小写英文字母组成
2.1 思路 简单字符可以用长度为26的数组来记录字符出现的次数 两个哈希表记录ransomNote和magazin两个字符串中字符出现的次数之后再一一比较由于是简单的字符所以可以用两个长度为26的数组来记录字符出现的次数cnt_r[26]cnt_m[26]之后遍历cnt_r中的值判断cnt_r中的每个字符出现的数量是否大于cnt_m中该字符出现的数量。小于则直接返回false2.2 代码
class Solution {public boolean canConstruct(String ransomNote, String magazine) {/***/int[] cnt_r new int[26];int[] cnt_m new int[26];for(int i 0;iransomNote.length();i){cnt_r[ransomNote.charAt(i)-a];}for(int i 0;imagazine.length();i){cnt_m[magazine.charAt(i)-a];}for(int i 0;i26;i){if(cnt_r[i]cnt_m[i]){return false;}}return true;}
}3 205.同构字符串
205. 同构字符串
简单
给定两个字符串 s 和 t 判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t 那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符同时不改变字符的顺序。不同字符不能映射到同一个字符上相同字符只能映射到同一个字符上字符可以映射到自己本身。
示例 1:
输入s egg, t add
输出true示例 2
输入s foo, t bar
输出false示例 3
输入s paper, t title
输出true提示
1 s.length 5 * 104t.length s.lengths 和 t 由任意有效的 ASCII 字符组成
3.1 思路 第一遍的时候用1个hashmap这样会存在s-t一对一t-s多对多的问题 两个HashMap分别存储s- t的映射和t- s的映射 用一个HashMap存储s中字符到t的映射关系之后判断即可具体而言对于s和t假如是同构的那么s中的所有字符都能映射到t中。即map[s[i]] t[i] 会对所有的i都满足。反之假如不满足上面条件则说明不同构。举例s egg,t add遍历s和t中的每个元素在第一个元素的时候得出映射关系为 e-a第二个元素 g-d第三个元素 g-d成立。具体实现则是维持两个HashMap分别存储s-t的映射和t-s的映射。因为一个的话会存在这种情况。s bacdt baba对于s中的字符满足唯一映射但是对于t中的比如b会映射到{b,c}不对。因此维持两个maps2t中以s字符为键映射至t的字符为值t2s中以t字符为键映射至s的字符为值从左到右遍历两个字符串更新哈希表。出现冲突时当前下标i对应的s[i]存在映射但是映射不为t[i]或者t[i]存在映射但是映射不为s[i]返回false3.2 代码
class Solution {public boolean isIsomorphic(String s, String t) {/***/int n s.length();MapCharacter,Character maps2t new HashMap();MapCharacter,Character mapt2s new HashMap();for(int i 0;in;i){char si s.charAt(i);char ti t.charAt(i);//冲突if(maps2t.containsKey(si) maps2t.get(si) ! ti){return false;}if(mapt2s.containsKey(ti) mapt2s.get(ti) ! si){return false;}maps2t.put(s.charAt(i),t.charAt(i));mapt2s.put(t.charAt(i),s.charAt(i));}return true;}
}4 290.单词规律
290. 单词规律
简单
给定一种规律 pattern 和一个字符串 s 判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配例如 pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern abba, s dog cat cat dog
输出: true示例 2:
输入:pattern abba, s dog cat cat fish
输出: false示例 3:
输入: pattern aaaa, s dog cat cat dog
输出: false提示:
1 pattern.length 300pattern 只包含小写英文字母1 s.length 3000s 只包含小写英文字母和 s 不包含 任何前导或尾随对空格s 中每个单词都被 单个空格 分隔
4.1 分析
和205.同构字符串差不多的题。简单题
4.2 代码
class Solution {public boolean wordPattern(String pattern, String s) {/**感觉和上一题一样都是维护两个map然后双向映射。思路差不多。*/String[] strs s.split( );if(strs.length!pattern.length()){return false;}MapCharacter,String c2strs new HashMap();MapString,Character strs2c new HashMap();for(int i 0;istrs.length;i){char c pattern.charAt(i);if(c2strs.containsKey(c) !c2strs.get(c).equals(strs[i])){return false;}if(strs2c.containsKey(strs[i]) strs2c.get(strs[i])!c ){return false;}c2strs.put(c,strs[i]);strs2c.put(strs[i],c);}return true;}
}5 242.有效的字母异位词
242. 有效的字母异位词
简单
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的 字母异位词。
示例 1:
输入: s anagram, t nagaram
输出: true示例 2:
输入: s rat, t car
输出: false提示:
1 s.length, t.length 5 * 104s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办你能否调整你的解法来应对这种情况
5.1 思路 分析不难 一个cnt数组1.将s中所有出现过的字母放入cnt中记录2.遍历t遇见一个t的字母就在cnt中减去对应的值。假如减之后cnt值0则s和t的字符一定不相同。返回false3.遍历cnt假如有不为0的数返回false5.2 代码
class Solution {public boolean isAnagram(String s, String t) {/***/if(s.length()!t.length()){return false;}int[] cnt new int[26];for(char c: s.toCharArray()){cnt[c-a];}for(char c: t.toCharArray()){cnt[c-a]--;if(cnt[c-a]0){return false;}}return true;}
}6 49. 字母异位词分组
49. 字母异位词分组
中等
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]示例 2:
输入: strs []
输出: [[]]示例 3:
输入: strs [a]
输出: [[a]]提示
1 strs.length 1040 strs[i].length 100strs[i] 仅包含小写字母
6.1 思路 重点是用Arrays.sort排序排序后的字符串作为key 遍历strs对strs中的每个str先使用Arrays.sort排序维持一个String,ListString 的Map排序后的字符串作为Key排序前的作为Value最后遍历Map取出Map中的所有Value放到List结果中6.2 代码
class Solution {public ListListString groupAnagrams(String[] strs) {/***/MapString,ListString map new HashMap();for(String str:strs){char[] str_c str.toCharArray();Arrays.sort(str_c);String key new String(str_c);ListString list map.getOrDefault(key,new ArrayListString());list.add(str);map.put(key,list);}ListListString res new ArrayList();for(Map.EntryString,ListString entry: map.entrySet()){res.add(entry.getValue());}return res;}
}7 1.两数之和
1. 两数之和
简单
给定一个整数数组 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]提示
2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案
**进阶**你可以想出一个时间复杂度小于 O(n2) 的算法吗
7.1 思路 经典题目但是第一遍只想得起来暴力 暴力枚举遍历用Map记录数字和他的下标。之后遍历的时候就能通过hashmap知道target-x是否出现过了。 枚举遍历要加速的话可以用空间换时间用一个Map记录每个数字和他的下标。之后给原数组排序。然后双指针遍历。上面是一个思路。实际上是记录了之后在遍历的时候能够借助hashmap知道target-x是否出现过。因此时间复杂度能从On^2降到O1// int n nums.length;// for(int i 0;in;i){// for(int j i1;jn;j){// if(nums[i]nums[j]target){// return new int[]{i,j};// }// }// }// return new int[]{};7.2 代码
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger,Integer map new HashMap();for(int i 0;inums.length;i){if(map.containsKey(target-nums[i])){return new int[]{i,map.get(target-nums[i])};}map.put(nums[i],i);}return new int[]{};}
}8 202.快乐数 需要复习
202. 快乐数
简单
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
示例 1
输入n 19
输出true
解释
12 92 82
82 22 68
62 82 100
12 02 02 1示例 2
输入n 2
输出false提示
1 n 231 - 1
8.1 思路 可以用哈希表做用哈希表记录出现的数字当出现重复的时候就可以返回了。 如果重复的数字为1说明是快乐数否则不为快乐数。 巧妙的是快慢指针判断有环的解法。具体参考下面 快慢指针快指针每次走2步慢指针每次走1步二者相等时即为1个循环周期若有环则一定能相遇若无环也会相遇但相遇点为1想起来了那道判断链表进环点的题。也是快慢指针。相遇后让一个新的指针从起点开始以和慢指针一样的速度行动相遇的节点即为入环点。但是本题只用判断循环点是否为1即可。8.2 代码
class Solution {public boolean isHappy(int n) {/***/int slow n,fast n;do{slow bigSquareSum(slow);fast bigSquareSum(fast);fast bigSquareSum(fast);}while(slow ! fast);if(slow1){return true;}return false;}int bigSquareSum(int n){int sum 0;while(n!0){sum (n%10)*(n%10);nn/10;}return sum;}
}9 219.存在重复元素II
219. 存在重复元素 II
已解答
简单
给你一个整数数组 nums 和一个整数 k 判断数组中是否存在两个 不同的索引 i 和 j 满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在返回 true 否则返回 false 。
示例 1
输入nums [1,2,3,1], k 3
输出true示例 2
输入nums [1,0,1,1], k 1
输出true示例 3
输入nums [1,2,3,1,2,3], k 2
输出false提示
1 nums.length 105-109 nums[i] 1090 k 105
9.1 思路 hashmap的应用 维护一个HashMap,map中是nums中的值-下标的映射遍历nums假如在遍历时发现map中存储过该值则根据map取出上次出现的下标计算是否满足i-jk,若不满足则将当前下标更新为j9.2 代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {/***/MapInteger,Integer map new HashMap();for(int i0;inums.length;i){int num nums[i];if(map.containsKey(num)){if(i-map.get(num)k){return true;}}map.put(num,i);}return false;}
}10 128.最长连续序列
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9提示
0 nums.length 105-109 nums[i] 109
10.1 思路 具体如下。重点是 需要找到可能的连续序列 开始的数字之后往后遍历计算最长连续序列即可。 利用hash表来存储nums的值帮助枚举连续的数1.先遍历nums将nums中的值都存在hashset中2.遍历hashset找到每个可能的连续序列开始的数然后从该数开始往后遍历计算最长连续序列10.2 代码
class Solution {public int longestConsecutive(int[] nums) {/***/SetInteger set new HashSet();for(Integer num: nums){set.add(num);}int res 0;for(Integer num: set){//2.1 判断是不是连续序列最开始的数if(set.contains(num-1)){continue;}//2.2 说明是连续序列最开始的数int curres 0;while(set.contains(num)){curres;}res Math.max(res,curres);}return res;}
}
