【代码随想录算法训练营-第七天】【哈希表】454,383,15,18

2024-01-08 21:39:27

454. 四数相加 II

第一遍

  • 思路
    • 想不出来,除了暴力解法,完全想不出来其他解法,看答案思路了…
    • 学习了两个新的方法:
      • getOrDefault:返回指定键对应的值,如果不存在,则返回默认值
      • containsKey:判断是否包含key
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sum = nums1[i] + nums2[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        for (int k = 0; k < nums3.length; k++) {
            for (int l = 0; l < nums4.length; l++) {
                int judge_num = -(nums3[k] + nums4[l]);
                if (map.containsKey(judge_num)) {
                    count += map.get(judge_num);
                }
            }
        }
        return count;
    }
}

383. 赎金信

第一遍

  • 思路
    • 这题想出来了,用了15mins,思考+做题;
    • 做完之后看了一下给的题解范例,使用了数组+字符的ascii码只有0-26;
    • 巧妙的利用了字符串ascii码;
    • 同时,因为利用了数组,数据结构更加简单,用时大幅减少;在这里插入图片描述
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            String word = String.valueOf(magazine.charAt(i));
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            String word = String.valueOf(ransomNote.charAt(i));

            if (!map.containsKey(word)) {
                return false;
            }
            if (map.get(word) < 1) {
                return false;
            }
            map.put(word, map.getOrDefault(word, 0) - 1);
        }
        return true;
    }
}
// 代码随想录提供的题解
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] judge = new int[26];
        for (char word : magazine.toCharArray()) {
            judge[word - 'a'] += 1;
        }
        for (char c : ransomNote.toCharArray()) {
            judge[c - 'a'] -= 1;
        }
        for (int i : judge) {
            if (i <= 0) {
                return false;
            }
        }
        return true;
    }
}

15. 三数之和

第一遍

  • 思路
    • 确实没想出来,先记录一下思路,回头看看能不能写出来;
    • 双指针,重点是固定和如何判定去重:
      • 如何判定去重:在移动指针的过程中,如果出现了和为0,则判断左指针的下一个/右指针的前一个,是否是相同数值的元素,如果是的话,left++ or right--
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) { 
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; 
                    left++;
                }
            }
        }
        return result;
    }
}

18. 四数之和

第一遍

  • 思路
    • 这次忘记计时了;
    • 大概思想和三书之和一样,只不过多处理一层循环而已;
    • 需要注意的地方是,用例里面会有让int溢出的场景,因此要在判断数之和与targe的大小的时候需要注意;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; ) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                i++;
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; ) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    j++;
                    continue;
                }
                int l = j + 1, r = nums.length - 1;
                int tmpTarget = target - nums[i];
                while (l < r) {
                    long threeSum = (long) nums[j] + nums[l] + nums[r];
                    if (threeSum > tmpTarget) {
                        r--;
                    } else if (threeSum < tmpTarget) {
                        l++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        while (r > l && nums[l] == nums[l + 1]) l++;
                        while (r > l && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    }
                }
                j++;
            }
            i++;
        }
        return result;
    }
}

文章来源:https://blog.csdn.net/qq_40691970/article/details/135072085
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。