自学内容网 自学内容网

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

哈希知识基础

文章链接: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#%E5%93%88%E5%B8%8C%E8%A1%A8

242.有效的字母异位词

题目链接:https://leetcode.cn/problems/valid-anagram/description/
使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。

思路:简易的哈希表

设置一个数组,其实就是一个简单哈希表,大小为26 就可以了,初始化为0,因为字符a到字符z的ASCII也是26个连续的数值。
这个数组用来记录字符串s里字符出现的次数,把字符映射到数组也就是哈希表的索引下标上。
只需要分别的遍历一下两个字符串,遍历第一个字符串的时候,对应的位置+1;遍历第二个字符串的时候,对应的位置-1。
最后检查一下,如果数组里有的元素不为0,说明一定是谁多了字符或者谁少了字符,return false
如果数组里所有的元素都为0,说明找到了,return true

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

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

        for(int count:a)
        {
            if(count!=0)
                return false;
        }
        return true;
    }
}

时间复杂度 O(n)
空间复杂度 O(1)

349. 两个数组的交集

题目连接:https://leetcode.cn/problems/intersection-of-two-arrays/description/

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。尝试用一遍扫描实现。

解法:使用HashSet

这道题目,主要要学会使用HashSet求解即可。
但是要注意,使用数组来做哈希的题目,是因为题目都限制了数值的大小。
而这道题目没有限制数值的大小,就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for(int val:nums1)
            set1.add(val);
        for(int val:nums2)
        {
            if(set1.contains(val))
                resSet.add(val);
        }

        // 方法1:直接转成数组
        // return resSet.stream().mapToInt(x->x).toArray();
        
        // 方法2:定义一个数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int val:resSet){
            arr[j++] = val;
        }
        return arr;
    }
}

时间复杂度 O(m+n)
空间复杂度 O(m+n) ,其中 m 和 n 分别是两个数组的长度。

202. 快乐数

题目连接:https://leetcode.cn/problems/happy-number/description/

解法:哈希法快速判断

当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法了。
题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要。
还有一个难点就是求和的过程,如果对取数值各个位上的单数操作不熟悉的话,做这道题也会比较艰难。

class Solution {

    public int getSum(int n){
        int ans = 0;
        // 不能写n%10,假如是100就直接不执行了
        while(n >0){
            ans += (n%10)*(n%10);
            n = n/10;
        }
        return ans;
    }

    public boolean isHappy(int n) {
        int result = n;
        Set<Integer>set = new HashSet<>();
        // 循环
        // while(true){
        //     result = getSum(result);
        //     System.out.println(result);
        //     if(result==1)
        //         return true;
        //     else if(set.contains(result))
        //         return false;
        //     else
        //         set.add(result);
        // }

        // 第二种循环写法
        while(n!=1 && !set.contains(n)){
            set.add(n);
            n = getSum(n);
        }
        return n==1;
    }
}

时间复杂度:O(logn)
空间复杂度:O(logn)

1. 两数之和

题目连接:https://leetcode.cn/problems/two-sum/

解法:哈希法

很明显暴力的解法是两层for循环查找,时间复杂度是O(n^2)。
当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。
因为本题,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适。
再来看一下使用数组和set来做哈希法的局限。
(1)数组的大小是受限制的,而且如果元素很少,而哈希值太大会造成内存空间的浪费。
(2)set是一个集合,里面放的元素只能是一个key,而两数之和这道题目,不仅要判断y是否存在而且还要记录y的下标位置,因为要返回x 和 y的下标。所以set 也不能用。
map目的用来存放我们访问过的元素,因为遍历数组的时候,需要记录我们之前遍历过哪些元素和对应的下标,这样才能找到与当前元素相匹配的(也就是相加等于target)
map中的存储结构为 {key:数据元素,value:数组元素对应的下标}
在遍历数组的时候,只需要向map去查询是否有和目前遍历元素匹配的数值,如果有,就找到的匹配对,如果没有,就把目前遍历的元素放进map中,因为map存放的就是我们访问过的元素。
在这里插入图片描述

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 tmp = target-nums[i];
            if(map.containsKey(tmp))
            {
                res[0] = map.get(tmp);
                res[1] = i;
                return res; 
            }else{
                map.put(nums[i],i);
            }
        }
        return res;
    }
}

时间复杂度:O(n)
空间复杂度:O(n)


原文地址:https://blog.csdn.net/Captain_Aaron/article/details/135597958

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