[数据结构与算法]代码随想录算法训练营第六天 | 242.有效的字母异位词，349. 两个数组的交集，202. 快乐数 ， 1. 两数之和 9.26

代码随想录算法训练营第六天 | 242.有效的字母异位词，349. 两个数组的交集，202. 快乐数 ， 1. 两数之和 9.26

哈希表原理

1. 哈希表用来快速判断一个元素是否出现在集合里
2. 需要判断一个元素是否出现过的场景也应该第一时间想到哈希法
3. 常见3种哈希结构 set map 数组

242.有效的字母异位词

1. 由于s,t字符串中存放的都是小写字母 因此可以用数组存放每个小写字母相对于’a’的相对位置 有26个
2. 统计是每个小写字母出现的次数 先用s存 然后再用t减掉
3. 最后遍历数组 看看是否全为0

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] res = new int[26];
        for(int i = 0;i<s.length(); i++){
            res[s.charAt(i)-'a']++;
        }

        for(int i = 0; i<t.length(); i++){
            res[t.charAt(i)-'a']--;
        }

        for(int i = 0; i<26; i++){
            if(res[i]!=0){
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集

1. 此题与上题寻找两个字符串中相同的字符相似 同样可以用数组来作为哈希表只不过长度很长为1000
2. 此外由于Int[]类型不能添加元素 所以先用ArrayList集合存结果 然后再用一次循环将结果转成Int[]返回

数组写法

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] rec = new int[1000];
        for(int i = 0; i<nums1.length; i++){
            rec[nums1[i]]++;
        }

        ArrayList res = new ArrayList();
        for(int i =0; i<nums2.length;i++){
            if(rec[nums2[i]]!=0){
                res.add(nums2[i]);
                rec[nums2[i]]=0;
            }
        }

        int[] ans = new int[res.size()];
        for(int i = 0; i<res.size(); i++){
            ans[i]=(int)res.get(i);
        }
        return ans;


    }
}

set解法

1. 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费
2. HashSet数据结构中存的是无重复 无索引 无序的元素

import java.util.Collection;
import java.util.HashSet;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Collection<Integer> set = new HashSet<>();
        Collection<Integer> resSet = new HashSet<>();

        //第一遍循环将Nums1 的元素存入哈希表
        for(int i: nums1){  //遍历集合中的元素 i为元素
            set.add(i);
        }

        //第二遍循环判断是否有交集 若有则加入结果集
        //由于set的特点是存储无重复的数据 所有无需去重操作
        for(int i : nums2){
            if(set.contains(i)){
                resSet.add(i);
            }
        }

        //把hashset数据结构转换成Int[]类型返回
        return resSet.stream().mapToInt(x -> x).toArray();


    }
}

202. 快乐数

1. 只要出现和之前计算过一样的数 就说明该数不是快乐数 因此想到用set哈希表存储每次运算结果
2. 此题另一个难点是 如何获得n 的每一位数字 方法是n%10 然后 再将n/10 这样就到下一位

import java.util.Collection;
import java.util.HashSet;

class Solution {
    public boolean isHappy(int n) {

        Integer happy1 = n;
        Collection<Integer> list = new HashSet<>();
        while(happy1!=1){
            happy1 = happy(happy1);
            if(list.contains(happy1)){
                return false;
            }
            list.add(happy1);


        }
        return true;

    }


    public static int happy(Integer n){
        Integer temp = 0;
        Integer res = 0;
        while(n>0){
            temp = n%10;
            res+=temp*temp;
            n = n/10;

            
        }
        return res;
        




    }
}

1. 两数之和

1. 用键值对Map集合 来解决 用key存元素 value存元素下标

import java.util.Map;
import java.util.HashMap;


class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> hashtable = new HashMap<>();
        int[] res = new int[2];
        for(int i=0; i<nums.length; i++){
            int temp = target-nums[i];
            if(hashtable.containsKey(temp)){
                res[0] = i;
                res[1] = hashtable.get(temp);
            }else{
                hashtable.put(nums[i],i);

            }
            
        }
        return res;


    }
}