力扣 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; }
}
文章来源: zclhit.blog.csdn.net，作者：zclhit_，版权归原作者所有，如需转载，请联系作者。
原文链接：zclhit.blog.csdn.net/article/details/107886586
- 点赞
- 收藏
- 关注作者
评论（0）