Java教程

【力扣刷题笔记】454. 四数相加 II、383. 赎金信

本文主要是介绍【力扣刷题笔记】454. 四数相加 II、383. 赎金信,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

这是跟着代码随想录的顺序学习算法的第八天。

以下是学习题解时自己的一些理解与笔记,有错误欢迎指正与讨论。


454. 四数相加 II、383. 赎金信

参考相关链接:

454. 四数相加 II

383. 赎金信

代码随想录


笔记

454. 四数相加 II

本题的一大关键点在于,需要求的是有多少个元组能满足 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 的要求,而不是要求每个元组具体中每数组的索引。

由于同一个数组中重复的元素可算做两个元素,即在最终结果中可出现在两个元组中,故需要计算相同出现的次数。此外,本题要求的是和为0,故可借用哈希表的查询重复元素特点,用一组已知元素来判断另外一组未知元素中有没有解。

主要思路是,设置变量 count 记录次数后,先历遍前两个数组,求出两个数组的和的出现情况和次数,存到 map 中,接着,历遍后两个数组,每次求出和 nums3[k] + nums4[l] 的时候,去 map寻找 0 - (nums3[k] + nums4[l]) 的出现次数,并累加到 count 上去。

具体实现中最关键的地方就在于 map 中存了前两个数组的和的出现情况和次数,出现情况用来判断是否有解,出现次数用来进一步判断有多少组解


其他:简单的 if...else 判断可考虑学着用短路运算来代替,会使代码更加精简!

(从大佬在代码随想录中提供 JS 版本的代码中真的感受到了代码精简的酷)

for...of语句在可迭代对象(包括 ArrayMapSetStringTypedArray,arguments 对象等等)上创建一个迭代循环,调用自定义迭代钩子,并为每个不同属性的值执行语句

const array1 = ['a', 'b', 'c'];

for (const element of array1) {
  console.log(element);
}

// expected output: "a"
// expected output: "b"
// expected output: "c"
// 代码随想录JS版本
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const twoSumMap = new Map();
    let count = 0;

    for(const n1 of nums1) {
        for(const n2 of nums2) {
            const sum = n1 + n2;
            twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1) // 精简!
        }
    }

    for(const n3 of nums3) {
        for(const n4 of nums4) {
            const sum = n3 + n4;
            count += (twoSumMap.get(0 - sum) || 0) // 精简!
        }
    }

    return count;
};

383. 赎金信

主要解题思路就是,先统计 magazine 中的各个字符出现的次数,然后拿到 ransomNote 中去 “消耗”,若不够用则说明无法构成故返回 false ,否则可以构成返回 true

一些同学可能想,用数组干啥,都用map完事了,其实在本题的情况下,使用map的空间消耗要比数组大一些的,因为map要维护红黑树或者哈希表,而且还要做哈希函数,是费时的!数据量大的话就能体现出来差别了。 所以数组更加简单直接有效!

我就是用 map 的那些同学。

元素个数确定时候可以用 数组 。(真看不出来是规定了26个小写字母…)

其他:str.charCodeAt() 是个方法,不是属性。

// 代码随想录JS版本
var canConstruct = function(ransomNote, magazine) {
    const strArr = new Array(26).fill(0), 
        base = "a".charCodeAt();
    for(const s of magazine) {
        // 统计出现次数
        strArr[s.charCodeAt() - base]++;
    }
    for(const s of ransomNote) {
        // 若不够用则为false
        const index = s.charCodeAt() - base;
        if(!strArr[index]) return false;
        strArr[index]--;
    }
    return true;
};
这篇关于【力扣刷题笔记】454. 四数相加 II、383. 赎金信的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!