[数据结构与算法]力扣算法学习day04-3

力扣算法学习day04-3

1-两树之和

题目

代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 题目提示已经说了长度大于2，故不需要写空和长度空的判断了。
        // 这道题主要采用map的特性解决。
        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i = 0;i < nums.length;i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }
}

454-四数相加

题目

代码实现

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 由提示知，数组的长度大于1.故可省略判断。
        HashMap<Integer,Integer> mapA = new HashMap<>();

        // 求得前两个数组相加的各种可能，并放入mapA中，并记录出现的次数。
        for(int i = 0;i < nums1.length;i++){
            for(int j = 0;j < nums1.length;j++){
                Integer temp = mapA.get(nums1[i] + nums2[j]);
                mapA.put(nums1[i] + nums2[j],temp == null ? 1 : temp + 1);
            }
        }

        // 将后两个数组也相加，然后计算判断是否有满足为0的，并统计次数。
        int number = 0;
        for(int i = 0;i < nums1.length;i++){
            for(int j = 0;j < nums1.length;j++){
              int temp = nums3[i] + nums4[j];
              if(mapA.containsKey(0 - temp)){
                  number += mapA.get(0 - temp);
              }  
            }
        }

        return number;
    }
}

383-赎金信

题目

代码实现

class Solution {
    // easy，not describe
    // public boolean canConstruct(String ransomNote, String magazine) {
    //     HashMap<Character,Integer> map = new HashMap<>();
    //     char[] a = ransomNote.toCharArray();
    //     char[] b = magazine.toCharArray();

    //     for(int i = 0;i < b.length;i++){
    //         Integer temp = map.get(b[i]);
    //         map.put(b[i],temp == null ? 1 : temp + 1);
    //     }

    //     for(int i = 0;i < a.length;i++){
    //         Integer temp = map.get(a[i]);
    //         if(temp == null || temp <= 0){
    //             return false;
    //         }
    //         map.put(a[i],temp - 1);
    //     }

    //     return true;
    // }

    // 数组版本，更快 9ms --> 1ms
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] cout = new int[26]; 
        char[] a = ransomNote.toCharArray();
        char[] b = magazine.toCharArray();

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

        for(int i = 0;i < a.length;i++){
            if(cout[a[i] - 'a'] <= 0){
                return false;
            }
            cout[a[i] - 'a']--;
        }

        return true;
    }
}