《五月集训》（第7天）——哈希表

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

哈希表的简单定义：将值映射到数组中某个位置（关键字），方便以后查找数据。
关键字可以用哈希函数来寻找，但一般的我们使用是只需要用指本身作为关键字即可。

二、课堂习题

这里的题均出自《算法零基础100讲》
暑假再细致更新，着急想要进一步学习的同学，可以去这个专栏看一看。

三、作业

1512. 好数对的数目
2006. 差的绝对值为 K 的数对数目
1347. 制造字母异位词的最小步骤数
面试题 10.02. 变位词组
解题思路：
1.用朴素的计数器cnt方法即可，双循环，定义两个指针，从左到右依次寻找满足条件的数对cnt++;
2.哈希表的思想，将数组元素存进去，并判断每个元素在+[k,-k]这个区间内是否有可以匹配的数，有就将答案加上个数；
3.将两个字符串出现的数字分别存进两个表里，只需要统计第二个表比第一个表少出现的字母个数即可；
4.将每个字符串按照字典序排序后得到的字符串当作关键词，然后将字符串存入每个关键词的位置，最后把相同关键词的字符串数组放进列表中返回即可。

代码以及结果：

class Solution {    public int numIdenticalPairs(int[] nums) { int cnt = 0; for(int i = 0;i < nums.length;++i){     for(int j = i + 1;j < nums.length;++j){  if(nums[j] == nums[i]){      cnt++;  }     } } return cnt;    }}

class Solution {    public int countKDifference(int[] nums, int k) { int[] hash = new int[101]; int cnt = 0; for(int num : nums){     int x = num + k;     if(x >= 1 && x <= 100){  cnt += hash[x];     }     x = num - k;     if(x >= 1 && x <= 100){  cnt += hash[x];     }     hash[x+k]++; } return cnt;    }}

class Solution {    public int minSteps(String s, String t) { int cnt = 0; int[] hash1 = new int[26]; int[] hash2 = new int[26]; for(int i = 0;i < s.length();++i){     hash1[s.charAt(i)-'a']++;     hash2[t.charAt(i)-'a']++; } for(int i = 0;i < 26;++i){     if(hash1[i] > hash2[i]){  cnt += hash1[i]-hash2[i];     } } return cnt;    }}

class Solution {    public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> ans = new ArrayList<>(); Map<String,List<String>> map = new HashMap<>(); for(int i = 0;i < strs.length;++i){     char[] words = strs[i].toCharArray();     Arrays.sort(words);     String s = new String(words);     if(!map.containsKey(s)){  List<String> temp = new ArrayList<>();  temp.add(strs[i]);  map.put(s,temp);     }else{  map.get(s).add(strs[i]);     } } for(String key : map.keySet()){     ans.add(map.get(key)); } return ans;    }}

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
课堂训练内容要等到放假辣(●ˇ∀ˇ●)