【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;    }

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;    }}

49. 字母异位词分组

方法一：字母排序

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

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

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

再着是运用字符串的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对应的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(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());    }}

第二种方法：

改变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());    }}

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;    }}