LeetCode 第384 场周赛题解(JavaScript版)

这篇具有很好参考价值的文章主要介绍了LeetCode 第384 场周赛题解(JavaScript版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

废话不多说,我们来直接看题目!没参与本次周赛的小伙伴也可以先点进去自己试试看!第 384 场周赛 - 力扣(LeetCode)

第一题:修改矩阵

题目

LeetCode 第384 场周赛题解(JavaScript版),leetcode,javascript,算法

题析

好的家人们,这个第一题,我们也是必须拿下的好吧,一道非常简单的模拟送分题,它的意思是,让我们把矩阵中,值为-1的数,变为它所在这一列最大的值,这样我们只需要模拟它的整个过程就行咯!

最简单的思路就是,双重遍历一下这个二维数组,一旦遍历到是-1,就把它替换成它这一列最大的数就OK了。果然简单到爆炸啊家人们,来,我们这就开干!

代码

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var modifiedMatrix = function(matrix) {
    // 特判
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return matrix;
    
    //设置辅助函数 -> 用于计算每列的最大值
    const big = a => {
        let res = matrix[0][a];
        for (let i = 1; i < matrix.length; i++) {
            if (matrix[i][a] > res) {
                res = matrix[i][a];
            }
        }
        return res;
    };
    
    //双重遍历每个值,遇到-1则替换
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == -1) {
                matrix[i][j] = big(j); 
            }
        }
    }
    return matrix;
};

 当然啦,靓仔,你可能会想到去优化一下代码,毕竟我们在计算的过程中,是会涉及到重复计算每列的最大值等等,还不如用一个Map、Set去缓存或递推等很多优化方式,但是捏,笔者认为,对于这道题,这种影响作用并不是很明显,得不偿失,第一题我们就到此为止,非常简单!

第二题:匹配模式数组的子数组数目I

题目

LeetCode 第384 场周赛题解(JavaScript版),leetcode,javascript,算法

 题析

看完题目,可见,出题人这小子还是有点老滑头啊,这铺天盖地的文字,属实是让人看了有点伤脑筋,其实,总的来说,题目的意思是:现在我有两个字符串,一个叫主串,另一个叫模板串,我需要在主串中,寻找能够匹配模板串的“子串”数量(这里的“子串”即主串的子集)

代码

咦,你会不会听完有种感觉,这不就是我们普通的字符串匹配问题嘛,我只需要找到主串中能够匹配到完整模板串的“子串”数量不就好了,如果是这样,我们很容易想到的一个做法是,我首先先设置一个变量count,用于记录“子串”数量,其次,我通过遍历主串,在每次循环中,以遍历到的这个索引为起始点,去判断它是否满足模板串,如果满足,则count加1,最后循环走完了,这个count不就是我们所要求的“子串”数量嘛,诶,还真是个不错的想法,我酷酷暴力,不说了,直接动手!

/**
 * @param {number[]} nums
 * @param {number[]} pattern
 * @return {number}
 */
var countMatchingSubarrays = function(nums, pattern) {
    let count = 0;
    const n = nums.length;
    const m = pattern.length;
    for (let i = 0; i <= n - m - 1; i++) {
        let matches = true;
      //用于判断其是否满足模板串
        for (let k = 0; k < m; k++) {
            if ((pattern[k] === 1 && !(nums[i + k + 1] > nums[i + k])) ||
                (pattern[k] === 0 && !(nums[i + k + 1] === nums[i + k])) ||
                (pattern[k] === -1 && !(nums[i + k + 1] < nums[i + k]))) {
                matches = false;
                break; 
            }
        }
        if (matches) {
            count++; 
        }
    }
    
    return count;
};

诶嘿,还真有点小帅,两道签到题,做得我美滋滋!

第三题:回文字符串的最大数量

题目

LeetCode 第384 场周赛题解(JavaScript版),leetcode,javascript,算法

题析

简单来说,题目的意思是,给出一个数组,数组里面包含了多个字符串,我们拥有一种能力,就是我们可以随意交换这些字符串中的任意两个字符(包括不同字符串上的字符,均可),这些操作,是为了保证这个数组中所拥有的回文字符串的数量最大,这个数量,就是我们本题的解!

emm....看完感觉还是有点棘手的,毕竟在做交换的时候,我们不仅要考虑到我们此次交换是否能生成一个回文串,而且还要保证说,此次交换是否为全局的最优解,会不会影响其他回文串。

