LeetCode

LeetCode-哈希

Posted by 黑矮皮卡 on October 23, 2024

哈希前置知识

哈希：快速判断一个元素是否出现集合里（牺牲空间换取时间）
● 哈希函数：把传入的key映射到符号表的索引上
● 哈希碰撞：多个key映射到相同索引上（处理碰撞方式：拉链法和线性探测法）
数据结构：
● 数组：大小有限（空间大但哈希值少）
● set (集合）：不允许重复元素的集合（用数组造成空间浪费时考虑set）
● map(映射)：键值对的几何

有效的字母异位词

//数组是简单哈希表，题中字符串只有小写字符，则定义一个数组记录字符串s里字符出现的次数。
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] z=new int[26];
        for(int i=0;i<s.length();i++){
            z[s.charAt(i)-'a']++;
        }
        for(int i=0;i<t.length();i++){
            z[t.charAt(i)-'a']--;
            if(z[t.charAt(i)-'a']<0){
                return false;
            }
        }
        return true;
    }
}

两个数组的交集

//nums1放set1，然后遍历nums2将交集添加到set2，最后把set2转成int数组
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1=new HashSet<>();
        Set<Integer> set2=new HashSet<>();
        for(int num:nums1){
            set1.add(num);
        }
        for(int num:nums2){
            if(set1.contains(num)){
                set2.add(num);
            }
        }
        return set2.stream().mapToInt(x -> x).toArray();
    }
}

快乐数

//用哈希法判断sum是否重复，重复是false， 否则一直找到sum为1为止。
class Solution {
    private int getNext(int n){
        int sum=0;
        while(n>0){
        int d=n%10;
        n=n/10;
        sum+=d*d;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        Set<Integer>set=new HashSet<>();
        while(n!=1&&!set.contains(n)){
            set.add(n);
            n=getNext(n);
        }
        return n==1;
    }
}

两数之和

//返回下标，因此用到map
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> h=new HashMap<>();
        for(int i=0;i<nums.length;i++){    
            if(h.containsKey(target-nums[i])){
                return new int[]{h.get(target-nums[i]),i};
            }
            h.put(nums[i],i);
        }
        return new int[0];
    }
}

四数相加II

//(a+b)+(c+d)=0,key为ab两数之和，value为两数之和出现的次数
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
   Map<Integer,Integer>h=new HashMap<>();
   for(int i:nums1){
    for(int j:nums2){
        int sum=i+j;
        h.put(sum,h.getOrDefault(sum,0)+1);
    }
   }
   int r=0;     
   for(int i:nums3){
    for(int j:nums4){
        r+=h.getOrDefault(-i-j,0);
    }
   }
   return r;
    }
}

赎金信

//类似字母异位词，但不能重复
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
       int cnt[]=new int[26];
       if(ransomNote.length()>magazine.length()){
       return false; 
       }
       for(char c:magazine.toCharArray()){
        cnt[c-'a']++;
       }
       for(char c:ransomNote.toCharArray()){
        cnt[c-'a']--;
        if(cnt[c-'a']<0){
            return false;
        }
       }
       return true;
    }
}

三数之和

//双指针：for按住一个动另两个(ij剪枝在前lr去重在找到三元后)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res= new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
            return res;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int l=i+1,r=nums.length-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum<0){
                    l++;
                }
                else if(sum>0){
                    r--;
                }
                else{
                res.add(Arrays.asList(nums[i],nums[l],nums[r])); 
                while(l<r&&nums[l]==nums[l+1])l++;
                while(l<r&&nums[r]==nums[r-1])r--;
                l++;
                r--;
            }
            }
        }
        return res;
    }
}

四数之和

//类似三数之和sum设为long防溢出
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            if(i>0&&nums[i]==nums[i-1])continue;
            for(int j=i+1;j<nums.length-2;j++){
                if(j>i+1&&nums[j]==nums[j-1])continue;
                int l=j+1,r=nums.length-1;
                while(l<r){
                    long sum=(long)nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum<target){
                        l++;
                    }
                    else if(sum>target){
                        r--;
                    }
                    else{
                        res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                    while(l<r&&nums[l]==nums[l+1])l++;
                    while(l<r&&nums[r]==nums[r-1])r--;
                    l++;
                    r--;
                    }
                }
            }
        }
        return res;
    }
}
CATALOG
    FEATURED TAGS
    LeetCode