技術文章 » 力扣 LeetCode-CN 第200場雙週賽

力扣 LeetCode-CN 第200場雙週賽

2020-08-08 21:56:44

最終成績

在这里插入图片描述

牢騷

在經歷了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;
        
    }
}