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;
}