yub‘s Algorithmic Adventures_Day8

Day8

两个数组的交集

link：349. 两个数组的交集 - 力扣（LeetCode）

思路分析

首先想到合并两个数组，遍历找重复项存储到新的数组中但其实用HashSet是更加方便的,【HashSet不存在重复数据】

**注意：使用数组做哈希表的题目都限制了大小 例如只有小写字母或者数值大小在【0-1000】内 **

HashSet

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 ) {
            return new int[0];
        }
        //创建需要的set表 set2用于返回结果
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();

        //遍历数组1
        for(int i : nums1)  {
            set1.add(i);
        }
        //遍历ser1映射的元素判断哈希表中是否存在对应元素
        for(int i : nums2) {
            if(set1.contains(i)) {
                set2.add(i);
            }
        }
        //将结果集合转换为数组
        int[] result = new int[set2.size()];
        int k = 0;
        for(int i : set2) {
            result[k++] = i;
        }
        return result;
    }
}

Tips

更高级的写法 Java8引入的流式API（Stream API）

    //将结果集合转换为数组
return set2.stream().mapToInt(x -> x).toArray();

stream()：将集合转换为流对象，便于对集合进行链式操作.
mapToInt(x -> x)：将流中的每个 Integer 元素转换为 int 类型（自动拆箱).
toArray()：将流中的元素收集为一个 int[] 数组.

Hash数组

思路相同 只不过加了大小限制之后可以用Hash数组解决

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //创建需要的两个数组  
        int[] hash1 = new int[1002];
        int[] hash2 = new int[1002];
        //分别遍历两个数组 对相同元素出现次数计数
        for(int i : nums1) {
            hash1[i]++;
        }
        for(int i : nums2) {
            hash2[i]++;
        }
        List<Integer> result = new ArrayList<>();
        //相同的下标位置都大于0 满足
        for(int i = 0; i < 1002; i++) {
          if(hash1[i] > 0 && hash2[i] > 0)
            result.add(i);
        }
        //转换成数组
        int[] finalArray = new int[result.size()];
        int index = 0;
        for(int i : result) {
            finalArray[index++] = i;
        }
        return finalArray;
 }
}   

快乐数

link：202. 快乐数 - 力扣（LeetCode）

思路分析

起初分析的时候被卡在了循环条件处【😓】，首先得不是1然后不满足快乐数条件最后不被包含在Hashset中.【是的没错是高贵的Hashset（bushi）】

class Solution {
    public boolean isHappy(int n) {
        //创建所需的set表
        Set<Integer> result = new HashSet<>();
        //循环判断 按除每一位判断
        while(n != 1 && !result.contains(n)) {
            result.add(n);
            //getNumber函数单独模拟实现
            n = getNumber(n);
        }
            return n == 1;
    }
            private int getNumber(int n) {
            int res = 0;
            //逐位进行平方求和判断
            while(n > 0) {
                int tmp = n % 10;
                res += tmp * tmp;
                n = n / 10;
            }
            return res;
        }
}

Tip

由此观之，所有判断元素是否出现过的题目都可以用哈希法解决.
一般哈希表都是用来快速判断一个元素是否出现集合里.

原文地址：https://blog.csdn.net/weixin_72981769/article/details/142866374

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！