Leetcode第200场周赛

前言

第一次参加周赛，AC 两道暴力题，重在参与，哈哈哈。

5475. 统计好三元组(Easy)

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (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

其中 |x| 表示 x 的绝对值。

返回 好三元组的数量 。

示例 1：

输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。

示例 2：

输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
输出：0
解释：不存在满足所有条件的三元组。

提示：

• 3 <= arr.length <= 100
• 0 <= arr[i] <= 1000
• 0 <= a, b, c <= 1000

我们直接使用暴力法。

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.length, ans = 0;
        for(int i = 0; i < n - 2; i++){
            for(int j = i + 1; j < n - 1; j++){
                for(int k = j + 1; k < n; k++){
                    if(Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c){
                        ++ans;
                    }
                }
            }
        }
        return ans;
	}
}

时间复杂度O(n^3)，空间复杂度O(1)。

5476. 找出数组游戏的赢家(Medium)

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。

每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。

返回赢得比赛的整数。

题目数据 保证 游戏存在赢家。

示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况(下图)：
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

示例 2：

输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

示例 3：

输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

示例 4：

输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99

提示：

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr 所含的整数 各不相同 。
• 1 <= k <= 10^9

方法一：链表

需要频繁在数组头部和尾部进行增删，我首先想到链表。我们使用链表来模拟这个游戏规则。当 k 大于数组的长度时，我们直接返回数组中的最大值。

class Solution {
    public int getWinner(int[] arr, int k) {
        // k 大于数组长度，直接返回数组中的最大值
        if(k > arr.length){
            int ans = arr[0];
            for(int x : arr){
                ans = Math.max(ans, x);
            }
            return ans;
        }
        //将数组转换为链表
        List<Integer> arrList = Arrays.stream(arr).boxed().collect(Collectors.toList());
        LinkedList<Integer> list = new LinkedList<>(arrList);
        int count = 0;
        //模拟游戏
        while(count < k){
            int first = list.get(0), second = list.get(1);
            if(first > second){
                ++count;
                list.addLast(second);
                list.remove(1);
            }else{
                count = 1;//删除第一个结点时，count 初始化为 1
                list.addLast(first);
                list.remove(0);
            }
        }
        //链表中第一个元素为结果
        return list.get(0);
    }
}

时间复杂度O(n)，n 为数组的长度。空间复杂度O(n)，n 为数组的长度。

方法二：滑动窗口

如果可以修改数组，我们可以只用一次遍历得到答案。我们每次比较两个数，两者中较小的数绝对不可能成为结果，我们将其修改为较大的值，窗口向后移动，再次比较，同时记录获胜的次数，如果次数等于 k 直接返回。

思路来自Huth。

class Solution {
    public int getWinner(int[] arr, int k) {
        int i = 0, t = 0, n = arr.length;
        while(t < k && i < n - 1){
            if(arr[i] > arr[i + 1]){
                arr[i + 1] = arr[i];
                t++;
            }else{
                t = 1;
            }
            i++;
        }
        return arr[i];
    }
}

时间复杂度O(n)，n 为数组的长度。空间复杂度O(1)。

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

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

示例 1：

输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

示例 2：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,1]]
输出：0

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 200
• grid[i][j] 要么是 0 要么是 1 。

自己的想法：首先求出每行右侧连续的 0 的个数，使用冒泡排序，将最大值放最上面，将最小值放下面，这不是最佳答案。。。就没想出来。

贪心思路：

从第一行开始，如果该行的后缀 0 满足要求，那么直接跳过进入下一行（因为需要的后缀 0 个数都是从大到小的顺序，所以不必担心前一行使用后一行的后缀 0 个数）。

如果该行的后缀 0 个数不满足条件，那么就往下遍历找到最先（贪心，这是最小次数）满足条件的行，一行一行交换上来，记录交换的次数

如果找不到满足条件的后缀 0 ，那么返回 - 1。

贪心思路来自spaceX。

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] zero = new int[n];
        //统计每一行的后缀 0 个数
        for(int i = 0; i < n; i++){
            int count = 0;
            for(int j = n - 1; j >= 0; j--){
                if(grid[i][j] == 0){
                    ++count;
                }else{
                    break;
                }
            }
            zero[i] = count;
        }
		//记录交换的次数
        int count = 0;
        //从第一行开始判断
        for(int i = 0; i < n - 1; i++){
            if(zero[i] >= n - i - 1) continue; //条件满足
            else{//条件不满足
                int j = i;
                //尝试找满足条件的后缀 0 个数
                for(; j < n; j++){
                    if(zero[j] >= n - i - 1) break;
                }
				//未找到
                if(j == n) return -1;
				//将找到的后缀 0 个数一直交换上来
                for(; j > i; j--){
                    int temp = zero[j];
                    zero[j] = zero[j - 1];
                    zero[j - 1] = temp;
                    //增加交换次数
                    ++count;
                }
            }
        }
        return count;
    }
}

时间复杂度O(n^2)，n 为数组的长度。空间复杂度O(n)。

5478. 最大得分(Hard)

你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。

一条 合法路径 定义如下：

• 选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
• 从左到右遍历当前数组。
• 如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。

得分定义为合法路径中不同数字的和。

请你返回所有可能合法路径中的最大得分。

由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

示例 1：

输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

示例 2：

输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

示例 3：

输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。

示例 4：

输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
输出：61

提示：

• 1 <= nums1.length <= 10^5
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^7
• nums1 和 nums2 都是严格递增的数组。

自己的想法：可以把两个数组看成一个数，从两个根节点开始求路径的最大长度。

尝试构建这个二叉树，花费的时间太多，正确的方法应该是使用两个指针来模拟这个过程。

别人的思路：

相交的点将两个数组分成(k + 1)段，取每一段的较大值计入结果，使用双指针实现。

思路来自LeonDeng。

class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        //nums1 和 nums2 当前计算的段的大小
        long sum1 = 0, sum2 = 0;
        long res = 0;
        //指针
        int i = 0, j = 0;
        while(i < nums1.length && j < nums2.length){
            //有相同的点，当前段结束
            if(nums1[i] == nums2[j]){
                res += (Math.max(sum1, sum2) + nums1[i]);
                //重置段长
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }else if(nums1[i] < nums2[j]){
                //必须先将较小值的指针向后移，先将较大的后移可能会错过相同点
                sum1 += nums1[i++];//将长度添加到段长内
            }else{
                sum2 += nums2[j++];
            }
        }
		//增加剩下的段长
        while(i < nums1.length){
            sum1 += nums1[i++];
        }

        while(j < nums2.length){
            sum2 += nums2[j++];
        }
		//取两个段长最长加入到结果
        res += Math.max(sum1, sum2);
        //结果取余
        return (int)(res % 1000000007);
    }
}

时间复杂度O(max(m,n))，m 和 n 为两个数组的长度。空间复杂度O(1)。