啊!想到这里,如果我关用模拟的思路去走的话,我的脑海里为什么全是贪心跟dp呢,那我要不然换种思路,我们知道,不管我们交换多少次,数组里面每个字符串的长度都是不能发生改变的,只是原来的布局发生了变化,那我们不妨将所有的字符都拿出来,然后对他们进行排布,保证尽可能多地凑齐回文串,这样不就可以了嘛。(提到尽可能多,短的自然会比长的容易凑齐回文串,所以,我们选择先凑短的回文串,再考虑长的)

代码

/**
 * @param {string[]} words
 * @return {number}
 */
var maxPalindromesAfterOperations = function(words) {
    //统计每个字母出现的次数
    const arr=new Array(26).fill(0)
    for(const word of words){
        for(const s of word){
            const i=s.charCodeAt()-'a'.charCodeAt()
            arr[i]+=1
        }
    }

    //计算可以用来组成回文串的一侧的字母的个数
    let left=arr.reduce((pre,cur)=>pre+=(cur>>1),0)

    //按照字符串长度,从小到大填入字母
    let ans=0
    words.sort((a,b)=>(a.length-b.length))
        for(const word of words){
            const len=word.length>>1
            if(left<len){
                break
            }
            left-=len
            ans+=1
        }
    return ans
};

第四题:匹配模式数组的子数组数目II

题目

题目与第二问一样,与第二问不同的是,此时的数据量变大了!

在问题二中,遍历数组的方法,显而易见,它的时间复杂度:O((N-M+1)*M),其中N是主串的长度,M是模板串的长度。

咦,小鬼,这时候,你想想,如果数组特别大的话,这种相乘的形式,它的效率是非常之慢的!那有没有其他更好的解决方案呢?

那当然有!就是我们大名鼎鼎的KMP算法,对于这一小问,你有没有发现,它无非就是想在主串里面,寻找符合模板串的“子串”个数嘛,第一个阻碍我们的就是,主串它的格式,并不能直接将它与模板串进行比对得到,那我们为什么不能先将主串转为模板串的格式,接下来的工作,我们就只需要找到,主串中含有多少个模板串不就好了嘛,至于如何找到有多少个,那就是用KMP算法来帮助我们解决

对于KMP算法还不太熟悉的伙伴,这里推荐看以下两个视频,相信你能有所收获!【天勤考研】KMP算法易懂版,KMP算法之求next数组代码讲解

/**
 * @param {number[]} nums
 * @param {number[]} pattern
 * @return {number}
 */
var countMatchingSubarrays = function (nums, pattern) {
    let arr = [];
    
    // 将主串转换为模板串的格式
    for (let i = 0; i < nums.length - 1; i++) {
        arr.push(nums[i] > nums[i + 1] ? -1 : (nums[i] < nums[i + 1] ? 1 : 0));
    }
    const next = getNext(pattern);
    // 获取next数组
    function getNext(pattern) {
        const m = pattern.length;
        const next = Array(m).fill(0);

        for (let i = 1, j = 0; i < m; i++) {
            while (j > 0 && pattern[i] !== pattern[j]) {
                j = next[j - 1];
            }
            if (pattern[i] === pattern[j]) {
                next[i] = ++j;
            }
        }

        return next;
    }
    // 匹配的过程
    function kmp(arr, pattern) {
        const n = arr.length;
        const m = pattern.length;

        let i = 0;
        let j = 0;
        let count = 0;
        while (i < n) {
            if (pattern[j] === arr[i]) {
                i++;
                j++;
            }
            if (j === m) {
                count++;
                j = next[j - 1];
            } else if (i < n && pattern[j] !== arr[i]) {
                if (j !== 0) {
                    j = next[j - 1];
                } else {
                    i++;
                }
            }
        }

        return count;
    }
    return kmp(arr, pattern)
};

此时KMP算法的时间复杂度为O(N+M),其中N是主串的长度,M是模板串的长度。这里,你能否感受到KMP的强大之处呢!

最后,祝大家新年快乐,新的一年要天天开心呀

LeetCode 第384 场周赛题解(JavaScript版),leetcode,javascript,算法文章来源地址https://www.toymoban.com/news/detail-836781.html

