代码随想录算法训练营DAY6

代码随想录算法训练营DAY6 | 哈希表(1)

DAY5休息一天，今天重启~

哈希表理论基础：代码随想录

Java hash实现：java 哈希表-CSDN博客

一、LeetCode 242 有效的字母异位词

题目链接：242.有效的字母异位词

思路：设置字典

class Solution {public boolean isAnagram(String s, String t) {int slen = s.length(), tlen = t.length();if(slen != tlen){return false;}int[] alp = new int[26];            //设置字典存储字母信息for(int i = 0; i < slen; i++){alp[s.charAt(i) - 'a']++;alp[t.charAt(i) - 'a']--;}for(int i = 0; i < 26; i++){if(alp[i] != 0){return false;}}return true;}
}

二、LeetCode 349 两个数组的交集

思路：利用哈希表的无序性、唯一性求交集。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {//哈希set无序唯一Set<Integer> set1 = new HashSet<>();Set<Integer> set2 = new HashSet<>();for(int a:nums1){set1.add(a);}for(int a:nums2){if(set1.contains(a)){set2.add(a);}}int n =  set2.size();int[] ans = new int[n];int index = 0;//加强循环遍历for(int num : set2){ans[index++] = num;}return ans;}
}

补充：HashSet遍历的三种方式

①迭代器遍历

②转换为List遍历

③增强for循环遍历

//迭代器遍历
Iterator iterator = set.iterator();
while (iterator.hasNext()) {System.out.println(iterator.next());			
}
//转换为List遍历
List<Integer> list = new ArrayList<>(set);
for(int i : list){System.out.println(i);
}
//增强for循环遍历
for(int i : set){System.out.println(i);
}

三、LeetCode 202 快乐数

题目链接：202.快乐数https://leetcode.cn/problems/happy-number/submissions/499209933/

思路：设置哈希表记录出现过的数，出现循环即终止。

class Solution {public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();while(n != 1){int sum = 0, temp = n;while(temp != 0){int x = temp%10;temp /= 10;sum += x*x;}if(set.contains(sum)){return false;}set.add(sum);n = sum;}return true;}
}

四、LeetCode 1 两数之和

题目链接：1.两数之和https://leetcode.cn/problems/two-sum/description/

思路：以数值为Key、下标为Value，建立映射关系并使用HashMap存储；使用HashMap的containsKey（）方法和get（）方法获取符合条件的数值下标。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();    //数值为Key、下标为Valueint[] ans = new int[2];for(int i = 0; i < nums.length; i++){if(map.containsKey(target - nums[i])){ans[0] = map.get(target - nums[i]);ans[1] = i;return ans;}map.put(nums[i],i);}return ans;}
}

补充：HashMap常用方法

//添加键值对
put(Object key, Object value) //添加指定的映射关系到目标映射关系
putAll(Collection c)//根据键来获取对应的值
get(Object key) //map中存在key则使用对应的value，否则使用defaultValue
getOrDefault(Object key, V defaultValue)//是否有指定key的映射 
containsKey(Object key)//是否有指定value的映射
containsValue(Object value)//删除该键值对
remove(Object key) //返回所有值，返回形式为Collection
values() //测试映射是否为空
isEmpty()//返回大小
size()