【LeetCode】 哈希表的使用

坚持啊！给自己自由！

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

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

242. 有效的字母异位词

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

classSolution{publicbooleanisAnagram(String s,String t){int[]num1 =newint[128];int[]num2 =newint[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])returnfalse;}returntrue;}

383. 赎金信

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

classSolution{publicbooleancanConstruct(String ransomNote,String magazine){int num[]=newint[128];for(char  i : ransomNote.toCharArray()){
            num[i]++;}for(char i : magazine.toCharArray()){
            num[i]--;}for(int i : num ){if(i >0)returnfalse;}returntrue;}}

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 =newHashMap<>();
    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对应的valueint score = map.getOrDefault("score",80);System.out.println(score);// 80，map中不存在score,使用默认值80

了解了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.

classSolution{publicList<List<String>>groupAnagrams(String[] strs){Map<String,List<String>>   map =newHashMap<String,List<String>>();for(String str: strs){char[] c = str.toCharArray();Arrays.sort(c);String key =newString(c);//构造单词的字符排序,作为键List<String>List= map.getOrDefault(key,newArrayList<String>());List.add(str);
            map.put(key,List);//将单词加入散列表中}returnnewArrayList<List<String>>(map.values());}}

第二种方法：

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

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

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

呜呜呜，超时了！

快慢指针法：

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

classSolution{publicList<Integer>findAnagrams(String s,String p){int num1[]=newint[128];List<Integer> list =newArrayList<>();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;}}