第424场周赛：使数组元素等于零、零数组变换 Ⅰ、零数组变换 Ⅱ、最小化相邻元素的最大差值
Q1、使数组元素等于零
1、题目描述
给你一个整数数组 nums 。
开始时，选择一个满足 nums[curr] == 0 的起始位置 curr ，并选择一个移动 方向 ：向左或者向右。
此后，你需要重复下面的过程：
- 如果
curr超过范围[0, n - 1]，过程结束。 - 如果
nums[curr] == 0，沿当前方向继续移动：如果向右移，则 递增curr；如果向左移，则 递减curr。 - 如果
nums[curr] > 0:- 将
nums[curr]减 1 。 - 反转 移动方向（向左变向右，反之亦然）。
- 沿新方向移动一步。
- 将
如果在结束整个过程后，nums 中的所有元素都变为 0 ，则认为选出的初始位置和移动方向 有效 。
返回可能的有效选择方案数目。
2、解题思路
-
问题描述：
-
从一个初始位置
curr开始，选择方向（左或右），按题目要求依次处理元素。 -
如果结束时
nums所有元素为 0，则此方案有效。 -
我们需要统计满足条件的方案数目。
-
-
核心逻辑：
-
遍历所有满足
nums[curr] == 0的起始位置curr。 -
针对每个起始位置，尝试两种移动方向（左、右），模拟过程并验证是否满足条件。
-
使用辅助数组
temp保存当前模拟的状态，避免修改原始数组。
-
-
模拟移动：
-
如果当前位置值是
0，继续沿当前方向移动。 -
如果当前位置值是 >0：
- 减少当前值
1。 - 反转方向。
- 移动一步。
- 减少当前值
-
如果当前位置越界（
curr < 0或curr >= n），结束模拟。
-
-
优化点：
-
尽量减少不必要的模拟操作。
-
当发现某个状态无法满足条件时立即终止。
-
3、代码实现
class Solution {
public:
int countValidSelections(vector<int>& nums) {
int n = nums.size();
int result = 0;
// 遍历所有可能的起始位置
for (int start = 0; start < n; ++start) {
if (nums[start] != 0) {
continue;
}
// 两个方向: 1 表示向右, -1 表示向左
for (int direction : {1, -1}) {
vector<int> temp = nums; // 临时数组用于模拟
int curr = start;
bool valid = true;
while (curr >= 0 && curr < n) {
if (temp[curr] == 0) {
// 当前位置为 0, 继续移动
curr += direction;
} else if (temp[curr] > 0) {
// 当前位置 > 0
temp[curr]--; // 减少当前值
direction = -direction; // 反转方向
curr += direction; // 移动一步
} else {
// 理论上不会出现这种情况
valid = false;
break;
}
}
// 如果数组所有元素变为 0, 则该方案有效
if (valid && all_of(temp.begin(), temp.end(), [](int x) { return x == 0; })) {
result++;
}
}
}
return result;
}
};
进阶方法
通过计算前后缀来计算。
假如左边和为2，右边和为2，此时，初始方向不管是向左还是向右都可以，+2；
假如左边和为2，右边和为3，此时，初始方向必须为向右，最后从左边离开边界，+1；
假如左边和为3，右边和为2，此时，初始方向必须为向左，最后从右边离开边界，+1；
假如左边和与右边和相差大于1，此时，初始方向不管是向左还是向右都没办法将数组归零。
class Solution {
public:
int countValidSelections(vector<int>& nums) {
int total = reduce(nums.begin(), nums.end());
int ret = 0, pre = 0;
for (const auto& num : nums) {
if (num) {
pre += num;
} else if (pre * 2 == total) {
ret += 2;
} else if (abs(pre * 2 - total) == 1) {
ret++;
}
}
return ret;
}
};
4、复杂度分析
- 时间复杂度：
- 遍历所有起始位置
O(n)。 - 每个起始位置模拟两种方向，最多访问每个元素一次，因此单次模拟的复杂度为
O(n)。 - 总复杂度为 O(n2)。
- 遍历所有起始位置
- 空间复杂度：
- 额外使用了一个数组
temp，大小为 O(n)。
- 额外使用了一个数组
Q2、零数组变换 Ⅰ
1、题目描述
给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
对于每个查询 queries[i]：
- 在
nums的下标范围[li, ri]内选择一个下标子集。 - 将选中的每个下标对应的元素值减 1。
零数组 是指所有元素都等于 0 的数组。
如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。
数组的 子集 是对数组元素的选择（可能为空）。
2、解题思路
首先告诉大家，暴力过不了，超时了，打竞赛的时候第一反应还是首选暴力，最后浪费五分钟，下面是暴力代码
class Solution {
public:
bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
// 处理每个查询
for (const auto& query : queries) {
int left = query[0], right = query[1];
while (left <= right) {
nums[left++]--;
}
}
// 验证
for (const auto& num : nums) {
if (num > 0) {
return false;
}
}
return true;
}
};
暴力代码之所以超时，是因为在每个查询中，直接对范围 [left, right] 逐元素操作，时间复杂度为 O(q×k)，其中 q 是查询的数量，k 是区间长度的平均值。如何在暴力的基础上进行优化呢？
差分数组是一种高效处理区间操作的工具。通过将每次操作分摊到差分数组的起点和终点，避免了逐元素修改，从而极大地提高效率。
差分数组优化：
-
使用一个差分数组 diff 来快速记录区间的减操作：
-
在 diff[left] 加上减操作的次数。
-
在 diff[right + 1] 减去减操作的次数。
-
-
最终通过计算差分数组的前缀和，快速得到对每个位置的累积操作数。
验证零数组：
-
模拟操作时，将 nums[i] 减去当前累积操作数。
-
如果遍历完所有元素都满足条件，则返回 true。
3、代码实现
class Solution {
public:
bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> diff(n + 1, 0); // 差分数组, 大小为 n+1
// 构建差分数组
for (const auto& query : queries) {
int left = query[0], right = query[1];
diff[left] -= 1; // 在左端点减 1
if (right + 1 < n) {
diff[right + 1] += 1; // 在右端点的下一个位置加 1
}
}
// 使用差分数组模拟操作
int curr_op = 0; // 当前的操作累计值
for (int i = 0; i < n; ++i) {
curr_op += diff[i]; // 当前位置的操作累计
nums[i] += curr_op; // 应用累计操作到 nums[i]
if (nums[i] < 0) {
nums[i] = 0; // 避免负值
}
}
// 检查是否全部为零
for (const auto& num : nums) {
if (num != 0) {
return false;
}
}
return true;
}
};
4、复杂度分析
时间复杂度：
- 构建差分数组：O(q)，其中 q 是 queries 的数量。
- 应用差分并验证：O(n)，其中 n 是 nums 的长度。
- 总复杂度：O(n+q)。
空间复杂度：
- 差分数组占用 O(n) 的额外空间。
Q3、零数组变换 Ⅱ
1、题目描述
给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。
每个 queries[i] 表示在 nums 上执行以下操作：
- 将
nums中[li, ri]范围内的每个下标对应元素的值 最多 减少vali。 - 每个下标的减少的数值可以独立选择。
零数组 是指所有元素都等于 0 的数组。
返回 k 可以取到的 最小非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。
2、解题思路
差分数组优化：
- 使用差分数组快速计算范围更新操作对原数组的影响，从而避免逐元素处理范围操作的高时间复杂度。
二分查找：
- 因为 k 是单调的（即处理更多查询一定能覆盖之前的效果），可以通过二分查找逐步缩小范围，找到最小满足条件的 k。
模拟操作：
- 对于一个固定的 k，使用差分数组和前缀和模拟查询操作的效果，并检查所有元素是否可以被减少到 0。
3、代码实现
class Solution {
public:
int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int m = queries.size();
vector<int> diff(n + 1, 0);
// 判断是否能通过前 k 个查询将 nums 变为零数组
auto canMakeZero = [&](int k) -> bool {
vector<int> curr_diff = diff;
vector<int> curr_nums = nums;
// 模拟前 k 个查询
for (int i = 0; i < k; ++i) {
int l = queries[i][0], r = queries[i][1], val = queries[i][2];
curr_diff[l] -= val;
if (r + 1 < n) {
curr_diff[r + 1] += val;
}
}
// 应用差分数组到 curr_nums
int running_sum = 0;
for (int i = 0; i < n; ++i) {
running_sum += curr_diff[i];
curr_nums[i] += running_sum;
}
// 检查是否所有元素都 <= 0
for (int i = 0; i < n; ++i) {
if (curr_nums[i] > 0) {
return false;
}
}
return true;
};
// 二分查找 k 的最小值
int left = 0, right = m, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canMakeZero(mid)) {
result = mid;
// 尝试更小的 k
right = mid - 1;
} else {
// 尝试更大的 k
left = mid + 1;
}
}
return result;
}
};
4、复杂度分析
时间复杂度：
- 模拟操作：每次处理 O(n) 。
- 二分查找：最多执行O(logm) 次模拟操作。
- 总复杂度：O(n⋅logm) 。
空间复杂度：
- 差分数组和辅助数组：O(n)。
- 总复杂度：O(n)。
Q4、最小化相邻元素的最大差值
1、题目描述
给你一个整数数组 nums 。nums 中的一些值 缺失 了，缺失的元素标记为 -1 。
你需要选择 一个正 整数数对 (x, y) ，并将 nums 中每一个 缺失 元素用 x 或者 y 替换。
你的任务是替换 nums 中的所有缺失元素，最小化 替换后数组中相邻元素 绝对差值 的 最大值 。
请你返回上述要求下的 最小值 。
2、解题思路
为了解决这个问题，我们通过以下步骤：
- 定位关键元素：
- 找出所有非
-1的元素。 - 确定
-1周围的最小和最大值，因为这些值决定了如何替换-1才能尽量减少相邻差值的最大值。
- 找出所有非
- 设计更新规则：
- 考虑到可能的替换组合，我们需要维护一个变量
max_diff来记录替换后相邻元素的最大绝对差值。 - 使用一个函数
updateMaxDiff计算并更新替换后的最大差值，考虑以下情况：- 替换后的值与
-1相邻的非-1元素之间的差值。 - 存在多个连续的
-1时，跨越空位的元素之间的差值。
- 替换后的值与
- 考虑到可能的替换组合，我们需要维护一个变量
- 遍历数组：
- 遍历数组，记录每个非
-1元素的位置。 - 根据相邻关系（是否紧邻或隔空位），更新
max_diff。 - 处理边界情况，比如第一个和最后一个非
-1元素。
- 遍历数组，记录每个非
- 输出结果：
- 遍历完成后，返回
max_diff，即替换后最小化的最大绝对差值。
- 遍历完成后，返回
3、代码实现
class Solution {
public:
int minDifference(vector<int>& nums) {
int n = nums.size();
// 定义空位附近的最小值 min_adjacent 和最大值 max_adjacent
int min_adjacent = INT_MAX, max_adjacent = 0;
// 遍历数组, 确定空位相邻的最小值和最大值
for (int i = 0; i < n; ++i) {
if (nums[i] != -1 && ((i > 0 && nums[i - 1] == -1) || (i < n - 1 && nums[i + 1] == -1))) {
min_adjacent = min(min_adjacent, nums[i]);
max_adjacent = max(max_adjacent, nums[i]);
}
}
// 记录最终的最大差值
int max_diff = 0;
// 更新最大差值的函数
auto updateMaxDiff = [&](int low, int high, bool considerTriple) {
int candidate_diff = (min(high - min_adjacent, max_adjacent - low) + 1) / 2;
if (considerTriple) {
candidate_diff = min(candidate_diff, (max_adjacent - min_adjacent + 2) / 3);
}
max_diff = max(max_diff, candidate_diff);
};
int previous_index = -1; // 记录上一个非 -1 元素的位置
// 遍历数组, 计算最大差值
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) {
continue;
}
if (previous_index >= 0) {
// 如果当前元素和上一个非 -1 元素相邻
if (i - previous_index == 1) {
max_diff = max(max_diff, abs(nums[i] - nums[previous_index]));
} else {
// 如果不相邻, 计算跨越空位时的最大差值
updateMaxDiff(min(nums[previous_index], nums[i]), max(nums[previous_index], nums[i]), i - previous_index > 2);
}
} else if (i > 0) {
// 如果这是第一个非 -1 元素且它不在开头
updateMaxDiff(nums[i], nums[i], false);
}
// 更新上一个非 -1 元素的位置
previous_index = i;
}
// 如果最后一个非 -1 元素靠近数组末尾
if (0 <= previous_index && previous_index < n - 1) {
updateMaxDiff(nums[previous_index], nums[previous_index], false);
}
return max_diff;
}
};
4、复杂度分析
单次遍历数组，复杂度为 O(n)。
原文地址：https://blog.csdn.net/mmlhbjk/article/details/145147970
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！