LeetCode Weekly 200 题解

正文索引 [隐藏]

5475. 统计好三元组

题目链接:https://leetcode-cn.com/contest/weekly-contest-200/problems/count-good-triplets/

题目大意

给定一个数组 arr,我们要找到一个三元组 (arr_i, arr_j, arr_k),满足一下条件:
* 0 <= i < j < k < arr.length
* |arr[i] – arr[j]| <= a
* |arr[j] – arr[k]| <= b
* |arr[i] – arr[k]| <= c
数据范围:3\leq arr.length \leq 100

题解

因为数据范围不是很大,所以我们可以枚举三个数据下标然后判断一下是否符合题目要求,复杂度 O(n^3)

5476. 找出数组游戏的赢家

题目链接:https://leetcode-cn.com/contest/weekly-contest-200/problems/find-the-winner-of-an-array-game/

题目大意

给定一个数组 arr,每次将开头元素同第二个元素进行打擂。如果赢的元素放在开头,输掉的元素放在数组结尾。连续进行打擂,输出第一个连胜 K 次的元素。

题解

首先,可以发现数组的最大值一定可以满足连胜 K 次的条件,所以这个过程一定可以得到答案。同时也就知道了,如果我们在遇到数组的最大值时,还没有发现找到能够连胜 K 次的数字,那么最终答案一定是这个最大值。
所以,令 n 为数组长度,我们只需要暴力的执行这个打擂过程 n 次,返回第一个满足要求的数字,如果没有直接返回数组最大值即可。

同时,因为我们只执行打擂过程 n 次,数组的移动也是没有必要的,直接拿当前的擂主按顺序在数组上比即可。

时间复杂度:O(n)

5477. 排布二进制网格的最少交换次数

题目链接:https://leetcode-cn.com/contest/weekly-contest-200/problems/minimum-swaps-to-arrange-a-binary-grid/

题目大意

给你一个 01 矩阵,你可以做的操作就是交换相邻行。为你最少执行多少次交换,可以让矩阵主对角线以上全 0,不可以返回 -1。
数据范围:矩阵规模小于等于 200。

题解

我们可以从上往下贪心分配符合要求的行,因为主对角线是左上到右下的,按照题目的要求元素为 0 的要求逐渐变宽松。换句话说,一行如果能让第 i 行如何要求,一定能让第 j (j > i) 行符合要求。

有了这个贪心分配行的方案,我们只需要从上往下检查当前行是否符合这行要求,如果不符合就从这行开始往下找第一个符合要求的行,把它换上来即可。由贪心策略,这样一定是最优的。

暴力这样写的时间复杂度:O(n^3)
用一些预处理和技巧也可以优化至 O(n^2),但是对于这题的数据范围没必要。

5478. 最大得分

题目链接:https://leetcode-cn.com/contest/weekly-contest-200/problems/get-the-maximum-score/

题目大意

给你两个严格递增的数组 nums1 与 nums2,你可以从任意一个数组开头开始遍历,一直到某一个数组的结尾,当遇到两个数组共有的数字时,你可以从这个数组的数字切换到另一个数组的相同数字上去。

对于所有可行的遍历路径,寻找一个数字之和最大的路径的数字之和。(路径上相同的数字求和时仅算一次)

题解

这题显然是一个动态规划,DP 数组表示遍历到此位置的最大路径和。但是这样确定计算 DP 数组的顺序却有些困难,因为存在在两个数组间跳跃的转移。

但是,无论如何,每次转移都一定是从较小的数组转移到较大的数字上去的。所以,我们可以按照数字大小顺序来进行动态规划,dp_v 表示在两个数组上遍历到数值 v 时的最大路径和。

为了这样做,首先我们要对两个数组中的数字进行离散化,因为仅有出现在数组中的数字才有计算的意义。

然后对一个数字 v,如果在 nums1 中他出现了并且上一个数组为 u,那么我们就可以执行转移 dp_v = max(dp_v, dp_u),对于 nums2 也是同样的道理。

最终在所有状态中找到一个最大值即可,这就是答案。

时间复杂度:O(n\log n)