【LeetCode】 哈希表的使用

坚持啊！给自己自由！

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242. 有效的字母异位词

因为string 只包含小写字母 ，所以可以创建数组来存储各个字母,再循环判断

class Solution {
    public boolean isAnagram(String s, String t) {
        int []num1 = new int[128];
        int []num2 = new int[128];
        for(int i  = 0; i <s.length(); i++){
            char c= s.charAt(i);
            num1[c]++;
        }
        for( int i = 0; i< t.length(); i++){
            char c = t.charAt(i);
            num2[c]++;
        }

        for(int i = 0; i<128;i++){
            if(num1[i] != num2[i])
            return false;
        }
        return true;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

383. 赎金信

改进版，只用一个数组，通过对这一个数组加减判断
小写字母是128以内的数字，主要magazine里字母存在，就让相应的下标的值加一，
在到ransomNote匹配，只要是ransomNote里的字母，就让相应下标的值减一，只要存在
哪个下标的值大于0，说明magazine里存在ransomNote没有的字母，那就return false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int num[] = new int[128];
        for(char  i : ransomNote.toCharArray()){
            num[i]++;
        }
        for(char i : magazine.toCharArray()){
            num[i]--;
        }
        for(int i : num ){
            if(i > 0)
            return false;
        }
        return true;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

49. 字母异位词分组

方法一：字母排序

理解字母异位词，具有相同的字母特征，所以可以利用散列表map来存储，键为一组异位字母词的标志， 值为一组字母异位词列表

1.首先，遍历每一个的string，得到每一个字符串所在组的字母异位词的标志

2将当前字符串加入该组字母异位词的列表中，遍历全部字符串之后，哈希表中的每一键值对即为一组字母异位词
这道题运用了好多集合的API，首先是定义上的套娃，map<String,List>

再着是运用字符串的toCharArray();,toCharArray() 方法将字符串转换为字符数组。

再使用Arrays.sort(),排序 是Arrays 不是Array，（这里我踩了坑，呜呜呜）

接着是，再将排序好的字符数组 创建成 字符串

下一步是，运用map.getOrDefault 获取 map的值 也就是List

说明一下map.getOrDefault方法:

Java中map.getOrDefault()方法的使用

Map.getOrDefault(Object key, V defaultValue)方法的作用是：

当Map集合中有这个key时，就使用这个key值；

如果没有就使用默认值defaultValue。

HashMap<String, String> map = new HashMap<>();
	map.put("name", "cookie");
	map.put("age", "18");
	map.put("sex", "女");
	String name = map.getOrDefault("name", "random");
	System.out.println(name);// cookie，map中存在name,获得name对应的value
	int score = map.getOrDefault("score", 80);
	System.out.println(score);// 80，map中不存在score,使用默认值80
1
2
3
4
5
6
7
8

了解了map.getOrDefault()后，我们就知道我们得到了 一个List ，这个List有两种情况，一种是map 里已经有key存在，那么直接获取key所对应的value值，不然就直接返回 新的ArrayList ，泛型为String。

接着，把一开始没有排序过的字符串加入List里，运用了List,add()的api

再把List放进map里，用的是map.put()的API；

最后一步是，退出循环后，返回ArrayList<List>(map.values());，这句话的意思是 创建ArrayList数组，类型是List，他的值为map.values值，map.values()取出来的值就是value，没有key.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
 Map<String ,List<String>>   map =new HashMap<String,List<String>>();
        for(String str: strs){
            char[] c = str.toCharArray();
            Arrays.sort(c);
            String key = new String(c);//构造单词的字符排序,作为键
            List<String>  List = map.getOrDefault(key,new ArrayList<String>());
            List.add(str);
            map.put(key,List);//将单词加入散列表中
        }
        return new ArrayList<List<String>>(map.values());

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二种方法：

改变map的key值，由字母和字母出现的次数组成

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        for(String str :strs){
            int []num = new int[26];
            for(int i = 0; i< str.length();i++){//统计字符出现次数
                num[str.charAt(i)-'a']++;
            }
            StringBuffer stringBuffer = new StringBuffer();
            for(int i = 0; i <26;i++){
                if(num[i] > 0){
                    stringBuffer.append((char)('a' +i));
                    stringBuffer.append(num[i]);//创建键值
                }
            }
            String s = new String(stringBuffer);
            List<String> list = map.getOrDefault(s,new ArrayList<String>());
            list.add(str);//将具有相同特征的字母放在一起
            map.put(s,list);       
        }
        return new ArrayList<List<String>>(map.values());

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

438. 找到字符串中所有字母异位词

呜呜呜，超时了！

快慢指针法：

如果遇到没有的字符，high原地等待；low++遍历到这个字符后（即low比high多1后），下一次high也会消耗掉这个没有的字符

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
            int num1[] = new int[128];
            List<Integer> list = new ArrayList<>();
            for(char i: p.toCharArray()) num1[i]++;
             int low = 0 ,high = 0;
             while(high <s.length()){
                 if(num1[s.charAt(high)] >0){
                     num1[s.charAt(high++)]--;
                     if(high -low == p.length())  list.add(low);
                 }else{
                     num1[s.charAt(low++)]++;
                 }
             }
             return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17