欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

力扣 LeetCode-CN 第200场双周赛

程序员文章站 2022-03-23 09:21:36
最终成绩牢骚在经历了198周、199周连续的两道题全退,1000+、2000+排名之后终于迎来了新一轮的手速竞赛。可以看到本周题相对来说非常简单,前489名都是AK了四道题的选手。自己的成绩也还算过的去,勉强挤进了前150名,得益于当天良好的状态和清晰的思路。。。正文1534.统计好三元组 - E题目内容:https://leetcode-cn.com/contest/weekly-contest-200/problems/count-good-triplets/思路:看了一下总共的数据量不...

最终成绩

力扣 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 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