算法笔记|Day5哈希表基础
- ☆☆☆☆☆leetcode 242.有效的字母异位词
- ☆leetcode 49.字母异位词分组（待补充）
- ☆leetcode 438.找到字符串中所有字母异位词（待补充）
- ☆☆☆☆☆leetcode 349. 两个数组的交集
- ☆leetcode 350.两个数组的交集II（待补充）
- ☆☆☆☆☆leetcode 202. 快乐数
- ☆☆☆☆☆leetcode 1. 两数之和
☆☆☆☆☆leetcode 242.有效的字母异位词
题目分析
1.数组就是一个简单哈希表，定义一个数组record记录字符串s里字符出现的次数，并分别减去各个字符在字符串t中出现的次数，若record各个元素均为0返回true，否则返回false；
2.时间复杂度O(m+n) ，空间复杂度O(1)。
代码
class Solution {
public boolean isAnagram(String s, String t) {
int record[]=new int[26];
for(int i=0;i<s.length();i++){
record[s.charAt(i)-'a']++;
}
for(int j=0;j<t.length();j++){
record[t.charAt(j)-'a']--;
}
for(int n=0;n<26;n++){
if(record[n]!=0){
return false;
}
}
return true;
}
}
提示
1.获取string字符串的长度：string.length();
2.获取string字符串指定索引位置的字符：string.charAt(int index);
☆leetcode 49.字母异位词分组（待补充）
题目链接：leetcode 49.字母异位词分组
题目分析
代码
☆leetcode 438.找到字符串中所有字母异位词（待补充）
题目链接：leetcode 438.找到字符串中所有字母异位词
题目分析
代码
☆☆☆☆☆leetcode 349. 两个数组的交集
题目分析
1.采用哈希数组，分别记录两个数组出现的元素，若有重复，将重复元素放到列表resList中，最后遍历列表resList得到所需数组；
2.采用哈希set，先记录第一个数组出现的元素，遍历第二个数组是否存在该元素，若存在放到列表resList中，最后遍历列表resList得到所需数组；
3.时间复杂度O(m+n) ，空间复杂度O(1)。
代码
1.采用哈希数组
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int hash1[]=new int[1001];
int hash2[]=new int[1001];
for(int i:nums1){
hash1[i]=1;
}
for(int i:nums2){
hash2[i]=1;
}
List<Integer> resList = new ArrayList<>();
for(int i=0;i<1001;i++){
if(hash1[i]==1&&hash2[i]==1){
resList.add(i);
}
}
int index=0;
int[] res = new int[resList.size()];
for (int i:resList) {
res[index++]=i;
}
return res;
}
}
2.采用哈希set
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1=new HashSet<>();
Set<Integer> resSet=new HashSet<>();
for(int i:nums1){
set1.add(i);
}
for(int i:nums2){
if(set1.contains(i)){
resSet.add(i);
}
}
int index=0;
int res[]=new int[resSet.size()];
for(int i:resSet){
res[index++]=i;
}
return res;
}
}
提示：
1.在Java中，for(元素变量x:遍历对象obj) 是一种增强的for循环（也称为"for-each"循环），它用于遍历数组或集合（如List、Set等）中的元素，而无需使用传统的索引，这种循环方式使得代码更加简洁易读；
2.List resList = new ArrayList<>(); 这行代码创建了一个可以存储Integer类型元素的ArrayList实例，并将这个实例的引用赋值给了List类型的变量resList。这允许你通过resList变量来执行添加、删除、获取等列表操作;
3.resSet.add(i);通过实例调用add方法，将i添加到列表中；
4.Set resSet=new HashSet<>();创建了一个可以存储不重复整数的集合 resSet【在Java中，Set 是一个接口，它代表了一个不允许有重复元素的集合。Set 接口提供了一系列用于操作集合的方法，比如添加、删除、检查元素是否存在等。不过，Set 接口本身并不提供实现；相反，它必须由具体的类来实现，比如 HashSet、LinkedHashSet 和 TreeSet 等。HashSet 是 Set 接口的一个常用实现，它基于哈希表（HashMap）实现。HashSet 允许存储 null 元素，并且不保证集合的迭代顺序；也就是说，当你遍历 HashSet 时，元素的顺序可能与它们被添加到集合中的顺序不同】；
5.set1.contains(i)用于检查集合set1是否包含指定的元素i；
☆leetcode 350.两个数组的交集II（待补充）
题目分析
代码
☆☆☆☆☆leetcode 202. 快乐数
题目链接：leetcode 202. 快乐数
题目分析
1.采用哈希map，此题中会出现循环，只需将每一次计算后的结果存在集合record中，若结果中有1则不是快乐数，一直处于循环结果没有1则是快乐数；
2.计算每个数各个位数的平方和是一个数学问题，从个位平开始取平方相加，直至首位；
3.时间复杂度为O(logn)，空间复杂度为O(logn)。
代码
class Solution {
public boolean isHappy(int n) {
Set<Integer> record=new HashSet<>();
while(n!=1&&!record.contains(n)){
record.add(n);
n=getNextNumber(n);
}
return n==1;
}
private int getNextNumber(int n){
int res=0;
while(n>0){
int temp=n%10;
res+=temp*temp;
n/=10;
}
return res;
}
}
☆☆☆☆☆leetcode 1. 两数之和
题目链接：leetcode 1. 两数之和
题目分析
1.采用哈希map，遍历每个元素nums[i]时，要考虑target-nums[i]是否出现过，故需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适；
2.时间复杂度为O(n)，空间复杂度为O(n)。
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int res[]=new int[2];
Map<Integer,Integer>map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int temp=target-nums[i];
if(map.containsKey(temp)){
res[0]=map.get(temp);
res[1]=i;
break;
}
map.put(nums[i],i);
}
return res;
}
}
提示：
1.Map<Integer,Integer> map = new HashMap<>(); 这行代码在Java中创建了一个名为map的HashMap实例，这个HashMap用于存储键值对（key-value pairs），其中键（key）和值（value）都是Integer类型的【HashMap的特点：不保证映射的顺序。允许一个null键和多个null值，基于哈希表的Map接口实现】；
2.map.containsKey(temp)是一个用于检查实现了Map接口的集合中是否包含指定键（key）的方法调用；
3.map.get(temp)是一个用于从实现了Map接口的集合中获取与指定键（key）相关联的值（value）的方法调用；
4.map.put(nums[i], i)是一个调用实现了Map接口的集合将指定的键（key）与值（value）关联（或更新）到映射中。