WNJXYKの博客

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)$。