力扣 LeetCode-CN 第200场双周赛

最终成绩

牢骚

在经历了198周、199周连续的两道题劝退，1000+、2000+排名之后终于迎来了新一轮的手速竞赛。可以看到本周题相对来说非常简单，前489名都是AK了四道题的选手。自己的成绩也还算过的去，勉强挤进了前150名，得益于当天良好的状态和清晰的思路。。。

正文

1534.统计好三元组 - E

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

思路：

看了一下总共的数据量不大，所以直接选择暴力O(N ^ 3)的时间复杂度去进行求解。

解题代码：

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

1535.找出数组游戏的赢家 - M

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

思路：

这道题题目很友好的告诉我们一定存在游戏的赢家，同时也说了让我们去寻找第一个符合的整数即可。我们可以先简单分析一下存在哪些情况：

1 最常规的情况：arr = [2, 1, 3, 5, 4, 6, 7], k =2。k < arr.length，arr.length - target的index > k - 1，不需要target循环的去和已经参与过比较的元素再去比较。

先看第一个元素2， 2比1大，第一次比较之后arr = [2, 3, 5, 4 ,6, 7, 1]，2再去和3比会输掉，但这次比较的结果同时导致了3获得了一次胜利，这时arr = [3, 5, 4, 6, 7, 1, 2]，3比5小，这次比较3又回输掉，但这次比较之后5留了下来并且积攒了一个胜场，5再去和4比，获胜，这时我们得到了最终的目标结果：5。

这种场景我们只需要从头寻找比他上一个数大的元素，再向后寻找k-1个元素看看是不是当前元素逗比他们大，同时注意处理第一个元素的情况，第一个元素需要向后去寻找k个元素看看是不是都比他们大

2 情况1的变体，k < arr.length, arr.length - target的index < k - 1的场景，这种场景下我们可以确定，如果k在这次比较中获胜，那么k一定是比所有从队首比较输了进入队尾的元素大，所以k只要比它到队尾的所有元素大即可，举例就是 arr = [2, 3, 4, 9, 8], k=3。具体比较路径大家可以在演算纸上自行推导。

3 特殊情况：当有 k > arr.length的时候，因为数组一定存在赢家，所以这个赢家一定是全数组最大的元素，只需要找数组最大元素即可。

解题代码：

class Solution {public int getWinner(int[] arr, int k) {int n = arr.length;if(k>=n) {return findMax(arr);}int max = Integer.MIN_VALUE;for(int i=0; i<n; i++) {if(arr[i] > max) {max = arr[i];int l = i==0? k:k-1;if(higher(arr, i , l)) {return arr[i];}}}return 0;}private boolean higher(int[] arr, int idx, int l) {int max = idx+l+1 > arr.length? arr.length: idx+l+1;for(int i=idx+1; i<max; i++) {if(arr[idx] < arr[i]) {return false;}}return true;}private int findMax(int[] arr) {int max = Integer.MIN_VALUE;for(int a:arr) {if(a > max) {max = a;}}return max;}}

1536.排布二进制网格的最少交换次数 - M

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

思路：

我们可以利用抽象思维，把二维数组转化为一维数组，抽象的依据是我们要看对角线右上的元素，所以我们关心的就是每一行最后一个非0元素的位置，相应的，例子中的grid = [[0,0,1],[1,1,0],[1,0,0]]就可以抽象成arr=[2,1,0]。得到了抽象数组之后，我们只需要让抽象数组满足arr[i] <=i即可。我们从i到n-1的位置，每次寻找从i之后第一个满足arr[p] <= i位置的元素，将p逐渐交换到i的位置并记录交换次数 p - i，然后得到交换之后的新数组arr，重复这个过程直到所有的i都满足arr[i] <= i。有一种特殊的场景是没有解，即存在位置i，在其之后的所有p点都不存在arr[p] <= i，这种情况下只需要直接返回-1即可。

以grid = [[0,0,1],[1,1,0],[1,0,0]]为例我们分析算法过程：

1. 获得arr = [2, 1, 0]
2. 针对位置i=0，找到第一个满足arr[p] <= i的位置，p=2，res+= (2-0)，swap之后数组变成了arr=[0, 2, 1]。
3. 针对位置i=1，找到第一个满足arr[p] <= i的位置，p=2，res+= (2-1)，swap之后数组变成了arr=[0, 1, 2]。
4. 针对位置i=2，p=2满足arr[p] <= i，res+=0，不需要任何swap。
5. 算法终止，返回最终的res = 2 + 1 + 0 = 3。

解题代码：

class Solution {public int minSwaps(int[][] grid) {int n = grid.length;int res = 0;int[] idx = new int[n];for (int i = 0; i < n; i++) {idx[i] = lastP(grid[i]);}for (int i = 0; i < n; i++) {int firstI = findFirst(idx, i);//non suitif (firstI == -1) {return -1;}res += firstI - i;
//      System.out.println("res = " +res);swapTo(idx, firstI, i);}return res;}private void swapTo(int[] before, int lastP, int startP) {int tmp = before[lastP];for(int i=lastP;i>startP;i--) {before[i] = before[i-1];}before[startP] = tmp;}private int findFirst(int[] arr, int target) {for(int i=target; i<arr.length; i++) {if(arr[i] <= target) {return i;}}return -1;}private int lastP(int[] arr) {for(int i=arr.length-1; i >=0; i--) {if(arr[i] == 1) {return i;}}return 0;}
}

1537.最大得分 - H

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

思路：

我不知道这道题为啥能被称之为Hard。。。思路很简单，可以简易的理解为数组对其问题我们一起过一遍题目示例1，按照相同元素在一起进行对其，如果没有元素就用x来表示，通过LinkedList或者ArrayList进行保存，同时区间内部可以求和。

题目：

Nums1 2 - 4 - 5 - 8 - 10

Nums2 4 - 6 - 8 - 9

对齐区间求和之后：

2 - 4 - 5 - 8 - 10

0 - 4 - 6 - 8 - 9

所有对齐分割点元素都可以作为跳跃点，所以我们只需要利用两个list分别保存对齐之后的区间和，每次从两个list的区间里面选最大的即可，即最终选择的结果是2 - 4 -6 - 8 -10同时要注意处理末尾的场景，不要丢失数据。在求和的过程中记得实时取模防止溢出异常。

解题代码：

class Solution {public int maxSum(int[] nums1, int[] nums2) {int modNumber = 1000000000 + 7;List<Integer> router = new ArrayList<>();List<Long> part1 = new ArrayList<>();List<Long> part2 = new ArrayList<>();long l1 = 0l;long l2 = 0l;long res = 0l;int i=0;int j=0;while(i<nums1.length && j<nums2.length) {if(nums1[i] == nums2[j]) {part1.add(l1);part2.add(l2);router.add(nums1[i]);// re-initl1=0l;l2=0l;i++;j++;} else {if(nums1[i]>nums2[j]) {l2+=nums2[j];j++;} else {l1+=nums1[i];i++;}}}while(i<nums1.length) {l1+=nums1[i];i++;}while(j<nums2.length) {l2+=nums2[j];j++;}part1.add(l1);part2.add(l2);for(int idx=0;idx<part1.size(); idx++) {res = (Math.max(part1.get(idx), part2.get(idx)) + res)% modNumber;}for(int k=0; k<router.size();k++) {res = (router.get(k) + res) % modNumber;}return (int)res % modNumber;}
}