100243. Distribute Elements Into Two Arrays I
给你一个下标从 1 开始、包含 不同 整数的数组 nums ，数组长度为 n 。
你需要通过 n 次操作，将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：
- 如果 arr1 的最后一个元素 大于 arr2 的最后一个元素，就将 nums[i] 追加到 arr1 。否则，将 nums[i] 追加到 arr2 。
通过连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。
返回数组 result 。
测试样例：
输入：nums = [2,1,3]
输出：[2,3,1]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。在第 3 次操作中，由于 arr1 的最后一个元素大于 arr2 的最后一个元素（2 > 1），将 nums[3] 追加到 arr1 。3 次操作后，arr1 = [2,3] ，arr2 = [1] 。因此，连接形成的数组 result 是 [2,3,1] 。
解答：创建两个队列，按照要求对比队列元素大小完成数组更新。
class Solution {
public int[] resultArray(int[] nums) {
List<Integer> arr1 = new ArrayList<>(), arr2 = new ArrayList<>();
arr1.add(nums[0]); arr2.add(nums[1]);
for (int i = 2; i < nums.length; ++i) {
if (arr1.get(arr1.size() - 1) > arr2.get(arr2.size() - 1)) {
arr1.add(nums[i]);
} else {
arr2.add(nums[i]);
}
}
int offset = 0;
for (int n : arr1) {
nums[offset++] = n;
}
for (int n : arr2) {
nums[offset++] = n;
}
return nums;
}
}100237. Count Submatrices with Top-Left Element and Sum Less Than k
给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。
返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵 的数目。
测试样例：
输入：grid = [[7,6,3],[6,6,1]], k = 18
输出：4
解释：只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。
解答：二维矩阵上的增强版前缀和。我们将每一列的前缀和在遍历的时候记录下。那么按行遍历的时候就能获取左上角累和情况。
class Solution {
public int countSubmatrices(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int res = 0;
int[] sum = new int[n];
for (int i = 0; i < m; ++i) {
int[] row = grid[i];
int last = 0;
for (int j = 0; j < n; ++j) {
sum[j] += row[j];
last += sum[j];
if (last <= k) {
++res;
}
}
}
return res;
}
}100234. Minimum Operations to Write the Letter Y on a Grid
给你一个下标从 0 开始、大小为 n x n 的矩阵 grid ，其中 n 为奇数，且 grid[r][c] 的值为 0 、1 或 2 。
如果一个单元格属于以下三条线中的任一一条，我们就认为它是字母 Y 的一部分：
- 从左上角单元格开始到矩阵中心单元格结束的对角线。
- 从右上角单元格开始到矩阵中心单元格结束的对角线。
- 从中心单元格开始到矩阵底部边界结束的垂直线。
当且仅当满足以下全部条件时，可以判定矩阵上写有字母 Y ：
- 属于 Y 的所有单元格的值相等。
- 不属于 Y 的所有单元格的值相等。
- 属于 Y 的单元格的值与不属于Y的单元格的值不同。
每次操作你可以将任意单元格的值改变为 0 、1 或 2 。返回在矩阵上写出字母 Y 所需的 最少 操作次数。
测试样例：
输入：grid = [[0,1,0,1,0],[2,1,0,1,2],[2,2,2,0,1],[2,2,2,2,2],[2,1,2,2,2]]
输出：12
解释：将在矩阵上写出字母 Y 需要执行的操作用蓝色高亮显示。操作后，所有属于 Y 的单元格（加粗显示）的值都为 0 ，而不属于 Y 的单元格的值都为 2 。
可以证明，写出 Y 至少需要进行 12 次操作。
解答：按照题意，分解出属于Y的元素和不属于Y的元素。暴力枚举Y和非Y元素的统一值，寻找最小值。
class Solution {
public int minimumOperationsToWriteY(int[][] grid) {
int[] yc = new int[3], oc = new int[3];
int n = grid.length;
int mid = n / 2;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j && i <= mid) {
yc[grid[i][j]] += 1;
} else if (i + j == n - 1 && i <= mid) {
yc[grid[i][j]] += 1;
} else if (mid == j && i > mid) {
yc[grid[i][j]] += 1;
} else {
oc[grid[i][j]] += 1;
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (i != j) {
res = Math.min(res, differCount(yc, i) + differCount(oc, j));
}
}
}
return res;
}
private int differCount(int[] arr, int target) {
int res = 0;
for (int i = 0; i < arr.length; ++i) {
if (i != target) res += arr[i];
}
return res;
}
}100246. Distribute Elements Into Two Arrays II
给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。
你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：
- 如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
- 如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
- 如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
- 如果仍然相等，那么将 nums[i] 追加到 arr1 。
连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。
返回整数数组 result 。
测试样例：
输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。因此，连接形成的数组 result 是 [2,3,1,3] 。
解答：这题难度不大，按照题目要求完成操作即可。难点是计算greaterCount函数，可以利用线段树储存数字分布情况，然后快速计算greaterCount函数。
class Solution {
class SegmentTree {
Map<Integer, Integer> sortMap;
List<Integer> buffer;
int[] tree;
int n, size;
public SegmentTree(Map<Integer, Integer> _sortMap) {
sortMap = _sortMap;
n = sortMap.size();
tree = new int[n * 2];
size = 0;
buffer = new ArrayList<>();
}
public int greaterCount(int val) {
int offset = sortMap.get(val) + 1;
return sumRange(offset, n - 1);
}
public void addNum(int val) {
buffer.add(val);
int offset = sortMap.get(val);
++size;
update(offset);
}
private void update(int pos) {
pos += n;
tree[pos] += 1;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
private int sumRange(int l, int r) {
l += n;
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public int[] resultArray(int[] nums) {
Map<Integer, Integer> sortMap = sortDistinctNum(nums);
SegmentTree arr1 = new SegmentTree(sortMap), arr2 = new SegmentTree(sortMap);
arr1.addNum(nums[0]);
arr2.addNum(nums[1]);
for (int i = 2; i < nums.length; ++i) {
int g1 = arr1.greaterCount(nums[i]), g2 = arr2.greaterCount(nums[i]);
if (g1 > g2) {
arr1.addNum(nums[i]);
} else if (g1 < g2) {
arr2.addNum(nums[i]);
} else {
if (arr1.size <= arr2.size) {
arr1.addNum(nums[i]);
} else {
arr2.addNum(nums[i]);
}
}
}
int[] res = new int[nums.length];
int o = 0;
for (int i : arr1.buffer) {
res[o++] = i;
}
for (int i : arr2.buffer) {
res[o++] = i;
}
return res;
}
private Map<Integer, Integer> sortDistinctNum(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for (int n : nums) {
set.add(n);
}
int offset = 0;
HashMap<Integer, Integer> res = new HashMap<>();
for (int n : set) {
res.put(n, offset++);
}
return res;
}
}