Leetcode - 周赛424
目录
一，3354. 使数组元素等于零
本题实际上是一个前/后缀和的问题，就是判断前缀和与后缀和的值是否相同，如果相同且当前位置的值为0，说明往左走和往右走都可以，ans += 2；如果前缀和与后缀和的值差1，如果相同且当前位置的值为0，说明只能往左走/只能往右走，ans += 1。其他情况都不会使得nums中所有元素为0，直接返回 ans。
代码如下：
class Solution {
public int countValidSelections(int[] nums) {
int s = 0;
for(int x : nums){
s += x;
}
int pre = 0, cnt = 0;
for(int x : nums){
if(x > 0){
pre += x;
}else if(pre == s - pre){
cnt += 2;
}else if(Math.abs(pre*2-s) == 1){
cnt += 1;
}
}
return cnt;
}
}二， 3355. 零数组变换 I
本题就是一道简单的差分题：
class Solution {
public boolean isZeroArray(int[] nums, int[][] queries) {
int n = nums.length;
int[] arr = new int[n+1];
for(int[] q : queries){
int l = q[0], r = q[1];
arr[l] -= 1;
arr[r+1] += 1;
}
long s = 0;
for(int i=0; i<n; i++){
s += arr[i];
if(s + nums[i] > 0) return false;
}
return true;
}
}三，3356. 零数组变换 II
本题可以直接使用二分 + 差分：
class Solution {
public int minZeroArray(int[] nums, int[][] queries) {
int l = 0, r = queries.length;
while(l <= r){
int k = (l + r) / 2;
if(check(nums, queries, k)){
r = k - 1;
}else{
l = k + 1;
}
}
return r+1 <= queries.length ? r+1 : -1;
}
boolean check(int[] nums, int[][] queries, int k){
int n = nums.length;
int[] diff = new int[n+1];
for(int i=0; i<k; i++){
int[] q = queries[i];
int l = q[0], r = q[1], val = q[2];
diff[l] -= val;
diff[r+1] += val;
}
long s = 0;
for(int i=0; i<n; i++){
s += diff[i];
if(s + nums[i] > 0) return false;
}
return true;
}
}也可以使用双指针 + 差分，枚举nums数组，同时枚举执行 queries[k]，直到 nums[i] = 0，跳出里面循环，枚举下一个 nums[i]。
代码如下：
class Solution {
public int minZeroArray(int[] nums, int[][] queries) {
int n = nums.length;
int[] diff = new int[n+1];
int k = 0, sum = 0;
for(int i=0; i<n; i++){
int x = nums[i];
sum += diff[i];
while(k < queries.length && sum + x > 0){
int[] q = queries[k];
int l = q[0], r = q[1], val = q[2];
diff[l] -= val;
diff[r+1] += val;
if(l <= i && i <= r){//满足 i 在 [L,R]
sum -= val;
}
k++;
}
if(sum + x > 0) return -1;
}
return k;
}
}四，3357. 最小化相邻元素的最大差值
如果两个数相邻没有-1，那么它们的绝对值差是固定的，可以直接计算；如果两个数相邻有-1，那么就需要进行分类讨论了（这里需要先算出与-1相邻的所有数中的最大值maxR和最小值minL，因为不管（x，y）取什么，都需要和这两值求绝对差）：
- 如果没有连续的 -1，对于 -1 左右的两个数 l 和 r （l <= r），它们的绝对差一定是 min((maxR - l+1) / 2，(r - minL+1) / 2)
- 如果有连续的 -1，对于连续 -1 左右的两个数 l 和 r （l <= r），它们的绝对差一定是 min((maxR - l + 1) / 2，(r - minL + 1) / 2，(maxR - maxL + 2) / 3)
- 这里忽略了一种情况，如果是前缀-1/后缀-1时，它只有一个数 x，它的绝对差是 min((maxR - x + 1) / 2，(x - minL + 1) / 2)
class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
int minL = Integer.MAX_VALUE;
int maxR = 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)){
minL = Math.min(minL, nums[i]);
maxR = Math.max(maxR, nums[i]);
}
}
int preI = -1;
for(int i = 0; i < n; i++){
if(nums[i] == -1) continue;
if(preI >= 0){
if(i - preI == 1){//相邻两个非0数的绝对差
ans = Math.max(ans, Math.abs(nums[i] - nums[preI]));
}else{// i - preI > 2:判断是否有连续的-1
update(Math.min(nums[preI], nums[i]), Math.max(nums[preI], nums[i]), i - preI > 2, minL, maxR);
}
}else if(i > 0){//-1 -1 -1 2 的情况
update(nums[i], nums[i], false, minL, maxR);
}
preI = i;
}
if(0 <= preI && preI < n - 1)// 2 -1 -1 -1 的情况
update(nums[preI], nums[preI], false, minL, maxR);
return ans;
}
private int ans;
void update(int l, int r, boolean big, int minL, int maxR){
int d = (Math.min(r-minL, maxR-l) + 1) / 2;
if(big) {//如果有连续的-1，还需要和 (maxR - minL + 2) / 3 比较
d = Math.min(d, (maxR - minL + 2) / 3);
}
ans = Math.max(ans, d);
}
}原文地址：https://blog.csdn.net/m0_74859835/article/details/143946763
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！