Leetcode 哈希表刷题

Leetcode 01 两数之和

思路：

1，循环遍历数组，拿到每个数字 X
2，以 target - x 作为 key 到 hash 表查找
1）若没找到，将 x 作为 key, 它的索引作为 value 放入 hash 表
2）若是找到，返回 x 和它配对数的索引即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums,int target){
	Map<Integer,Integer>map = new HashMap<>();
	for(int i=0;i<nums.length;i++){
		int x = nums[i];
		int y = target-x;
		if(map.containsKey(y)){
			return new int[]{i，map.get(y)};
		}
		else{
			map.input(x,i)
		} 
		return nulll
	}

}

Leetcode 03 无重复字符的最长字串

思路：

  1. 用 begin 和 end 表示子串开始和结束位置
  2. 用 hash 表检查重复字符
  3. 从左向右查找每个字符，如果：
    • 没遇到重复字符，调整 end
    • 遇到重复字符，调整 begin
    • 将当前字符放入 hash 表
  4. End - begin + 1 是当前子串长度
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
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 = 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 是无法通过的用上面的代码发现是 3

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
【(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. 返回分组结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ab ba 组成相同但是顺序不同
// 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
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

static class ArrayKey {// 5ms
	int[] key = new int[26];
	
	//生成hashcode 和equals方法
	public boolean equals(Object o){
		if(this == o) return true;
		if(o==null||getClass()!=o.getClass()) return false;
		
		ArrayKey arrayKey = (ArrayKey) o;
		
		return Arrays.equals(key,arrayKey.key);
	}
	
	pubic int hashCode(){
		return Arrays.hashCode(key);
	}
	
	public ArrayKey(String str){
		for(int i = 0;i<str.length();i++){
			char ch = str.charAt(i);//'a' 97-97=0
			key[ch-97]++; 
		}
	}
}
public List<List<String>>groupAnagrams(String[] strs){//
	HashMap<ArrayKey,List<String>>map = new HashMap<>();
	for(String str:strs){
		ArrayKey key = new ArrayKey(str);
		List<String> list = map.computeIfAbsent(key,k->new ArrayList<>());
		list.add(str);
	}
	return new ArrayList<>(map.values());
}

Leetcode 217 判断数组中有没有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean containsDuplicate(int[] nums){//11ms
	HashMap<Integer,Integer>map = new HashMap<>();
	for(int key:nums){
		for(int key: nums){
			if(map.containsKey(key)){
				//找到重复
				return true;	
			}
			map.put(key,key);
		}
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
// HashSet底层也是调用HashMap来判断有没有重复
//为什么性能上会相差一倍？ 区别是方法的调用次数 
// add 返回值是boolean O（n）上面的方法比下面的多义词containsKey
public boolean containsDuplicate(int[] nums){//5ms
	HashSet<Integer,Integer>map = new HashSet<>();
	for(int key:nums){
		if(!set.add(key)){
			return true;
		}
	}
	return false;
}

那其实我们也可以模拟一下 add 方法的实现

1
2
3
4
5
6
7
8
9
10
11
public 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:

  1. 任何相同的数字异或，结果都是 0
  2. 任何数字和 0 异或，都是数字本身==
1
2
3
4
5
6
7
public int singleNumber(int[] nums){
	int num = nums[0];
	for(int i=1;i<nums.length;i++){
		num = num ^ nums[i];
	}
	return num;
}

Leetcode 242 判断两个单词是否为字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
	输入：s = "anagram", t = "nagaram"
	输出true
	
	1.拿到字符数组，排序后比较字符数组
	2.字符打散放入 int[26],比较数组
*/

public boolean isAnagram(String s,String t){//3ms
	return Arrays.equals(getKey(s) getKey(t));
}

private int[] getKey(String s){
	int[] array = new int[26];
	for(int i = 0;i<s.length();i++){
		char ch = s.charAt(i);//'a' - 97 = 0
		array[ch-97]++;
	}
	return array;
}

优化：

1
2
3
4
5
6
7
8
9
10
11
12
public 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
	输入：s="leecode"
	l t c o d e
	输出 0 
*/

public int firstUniqueChar(String s){
	int[] array = new int[26];
	char[] chars = s.toCharArray();
	for(char ch : chars){
		array[ch-97]++;
	}
	for(int i = 0;i<chars.length;i++){
		char ch = chars[i];
		if(array[ch-97]==1){
			return i;
		}
	}
	return -1;
}



Leetcode 819 出现次数最多的单词

==有实际意义的题目==

思路

  1. 将 paragraph 截取为一个个单词
  2. 将单词加入 map 集合，单词本身作为 key，出现次数作为 value, 避免禁用词加入
  3. 在 map 集合中找到 value 最大的，返回它对应的 key 即可
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
public String mostCommonWord(String paragraph,String[] banned){//禁用词 14ms
	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);
		}
		
	}
	Optional<Map.Entry<String,Integer>>optional = map.entrySet().stream().max(Map.Entry.comparingByValue());
	return optional.map(Entry::getKey).orElse()null;
}

public static void main(String[] args){

}

优化：

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
public 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
35
public 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