到了这里,关于LeetCode 第384 场周赛题解(JavaScript版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode周赛】LeetCode第358场周赛

    给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数,且这两个数数位上最大的数字相等。 返回最大和,如果不存在满足题意的数字对,返回 -1 。 示例 1: 输入:nums = [51,71,17,24,42] 输出:88 解释: i = 1 和 j = 2 ,nums[i] 和 nums[j] 数位上最大的数字相等,且这

    2024年02月12日
    浏览(40)
  • 【LeetCode周赛】LeetCode第370场周赛

    一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。 给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 = i, j = n - 1 且 i != j 的所有 i, j :如果 grid[i][j] == 1,那么 i 队比 j 队 强 ;否则,j 队比 i 队 强 。 在这场比赛中,如果不存在某支强于 a 队的队伍,则认为

    2024年02月05日
    浏览(48)
  • LeetCode第354场周赛

    给你一个下标从 1 开始、长度为 n 的整数数组 nums 。 对 nums 中的元素 nums[i] 而言,如果 n 能够被 i 整除,即 n % i == 0 ,则认为 num[i] 是一个 特殊元素 。 返回 nums 中所有 特殊元素 的 平方和 。 直接模拟就好了 给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。 在一

    2024年02月16日
    浏览(55)
  • leetcode 第360场周赛

    好久没参加leetcode周赛了,比赛时间都从两小时变成了一个半小时。这次周赛由两道签到题和两道中等难度题组成,严格来说最后一道的难度也可以视为hard,但是只要想到正确的思路,编码还是比较容易的。 比赛链接:leetcode 第 360 场周赛 题目描述 给你一个长度为 n 的字符串

    2024年02月11日
    浏览(36)
  • LeetCode第343场周赛

    2023.4.30LeetCode第343场周赛 根据题意模拟 使用哈希表记录每个数出现的位置,再用m+n个集合记录每一行和每一列被涂满的格子数,若某行或某列全部被涂满则返回答案 BFS 首先将距离大于两点的曼哈顿距离的特殊路径去掉 每个点考虑经过每个特殊路径到达,分成两段,一段是当

    2024年02月02日
    浏览(40)
  • LeetCode第347场周赛

    2023.5.28LeetCode第347场周赛 从最后一位开始遍历,为0则跳过 暴力模拟 对于每个 s[i] != s[i - 1] ,要使其相等 有两种选择,翻转前 i 个,或者翻转后 n - i 个,选择代价最小的方案 动态规划 从小到大枚举所有值,每个值一定是从更小的数转移而来 定义动态规划数组f, f[i][j] 表示

    2024年02月06日
    浏览(72)
  • [LeetCode周赛复盘] 第 353 场周赛20230709

    感觉有奖品大家都来了。 T1 数学。 T2 dp。 T3 dp。 T4 差分/BIT RUPQ。 6451. 找出最大的可达成数字 1. 题目描述 2. 思路分析 为了使x num在t步内相同,需要相向而行,每步最大缩短距离是2,那么t步距离是2t。 3. 代码实现 6899. 达到末尾下标所需的最大跳跃次数 1. 题目描述 2. 思路分

    2024年02月15日
    浏览(31)
  • [LeetCode周赛复盘] 第 348场周赛20230604

    这场可惜了。 T1 模拟。 T2 模拟。 T3 倒序计算。 T4 同时限制上下界的数位DP。 6462. 最小化字符串长度 1. 题目描述 2. 思路分析 题意仔细想一下就会发现,其实会将每个字符仅留1个。 3. 代码实现 6424. 半有序排列 1. 题目描述 2. 思路分析 由于只能相邻交换来移动,因此每次只能

    2024年02月08日
    浏览(37)
  • [LeetCode周赛复盘] 第 359 场周赛20230820

    T1 模拟。 T2 数学贪心。 T3 dp。 T4 分组+滑窗。 2828. 判别首字母缩略词 1. 题目描述 2. 思路分析 按题意模拟即可。 3. 代码实现 2829. k-avoiding 数组的最小总和 1. 题目描述 2. 思路分析 贪心 1~k-1中,选了1就不能选k-1;选了2就不能选k-2… 因此可以选1~k//2 剩余的从k开始向上选。 可以

    2024年02月11日
    浏览(33)
  • leetcode第 357/358 场周赛

    可能别人有更好的解法,我这写法是不断往线段树中插入数值,每次先插入nums[i-x],然后搜索(1到i)中的最大值和(i到max)中的最小值去更新ans。 看了看别人题解,直接用set写是真的牛。自己还是见识短浅了。 暴力乱搞,考虑两种极端情况,一种无脑选profit大的,一种优先选

    2024年02月12日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包