100224. Split the Array
给你一个长度为 偶数 的整数数组 nums 。你需要将这个数组分割成 nums1 和 nums2 两部分，要求：
- nums1.length == nums2.length == nums.length / 2 。
- nums1 应包含 互不相同 的元素。
- nums2也应包含 互不相同 的元素。
如果能够分割数组就返回 true ，否则返回 false 。
测试样例：
输入：nums = [1,1,2,2,3,4]
输出：true
分割 nums 的可行方案之一是 nums1 = [1,2,3] 和 nums2 = [1,2,4] 。
解答：数字频次计数题，保证所有数字出现次数小于等于2。
class Solution {
public boolean isPossibleToSplit(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
int c = map.getOrDefault(n, 0) + 1;
if (c > 2) {
return false;
}
map.put(n, c);
}
return true;
}
}100225. Find the Largest Area of Square Inside Two Rectangles
在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的 左下角 和 右上角 坐标。
我们定义 向右 的方向为 x 轴正半轴（x 坐标增加），向左 的方向为 x 轴负半轴（x 坐标减少）。同样地，定义 向上 的方向为 y 轴正半轴（y 坐标增加），向下 的方向为 y 轴负半轴（y 坐标减少）。
你可以选择一个区域，该区域由两个矩形的 交集 形成。你需要找出能够放入该区域 内 的 最大 正方形面积，并选择最优解。
返回能够放入交集区域的正方形的 最大 可能面积，如果矩形之间不存在任何交集区域，则返回 0。
测试样例：
输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域，或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 边长，即 1 1 = 1。可以证明，边长更大的正方形无法放入任何交集区域。
解答：题目范围很小，直接暴力枚举所有长方形的相交最大正方形边长。然后最长边长平方，返回面积。
class Solution {
public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
long max = 0;
int len = bottomLeft.length;
for (int i = 0; i < len; ++i) {
for (int j = i + 1; j < len; ++j) {
int tmp = Math.min(intersect(bottomLeft[i][0], topRight[i][0], bottomLeft[j][0], topRight[j][0]),
intersect(bottomLeft[i][1], topRight[i][1], bottomLeft[j][1], topRight[j][1]));
max = Math.max(max, tmp);
}
}
return max * max;
}
private int intersect(int x1, int x2, int y1, int y2) {
return Math.max(Math.min(y2, x2) - Math.max(x1, y1), 0);
}
}100200. Earliest Second to Mark Indices I
给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。
一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。
从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：
- 选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
- 如果 nums[changeIndices[s]] 等于 0 ，标记 下标 changeIndices[s] 。
- 什么也不做。
请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。
测试样例：
输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
输出：8
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
- 第 1 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [1,2,0] 。
- 第 2 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,2,0] 。
- 第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,1,0] 。
- 第 4 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,0,0] 。
- 第 5 秒，标记 changeIndices[5] ，也就是标记下标 3 ，因为 nums[3] 等于 0 。
- 第 6 秒，标记 changeIndices[6] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
- 第 7 秒，什么也不做。
- 第 8 秒，标记 changeIndices[8] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。最早可以在第 8 秒标记所有下标。
所以答案是 8 。
解答：时间越短，那么成功的可能性就必然越小。所以我们可以利用二分查找来寻找最优的值。当前值，利用它最后可以标记的时间来计算之前它是否可以安全被清零。
class Solution {
public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
long sum = 0;
for (int n : nums) {
sum += n;
}
if (sum + nums.length > changeIndices.length) {
return -1;
}
int st = (int)(sum + nums.length), ed = changeIndices.length;
while (st < ed) {
int mid = (st + ed) / 2;
if (!isValid(nums, changeIndices, mid)) {
st = mid + 1;
} else {
ed = mid;
}
}
return isValid(nums, changeIndices, st) ? st : -1;
}
private boolean isValid(int[] nums, int[] changeIndices, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < changeIndices.length && i + 1 <= target; ++i) {
map.put(changeIndices[i], Math.max(map.getOrDefault(changeIndices[i], 0), i + 1));
}
if (map.size() != nums.length) {
return false;
}
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (map.get(a).compareTo(map.get(b))));
for (int i = 1; i <= nums.length; ++i) {
queue.add(i);
}
int sum = 0;
while (!queue.isEmpty()) {
int tmp = queue.poll();
sum += nums[tmp - 1] + 1;
if (sum > map.get(tmp)) {
return false;
}
}
return true;
}
}100200. Earliest Second to Mark Indices II
给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。
一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。
从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：
- 选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
- 将 nums[changeIndices[s]] 设置成任意的 非负 整数。
- 选择范围 [1, n] 中的一个下标 i ， 满足 nums[i] 等于 0, 并 标记 下标 i 。
- 什么也不做。
请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。
测试样例：
输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
输出：8
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
- 这个例子中，我们总共有 7 秒。按照以下操作标记所有下标：
- 第 1 秒：将 nums[changeIndices[1]] 变为 0 。nums 变为 [0,2,3] 。
- 第 2 秒：将 nums[changeIndices[2]] 变为 0 。nums 变为 [0,2,0] 。
- 第 3 秒：将 nums[changeIndices[3]] 变为 0 。nums 变为 [0,0,0] 。
- 第 4 秒：标记下标 1 ，因为 nums[1] 等于 0 。
- 第 5 秒：标记下标 2 ，因为 nums[2] 等于 0 。
- 第 6 秒：标记下标 3 ，因为 nums[3] 等于 0 。
现在所有下标已被标记。最早可以在第 8 秒标记所有下标。
所以答案是 6 。
解答：暂时不会做，放一个别人的答案。
class Solution {
public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
long sum = 0;
int n = nums.length;
int m = changeIndices.length;
for (int v:nums) {
sum += v;
}
int[] first = new int[n+1];
int[] fp = new int[m];
Arrays.fill(first,-1);
Arrays.fill(fp,-1);
for(int i = 0; i < m; ++i) {
PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->Integer.compare(nums[o1],nums[o2]));
long ts = sum;
if (first[changeIndices[i]] == -1) {
first[changeIndices[i]] = i;
fp[i] = changeIndices[i] - 1;
}
int cnt = 0;
for (int j = i; j >= 0; --j) {
if(fp[j] == -1 || nums[fp[j]]<=1) {
continue;
}
cnt++;
ts -= nums[fp[j]];
pq.add(fp[j]);
if(pq.size()*2>(i-j+1)) {
int t = pq.poll();
cnt --;
ts += nums[t];
}
}
if(i + 1 - cnt * 2 >= ts + n - cnt) {
return i + 1;
}
}
return -1;
}
}