leetcode周賽補完計劃（一）

周賽133

leetcode 1029.兩地排程

解題思路：按每個人飛往A市和B市費用的內插補點排序，取其中內插補點大，費用少的選項，滿足有N人飛往A市或B市後，剩餘人全部飛往剩下的城市

public int twoCitySchedCost(int[][] costs) {
    int h = costs.length;
    int min = 0;
    int a = 0,b = 0;
    Arrays.sort(costs, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return Math.abs(o1[0]-o1[1])-Math.abs(o2[0]-o2[1]);
        }
    });
    for(int i = h - 1;i >= 0;i--) {
        if(a < h/2 && b < h/2){
            if(costs[i][0] < costs[i][1]){
                a++;
                min+=costs[i][0];
            } else {
                b++;
                min+=costs[i][1];
            }
        }else if(a >= h / 2){
            b++;
            min+=costs[i][1];
        }else if(b >= h / 2){
            a++;
            min+=costs[i][0];
        }
    }
    return min;
}
           

leetcode 1030. 距離順序排列矩陣單元格

解題思路：按題義排序就行了。。。

public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
    int[][] matrix = new int[R*C][2];
    int index = 0;
    for(int i = 0;i < R;i++){
        for (int j = 0;j < C;j++){
            matrix[index][0] = i;
            matrix[index][1] = j;
            index++;
        }
    }
    Arrays.sort(matrix, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return (Math.abs(o1[0]-r0)+Math.abs(o1[1]-c0))-(Math.abs(o2[0]-r0)+Math.abs(o2[1]-c0));
        }
    });
    return matrix;
}
           

leetcode 1031. 兩個非重疊子數組的最大和

解題思路：建立數組，滑動視窗儲存所有長度為L和M的子數組的和，周遊取L和M不重疊的最大和

public int maxSumTwoNoOverlap(int[] A, int L, int M) {
  	int[] sum1 = new int[1000],sum2 = new int[1000];
    int len = A.length;
    int max = 0;
    for(int i = 0;i < L;i++){
        sum1[0]+=A[i];
    }
    for(int i = 1;i < len - L + 1;i++){
        sum1[i] = sum1[i - 1] - A[i - 1] + A[i + L - 1];
    }
    for(int i = 0;i < M;i++){
        sum2[0]+=A[i];
    }
    for(int i = 1;i < len - M + 1;i++){
        sum2[i] = sum2[i - 1] - A[i - 1] + A[i + M - 1];
    }
    
    for(int i = 0;i < len - L + 1;i++){
        for(int j = 0;j < len - M + 1;j++){
            if(i + L <= j || j + M <= i){
                if(max < sum1[i]+sum2[j])
                    max = sum1[i]+sum2[j];
            }
        }
    }
    return max;
}