哈希表开始 代码随想录训练营第6天

发布时间:2023年12月19日

代码随想录训练营第6天

今日任务

●??哈希表理论基础

●??242.有效的字母异位词

●??349.?两个数组的交集

●??202.?快乐数

●??1.?两数之和

1.哈希表理论基础

了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set?和map。

当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。??这句话很重要,大家在

文章讲解:https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

2.242.有效的字母异位词

242.?有效的字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        //判断一个元素是否在什么中,考虑用哈希表法
        //将第一个数组元素通过你哈希值,转成索引,保存在哈希表中
        //将第二个数组元素通过哈希值得到索引,检查包不包含在哈爱惜表中,有就把它删掉,然后如果遍历哈希表得到值为0的话,那么就证明字母都是一样的

        //哈希表已经是封装定义好的,直接拿来用就行
        //比如说数值容量小的用数组,容量大用set,有value key我们用map
        //这里是字母字符串,只有26个字母,那我i们就用数组,数组元素都默认是0
        //先定义一个容量为26的数组,用来统计每一个字符串里面字母出现的频率,出现就在元素里面+1
        int[] hash=new int[26];
        for(int i=0;i<s.length();i++){
            //字符串包含 unicode 字符怎么办,用当前的字符减去字母第一个a,如果是a-a的话,最终a就在下标0的位置
            hash[s.charAt(i)-'a']++;
        }
        //遍历第二个字符串
        for(int i=0;i<t.length();i++){
            hash[t.charAt(i)-'a']--;
        }//将出现在同一个索引下标的元素减减

        //遍历hash数组,如果每个元素都是0,的话,证明两个字符串字母都是相同的
        for(int i=0;i<hash.length;i++){
            if(hash[i]!=0){return false;}
        }
        return true;
        //字符串的长度是方法,要用length()
        //数组的长度是属性,用.length
    }
}

3.?349.?两个数组的交集

349.?两个数组的交集

法一:数组

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //因为1 <= nums1.length, nums2.length <= 1000
        //先用数组解决
        int[] hash1=new int[1000];
        int[] hash2=new int[1000];

        //创建一个集合
        List<Integer> resList = new ArrayList<>(); 

        //遍历第一个刷组,将每一个元素出现的频率存储到哈希表中,并且值都给到1
        for(int i=0;i<nums1.length;i++){
            //hash1[nums1[i]%1000]++;
            hash1[nums1[i]]=1;
        }
        //遍历第二个数组,查看第二个数组的值在哈希表中位置的值是否等于1,如果等于1,证明是交集,那么我们存储到新的集合中(可以去重)
        for(int i=0;i<nums2.length;i++){
            if(hash1[nums2[i]]==1){
                //证明是交集
                resList.add(nums2[i]);
            }
        }
        //转为HashSet进行去重
        HashSet<Integer> set = new HashSet<>(resList);
         return set.stream().mapToInt(x->x).toArray();
        //遍历这些数值

    }
}

法二: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];
        }
        //用HashSet解决
        Set<Integer> hashSet1=new HashSet<>();
        Set<Integer> hashSet2=new HashSet<>();
        //将两个数组的元素存进哈希表中
        //这里遍历用for(int num:nums){输出num},这里的num就是每一个元素的值,而不是下标
        for(int num:nums1){
            hashSet1.add(num);
        }
        //判断数组2中的元素是否在1中包含过,如果包含过,则存进哈希表中
        for(int num:nums2){
            if(hashSet1.contains(num)){
                hashSet2.add(num);
            }
        }
        //那现在hashSet2就是存储着两个数组的交集了,HashSet也已经帮我们去重过了
        //直接将set转为数组就好
        return hashSet2.stream().mapToInt(x->x).toArray();
    }
}

4.202.?快乐数

202.?快乐数

class Solution {
    public boolean isHappy(int n) {
        //判断一个数是不是什么,优先考虑到哈希
        Set<Integer> hashSet1=new HashSet<>();
        while(n!=1&&!hashSet1.contains(n)){
            //如果结果不是1,那就把元素添加进哈希表中
            hashSet1.add(n);
            //继续去算每个位置上的数字的平方和
            n=getNextNumber(n);
        }
        //如果和为1,那么就证明是快乐数
        return n==1;
    }

    //求出每个位置的值,存进哈希表中
        //如果result是大于1,就继续重复这一段(写成一个函数)
        private int getNextNumber(int n){//每个位置上的数字的平方和
            int result=0;
            while(n>0){
                //取个位数
                int temp=n%10;
                result+=temp*temp;
                //舍去最后一位
                n=n/10;
            }
            return result;
        }
}

5.1.?两数之和

1.?两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //请你在该数组中找出 和为目标值 target  的那 两个 整数
        //考虑用到哈希

        //我们用哈希表来存放我们遍历过的元素(元素值和下标)
        //因为要找元素值和下标,所以我们考虑用哈希的map结构来存储
        Map<Integer,Integer> hashmap=new HashMap<>();
        
        //存放
        int[] arr=new int[2];

        if(nums == null || nums.length == 0){
            return arr;
        }

        //我们遍历元素,遍历第一个元素的时候,就要想当前target-当前元素的值是否在map集合中出现过,如果出现过,就证明我们找到了
        //如果没出现过,就继续往下遍历
        for(int i=0;i<nums.length;i++){
            int s=target-nums[i];
            if(hashmap.containsKey(s)){
                arr[0]=hashmap.get(s);
                arr[1]=i;
                break;
            }
                //往map里面存
                hashmap.put(nums[i],i);
        }
        //遍历完了
        return arr;
    }
}
文章来源:https://blog.csdn.net/Belle_Daisy/article/details/135087570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。