欢迎大家加QQ群：623375442，可以方便群里面交流。
100342. Minimum Average of Smallest and Largest Elements
你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。
你需要重复以下步骤 n / 2 次：
- 从 nums 中移除 最小 的元素 minElement 和 最大 的元素 maxElement。
- 将 (minElement + maxElement) / 2 加入到 averages 中。
返回 averages 中的 最小 元素。
测试样例：
输入：nums = [7,8,3,4,15,13,4,1]
输出：5.5
解释：返回 averages 中最小的元素，即 5.5。
解答：排序后按照题意，配合指针来计算当前average，并记录最小值。
class Solution {
public double minimumAverage(int[] nums) {
Arrays.sort(nums);
int st = 0, ed = nums.length - 1;
double res = (nums[0] + nums[nums.length - 1]) / 2.0;
while (st < ed) {
res = Math.min(res, (nums[st] + nums[ed]) / 2.0);
++st;
--ed;
}
return res;
}
}100334. Find the Minimum Area to Cover All Ones I
给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。
返回这个矩形可能的 最小 面积。
测试样例：
输入：grid = [[0,1,0],[1,0,1]]
输出：6
解释：这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。
解答：遍历整个grid，寻找所有为1的节点的，最小x,y坐标和最大x,y坐标，然后计算所需要的面积。
class Solution {
public int minimumArea(int[][] grid) {
int[] nums = {0, Integer.MAX_VALUE, 0, Integer.MAX_VALUE};
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[i].length; ++j) {
if (grid[i][j] == 1) {
nums[0] = Math.max(i, nums[0]);
nums[1] = Math.min(i, nums[1]);
nums[2] = Math.max(j, nums[2]);
nums[3] = Math.min(j, nums[3]);
}
}
}
return (nums[0] - nums[1] + 1) * (nums[2] - nums[3] + 1);
}
}100337. Maximize Total Cost of Alternating Subarrays
给你一个长度为 n 的整数数组 nums。
子数组 nums[l..r]（其中 0 <= l <= r < n）的 成本 定义为：
cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)r − l
你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。
具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 i1, i2, ..., ik − 1（其中 0 <= i1 < i2 < ... < ik - 1 < n - 1），则总成本为：
cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik − 1 + 1, n − 1)
返回在最优分割方式下的子数组成本之和的最大值。
注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。
测试样例：
输入：nums = [1,-2,3,4]
输出：10
解释：一种总成本最大化的方法是将 [1, -2, 3, 4] 分割成子数组 [1, -2, 3] 和 [4]。总成本为 (1 + 2 + 3) + 4 = 10。
解答：这题可以利用动态规划。我们将每个位置记录两种状态，一种是它是1，另一种是-1。这两种状态的转移方程就比较简单了。-1的状态必然是从上一个1的状态转移过来。1的状态稍微复杂一点，它可以单独成一个子数组，也能从上一个-1继承过来。
class Solution {
public long maximumTotalCost(int[] nums) {
int len = nums.length;
long[][] mem = new long[len][2];
for (int i = 0; i < len; ++i) {
mem[i][0] = Long.MIN_VALUE;
mem[i][1] = Long.MIN_VALUE;
}
mem[0][0] = nums[0];
for (int i = 1; i < len; ++i) {
// 从上一个*-1继承过来
mem[i][1] = -nums[i] + mem[i - 1][0];
// 从上一个*1继承过来（当前位置切分一个新的子数组），或者从上一个*-1继承过来。
mem[i][0] = Math.max(mem[i - 1][0], mem[i - 1][1]) + nums[i];
}
return Math.max(mem[len - 1][0], mem[len - 1][1]);
}
}100334. Find the Minimum Area to Cover All Ones I
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形，并且满足 grid 中所有的 1 都在这些矩形的内部。
返回这些矩形面积之和的 最小 可能值。
注意，这些矩形可以相接。
测试样例：
输入：grid = [[1,0,1],[1,1,1]]
输出：5
解释：
- 位于 (0, 0) 和 (1, 0) 的 1 被一个面积为 2 的矩形覆盖。
- 位于 (0, 2) 和 (1, 2) 的 1 被一个面积为 2 的矩形覆盖。
- 位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。
解答：这题范围太小了，实际可以利用暴力计算。因为切分的3个长方形，它第一刀必然是横切 或者 竖切。然后又在切分完的两块中，寻找一块再切分，另一块就类似这周第二题寻找最小面积。
class Solution {
private int m, n;
public int minimumSum(int[][] grid) {
m = grid.length;
n = grid[0].length;
List<int[]> list = new ArrayList<>();
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[i].length; ++j) {
if (grid[i][j] == 1) {
list.add(new int[]{i, j});
}
}
}
int res = Integer.MAX_VALUE;
// 横切
for (int i = 0; i < m; ++i) {
List<int[]> left = new ArrayList<>(), right = new ArrayList<>();
for (int[] t : list) {
if (t[0] <= i) {
left.add(t);
} else {
right.add(t);
}
}
{
// 左边再切分，右边单块
int l1 = findBestTwo(left), l2 = findBestOne(right);
if (l1 != Integer.MAX_VALUE && l2 != Integer.MAX_VALUE) {
res = Math.min(l1 + l2, res);
}
}
{
// 右边再切分，左边单块
int l1 = findBestTwo(right), l2 = findBestOne(left);
if (l1 != Integer.MAX_VALUE && l2 != Integer.MAX_VALUE) {
res = Math.min(l1 + l2, res);
}
}
}
// 竖切
for (int i = 0; i < n; ++i) {
List<int[]> left = new ArrayList<>(), right = new ArrayList<>();
for (int[] t : list) {
if (t[1] <= i) {
left.add(t);
} else {
right.add(t);
}
}
{
int l1 = findBestTwo(left), l2 = findBestOne(right);
if (l1 != Integer.MAX_VALUE && l2 != Integer.MAX_VALUE) {
res = Math.min(l1 + l2, res);
}
}
{
int l1 = findBestTwo(right), l2 = findBestOne(left);
if (l1 != Integer.MAX_VALUE && l2 != Integer.MAX_VALUE) {
res = Math.min(l1 + l2, res);
}
}
}
return res;
}
// 迭代暴力，直接横切和竖切再尝试一下最小面积
private int findBestTwo(List<int[]> list) {
if (list.size() <= 1) return Integer.MAX_VALUE;
int res = Integer.MAX_VALUE;
{
for (int i = 0; i < m; ++i) {
int[] n1 = initialArr(), n2 = initialArr();
for (int[] t : list) {
if (t[0] <= i) {
update(t, n1);
} else {
update(t, n2);
}
}
if (n1[1] != Integer.MAX_VALUE && n2[1] != Integer.MAX_VALUE) {
res = Math.min(res, cal(n1) + cal(n2));
}
}
}
{
for (int i = 0; i < n; ++i) {
int[] n1 = initialArr(), n2 = initialArr();
for (int[] t : list) {
if (t[1] <= i) {
update(t, n1);
} else {
update(t, n2);
}
}
if (n1[1] != Integer.MAX_VALUE && n2[1] != Integer.MAX_VALUE) {
res = Math.min(res, cal(n1) + cal(n2));
}
}
}
return res;
}
// 和本周第二题一致，寻找最小面积。
private int findBestOne(List<int[]> grid) {
if (grid == null || grid.isEmpty()) return Integer.MAX_VALUE;
int[] nums = initialArr();
for (int[] l : grid) {
update(l, nums);
}
return cal(nums);
}
private void update(int[] l, int[] nums) {
int i = l[0], j = l[1];
nums[0] = Math.max(i, nums[0]);
nums[1] = Math.min(i, nums[1]);
nums[2] = Math.max(j, nums[2]);
nums[3] = Math.min(j, nums[3]);
}
private int[] initialArr() {
int[] nums = {0, Integer.MAX_VALUE, 0, Integer.MAX_VALUE};
return nums;
}
private int cal(int[] nums) {
return (nums[0] - nums[1] + 1) * (nums[2] - nums[3] + 1);
}
}