力扣 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]]为例我们分析算法过程：
- 获得arr = [2, 1, 0]
- 针对位置i=0，找到第一个满足arr[p] <= i的位置，p=2，res+= (2-0)，swap之后数组变成了arr=[0, 2, 1]。
- 针对位置i=1，找到第一个满足arr[p] <= i的位置，p=2，res+= (2-1)，swap之后数组变成了arr=[0, 1, 2]。
- 针对位置i=2，p=2满足arr[p] <= i，res+=0，不需要任何swap。
- 算法终止，返回最终的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 suit
if (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-init
l1=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;
}
}
本文地址：https://blog.csdn.net/u013576018/article/details/107886586