Leetcode周赛第200场 8/2 记录

偏执的太偏执、 2023-03-04 08:09 14阅读 0赞

本次AC1.2题，第三题有思路吃饭去了，吃完回来解决了

## 第一题简单难度 ##

### 5475统计好三元组 ###

给你一个整数数组 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 的绝对值。

返回 好三元组的数量 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/count-good-triplets

示例 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 res = 0;
            for(int i=0;i<arr.length-2;i++){
                for(int j=i+1;j<arr.length-1;j++){
                    for(int k=j+1;k<arr.length;k++){
                        if(Math.abs(arr[i] - arr[j])<= a && Math.abs(arr[j] - arr[k])<=b && Math.abs(arr[i] - arr[k])<=c)
                            res++;
                    }
                }
            }
            return res;
        }
    }

## 第二题难度中等 ##

### 5476找出数组游戏的赢家 ###

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

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

返回赢得比赛的整数。

题目数据 保证 游戏存在赢家。来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-the-winner-of-an-array-game  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

![format_png][]

输入：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

class Solution {
    public:
        int getWinner(vector<int>& arr, int k) {
            int cnt = 0;
            int maxarr=0;
            for(int i=0;i<arr.size();i++){
                maxarr = max(maxarr,arr[i]);
            }
            int r=1;
            while(cnt<k){
                if(arr[0]==maxarr) return arr[0];
                if(arr[0]>arr[r]){
                    cnt++;
                    r++;
                }else{
                    cnt=1;
                    swap(arr[0],arr[r]);
                    r++;
                }
            }
            return arr[0];
        }
    };

## 第三题中等难度 ##

### 5477 ###

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

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

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid  
![format_png 1][]

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

class Solution {
        public int minSwaps(int[][] grid) {
            int n = grid.length;
            int res = 0;
            int sum;
            int[] cnt = new int[n];
            for(int i=0;i<n;i++){
                sum=0;
                for(int j=n-1;j>=0;j--){
                    if(grid[i][j]==0) sum++;
                    else break;
                }
                cnt[i]=sum;
            }
            for(int i=0;i<n;i++){
                if(cnt[i]<n-i-1){
                    for(int j=i+1;j<n;j++){
                        if(cnt[j]>=n-i-1){
                            res+=swap(cnt,i,j);
                            break;
                        }
                    }
                }
            }
            for(int i=0;i<n;i++){
                if(cnt[i]<n-1-i) return -1;
            }
            return res;
    
        }
        private int swap(int[] num,int i,int j){
            int count = 0;
            while(j>i){
                int temp = num[j-1];
                num[j-1] = num[j];
                num[j]=temp;
                j--;
                count++;
            }
            return count;
        }
    }

## 第四题待更新 ##

[format_png]: /images/20230208/315c8d66646e47ae8f47efa6920ef892.png
[format_png 1]: /images/20230208/eb0cb9b46c55491d9e0ede2a7cc2884b.png