欢迎大家加QQ群：623375442，可以方便群里面交流。
100460. Make Array Elements Equal to Zero
给你一个整数数组 nums 。
开始时，选择一个满足 nums[curr] == 0 的起始位置 curr ，并选择一个移动 方向 ：向左或者向右。
此后，你需要重复下面的过程：
- 如果 curr 超过范围 [0, n - 1] ，过程结束。
- 如果 nums[curr] == 0 ，沿当前方向继续移动：如果向右移，则 递增 curr ；如果向左移，则 递减 curr 。
- 如果 nums[curr] > 0:
- 将 nums[curr] 减 1 。
- 反转 移动方向（向左变向右，反之亦然）。
- 沿新方向移动一步。
如果在结束整个过程后，nums 中的所有元素都变为 0 ，则认为选出的初始位置和移动方向 有效 。
返回可能的有效选择方案数目。
测试样例：
输入：nums = [1,0,2,0,3]
输出：2
解释：可能的有效选择方案如下：
- 选择 curr = 3 并向左移动。
- [1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,0].
- 选择 curr = 3 并向右移动。
- [1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].
解答：暴力模拟枚举。
class Solution {
public int countValidSelections(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
continue;
}
if (isValid(Arrays.copyOf(nums, nums.length), i, 1)) {
++res;
}
if (isValid(Arrays.copyOf(nums, nums.length), i, -1)) {
++res;
}
}
return res;
}
private boolean isValid(int[] nums, int pos, int dir) {
while (pos >= 0 && pos < nums.length) {
if (nums[pos] == 0) {
pos += dir;
} else {
nums[pos] -= 1;
dir *= -1;
pos += dir;
}
}
for (int n : nums) {
if (n != 0) {
return false;
}
}
return true;
}
}100481. Zero Array Transformation I
给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
对于每个查询 queries[i]：
- 在 nums 的下标范围 [li, ri] 内选择一个下标子集。
- 将选中的每个下标对应的元素值减 1。
零数组 是指所有元素都等于 0 的数组。
如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。
数组的 子集 是对数组元素的选择（可能为空）。
测试样例：
输入：nums = [1,0,1], queries = [[0,2]]
输出：true
解释：
- 对于 i = 0：
- 选择下标子集 [0, 2] 并将这些下标处的值减 1。
- 数组将变为 [0, 0, 0]，这是一个零数组。
解答：利用前缀和记录queries的情况，然后一次应用所有计算。
class Solution {
public boolean isZeroArray(int[] nums, int[][] queries) {
int[] count = new int[nums.length];
for (int[] q : queries) {
count[q[0]] += 1;
if (q[1] + 1 < nums.length) {
count[q[1] + 1] -= 1;
}
}
int sum = 0;
for (int i = 0; i < nums.length; ++i) {
sum += count[i];
if (nums[i] - sum > 0) {
return false;
}
}
return true;
}
}100483. Zero Array Transformation II
给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。
每个 queries[i] 表示在 nums 上执行以下操作：
- 将 nums 中 [li, ri] 范围内的每个下标对应元素的值 最多 减少 vali。
-每个下标的减少的数值可以独立选择。零数组 是指所有元素都等于 0 的数组。
返回 k 可以取到的 最小非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。
测试样例：
输入：nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]
输出：2
解释：
- 对于 i = 0（l = 0, r = 2, val = 1）：
- 在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。
- 数组将变为 [1, 0, 1]。
- 对于 i = 1（l = 0, r = 2, val = 1）：
- 在下标 [0, 1, 2] 处分别减少 [1, 0, 1]。
- 数组将变为 [0, 0, 0]，这是一个零数组。因此，k 的最小值为 2。
解答：和第二题类似的思路，用前缀和压缩queries的情况。唯一区别是，题目要求我们找到正确的查询次数。利用折半搜索寻找。
class Solution {
public int minZeroArray(int[] nums, int[][] queries) {
int st = 0, ed = queries.length;
while (st < ed) {
int mid = (st + ed) / 2;
if (isValid(nums, queries, mid)) {
ed = mid;
} else {
st = mid + 1;
}
}
return isValid(nums, queries, st) ? st : -1;
}
private boolean isValid(int[] nums, int[][] queries, int mid) {
long[] count = new long[nums.length + 1];
for (int i = 0; i < mid; ++i) {
count[queries[i][0]] += queries[i][2];
count[queries[i][1] + 1] -= queries[i][2];
}
long sum = 0;
for (int i = 0; i < nums.length; ++i) {
sum += count[i];
if (nums[i] - sum > 0) {
return false;
}
}
return true;
}
}100497. Minimize the Maximum Adjacent Element Difference
给你一个整数数组 nums 。nums 中的一些值 缺失 了，缺失的元素标记为 -1 。
你需要选择 一个正 整数数对 (x, y) ，并将 nums 中每一个 缺失 元素用 x 或者 y 替换。
你的任务是替换 nums 中的所有缺失元素，最小化 替换后数组中相邻元素 绝对差值 的 最大值 。
请你返回上述要求下的 最小值 。
测试样例：
输入：nums = [1,2,-1,10,8]
输出：4
解释：选择数对 (6, 7) ，nums 变为 [1, 2, 6, 10, 8] 。
相邻元素的绝对差值分别为：
- |1 - 2| == 1
- |2 - 6| == 4
- |6 - 10| == 4
- |10 - 8| == 2
解答：这题是真的思维题。想了很长时间，以至于第三题都没空做完。。。幸好这题足够难，这周的排名还是挺不错的。具体步骤：
- 找到所有-1周围的数字
- 如果没有-1，就返回当前最大diff
- 如果-1周围的数字都一样，也没必要计算，直接返回0
- min和max是最重要的，我们选择加入的数不可能小于min，也不可能大于max（相比于选择min与max之间的数字，只会导致diff进一步增加），利用折半搜索寻找答案。为什么这里可以选择折半搜索。我们假设选择的是x和y（x < y)。且这个时候x - min = binarySearh, max - y = binarySearh。我们有接下来几种情况：
- a < b < x < y: 这个时候diff必然小于binarySearh
- a < x < b < y: diff = min(binarySearch, b - x)
- a < x < y < b: 间隔一个-1: diff = min(binarySearch, y - a, b - x)。大于一个-1：diff = min(binarySearch, y - x)
- x < a < b < y: diff = min(binarySearch, b - x, y - a)
- x < a < y < b: diff = min(binarySearch, y - a)
- x < y < a < b: 这个时候diff必然小于binarySearh
可以发现x, y尽量大，就能确保binarySearch到达。
class Solution {
public int minDifference(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int curDiff = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == -1) {
if (i - 1 >= 0 && nums[i - 1] != -1) {
min = Math.min(min, nums[i - 1]);
max = Math.max(max, nums[i - 1]);
}
if (i + 1 < nums.length && nums[i + 1] != -1) {
min = Math.min(min, nums[i + 1]);
max = Math.max(max, nums[i + 1]);
}
} else if (i - 1 >= 0 && nums[i - 1] != -1) {
curDiff = Math.max(curDiff, Math.abs(nums[i] - nums[i - 1]));
}
}
if (min == Integer.MAX_VALUE) {
return curDiff;
}
int diffBetween = (max - min) / 2 + (max - min) % 2;
if (diffBetween <= curDiff) {
return curDiff;
}
int st = curDiff, ed = diffBetween;
while (st < ed) {
int mid = (st + ed) / 2;
if (isValid(nums, Math.min(min + mid, max - mid), max - mid, mid)) {
ed = mid;
} else {
st = mid + 1;
}
}
return st;
}
private boolean isValid(int[] nums, int left, int right, int target) {
int st = 0;
while (st < nums.length && nums[st] == -1) {
++st;
}
int diff = 0;
if (st == nums.length) {
return true;
} else if (st != 0) {
diff = Math.max(diff, Math.min(Math.abs(nums[st] - left), Math.abs(nums[st] - right)));
}
int ed = nums.length - 1;
while (nums[ed] == -1) {
--ed;
}
if (ed != nums.length - 1) {
diff = Math.max(diff, Math.min(Math.abs(nums[ed] - left), Math.abs(nums[ed] - right)));
}
int last = nums[st], pos = st;
int[] d1 = {left, right}, d2 = {left, left}, d3 = {right, right};
for (int i = st; i <= ed; ++i) {
if (nums[i] != -1) {
if (i - pos >= 2) {
int tmp = Math.min(calculateDiff(nums[i], last, d2), calculateDiff(nums[i], last, d3));
if (i - pos > 2) {
tmp = Math.min(tmp, calculateDiff(nums[i], last, d1));
}
diff = Math.max(diff, tmp);
}
last = nums[i];
pos = i;
}
}
return diff <= target;
}
private int calculateDiff(int min, int max, int[] n2) {
int res = Integer.MAX_VALUE;
for (int l : n2) {
for (int r : n2) {
int d1 = Math.abs(min - l), d2 = Math.abs(max - r);
int tmp = Math.max(d1, d2);
if (l != r) {
tmp = Math.max(tmp, Math.abs(l - r));
}
res = Math.min(res, tmp);
}
}
return res;
}
}