哈希表刷题
Leetcode 哈希表刷题
Leetcode 01 两数之和
思路：
1，循环遍历数组，拿到每个数字 X
2，以 target - x 作为 key 到 hash 表查找
1）若没找到，将 x 作为 key, 它的索引作为 value 放入 hash 表
2）若是找到，返回 x 和它配对数的索引即可
1 | public int[] twoSum(int[] nums,int target){ |
Leetcode 03 无重复字符的最长字串
思路：
1. 用 begin 和 end 表示子串开始和结束位置 2. 用 hash 表检查重复字符 3. 从左向右查找每个字符，如果： - 没遇到重复字符，调整 end - 遇到重复字符，调整 begin - 将当前字符放入 hash 表 1. End - begin + 1 是当前子串长度
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int begin = 0;
int maxLength = 0;
HashMap<Character,Integer>map = new HashMap<>();
for(int end = 0;end < s.length();end++){
char ch = s.charAt(end);
if(map.containsKey(ch)){//重复
begin = map.get(ch) + 1;
map.put(ch,end);
}else{
map.put(ch,end);
}
System.out.println(s.substring(begin,end+1));
maxLength = Math.max(maxLength,end - begin + 1);
}
return 0;
}
public static void main(String[] args) {
/*
给定一个字符串s,请你找出其中不含有重复字符的最长字串的长度。
abcabcbb 3
a
ab
abc
bca
cab
abc
cb
b
bbbbb 1
pwwkew
p
pw
w
wk
wke
演示：
[(a,3),(b,1),(c,2)]
b
e
abcabcbb
*/
}
但是这个代码还存在问题 ： 如果遇到 abba 是无法通过的用上面的代码发现是 31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28【(a,0),(b,2)】
b(0+1)反而往回走的
e
abba
所以我们应该拿到map+1的索引后跟当前做一个比较 取一个较大的值
public int lengthOfLongestSubstring(String s){
int begin = 0;
int maxLength = 0;
HashMap<Character,Integer>map = new HashMap<>();
for(int end = 0;end < s.length();end++){
char ch = s.charAt(end);
if(map.containsKey(ch)){//重复
--- 修改这里
begin = Math.max(begin,map.get(ch) + 1);
-----------------
map.put(ch,end);
}else{
map.put(ch,end);
}
System.out.println(s.substring(begin,end+1));
maxLength = Math.max(maxLength,end - begin + 1);
}
return 0;
}
题目说s是由英文字母，数字，符号和空格组成的 只有128个 所以我们可以进一步优化 可以不用hashmap
已知大小可以使用数组，性能会更胜一筹
作为提高
Leetcode 49 字母异位词分组
思路：
1. 遍历字符串数组，每个字符串中的字符重新排序后作为 key 2. 所谓分组，其实就是准备一个集合，把这些单词加入到 key 相同的集合中 3. 返回分组结果
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// eat eta tae tea ate aet => aet
// tan nat => ant
// bat => bat
//[(aet,{eat,tea}),(ant,{tan})...]
public List<List<String>>groupAnagrams(String[] strs){//6ms
HashMap<String,List<String>> map = new HashMap<>();
for(String str:strs){
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
// List<String>list = map.get(key);
//if(list==null){
// list = new ArrayList<>();
// map.put(key,list);
//}
List<String>list = map.computeIfAbsent(key,k->new ArrayList<>());
list.add(str);
}
return new ArrayList<>(map.values());
}解法二：
题目中说明： strs [i] 仅包含小写字母
Key = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
1 |
|
Leetcode 217 判断数组中有没有重复元素
1 | public boolean containsDuplicate(int[] nums){//11ms |
1 | // HashSet底层也是调用HashMap来判断有没有重复 |
那其实我们也可以模拟一下 add 方法的实现1
2
3
4
5
6
7
8
9
10
11public boolean containsDuplicate(int[] nums){//优化 6ms左右
HashMap<Integer,Object>map = new HashMap<>(nums.length*2);//保证大小 避免扩容
Object value = new Object();//因为值不重要我们使用一个即可不用使用多个Integer对象
for(int key:nums){
Integer put = map.put(key,value);
if(pull!=null){
return true;
}
}
return false;
}
Leetcode 136 找出出现一次的数字
除了某个元素出现一次意外，其余每个元素均出现两次1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/*
输出：nums=[2,2,1]
[1]
nums=[4,1,2,1,2]
*/
public int singleNumber(int[] nums){
HashSet<Integer>set = new HashSet<>();
for(int num:nums){
if(!set.add(num)){
set.remove(num);
}
}
return set.toArray(new Integer[0])[0];
}
使用异或相同为 0 不同为 1
123 ^ 321
0111_1011
^
0100_0001
0011_1010
—》 314
==思路 2:
- 任何相同的数字异或，结果都是 0
- 任何数字和 0 异或，都是数字本身==
1 | public int singleNumber(int[] nums){ |
Leetcode 242 判断两个单词是否为字母异位词
1 | /* |
优化：1
2
3
4
5
6
7
8
9
10
11
12public boolean isAnagram(String s,String t){//3ms
return Arrays.equals(getKey(s) getKey(t));
}
private int[] getKey(String s){//1ms 优化这里
int[] array = new int[26];
char[] chars = s.toCharArray();
for(char ch:chars){
array[ch-97]++;
}
return array;
}
Leetcode 387 字符串中的第一个不重复的字符
1 | /* |
Leetcode 819 出现次数最多的单词
==有实际意义的题目==
思路
1. 将 paragraph 截取为一个个单词 2. 将单词加入 map 集合，单词本身作为 key，出现次数作为 value, 避免禁用词加入 3. 在 map 集合中找到 value 最大的，返回它对应的 key 即可
1 | public String mostCommonWord(String paragraph,String[] banned){//禁用词 14ms |
优化：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29public String mostCommonWord(String paragraph,String[] banned){//禁用词 12ms
String[] split = paragraph.toLowerCase().split("[^A-Za-z]+");
//如果把禁用词放在循环中则是O（n） 怎么样降成O(1)
//Java9 Set.of方法可以把我们的数组转为Set集合
Set<String>set = Set.of(banned);
HashMap<String,Integer>map = new HashMap<>();
for(String key:split){
if(!set.contains(key)){
System.out.println(key);
/* Integer value = map.get(key);
if(value==null){
value=0;
}
map.put(key,value+1); */
map.compute(key,(k,v)->v==null?1:v+1);
}
}
int max = 0;
String maxKey = null;
for(Map.Entry<String,Integer>e:map.entrySet()){
Integer value = e.getValue();
if(value > max){
max = value;
maxKey = e.getKey();
}
}
return maxKey;
}
优化 2：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35public String mostCommonWord(String paragraph,String[] banned){//禁用词
//自己截取StringBuilder 遇到a-z 就拼接 这样比正则的效率高很多
Set<String>set = Set.of(banned);
HashMap<String,Integer>map = new HashMap<>();
char[] chars = paragraph.toLowerCase().toCharArray();
StringBuilder sb = new StringBuilder();
for(char ch:chars){
if(ch>='a' && ch<='z'){
sb.append(ch);
}else{
String key = sb.toString();
if(!set.contains(key)){
map.compute(key,(k,v)->v==null?1:v+1);
}
//sb = new StringBuilder();//这里还能优化
sb.setLength(0);//4ms 学无止境
}
}
if(sb.length()>0){
String key = sb.toString();
if(!set.contains(key)){
map.compute(key,(k,v)->v==null?1:v+1);
}
}
int max = 0;
String maxKey = null;
for(Map.Entry<String,Integer>e:map.entrySet()){
Integer value = e.getValue();
if(value > max){
max = value;
maxKey = e.getKey();
}
}
return maxKey;
}//5ms
