Leetcode (501 - 600)

发表于 | 分类于 | 0 comments

561. Array Partition I

算法

求解将2n个数组合后的最小值, 解法1，排序后隔一个取

1
2
3
4
5
6
7
8
9
10
public class Solution { 
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i = i + 2) {
            sum += nums[i];
        }
        return sum;
    }
}

算法证明:

  • Assume in each pair i, bi >= ai.
  • Denote Sm = min(a1, b1) + min(a2, b2) + … + min(an, bn). The biggest Sm is the answer of this problem. Given 1, Sm = a1 + a2 + … + an.
  • Denote Sa = a1 + b1 + a2 + b2 + … + an + bn. Sa is constant for a given input.
  • Denote di = |ai - bi|. Given 1, di = bi - ai. Denote Sd = d1 + d2 + … + dn.
  • So Sa = a1 + a1 + d1 + a2 + a2 + d2 + … + an + an + di = 2Sm + Sd => Sm = (Sa - Sd) / 2. To get the max Sm, given Sa is constant, we need to make Sd as small as possible.
  • So this problem becomes finding pairs in an array that makes sum of di (distance between ai and bi) as small as possible. Apparently, sum of these distances of adjacent elements is the smallest. If that’s not intuitive enough, see attached picture. Case 1 has the smallest Sd.

566. Reshape the Matrix

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums == null || nums.length == 0 || nums[0].length == 0) return nums;
        int m = nums.length, n = nums[0].length;
        if (m * n != r * c) return nums;
        int[][] newmatrix = new int[r][c];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int row = (i * n + j) / c;
                int col = (i * n + j) % c;
                newmatrix[row][col] = nums[i][j];
            }
        }
        return newmatrix;
    }
}