Leetcode - 周赛424

发布于:2024-11-29 ⋅ 阅读:(29) ⋅ 点赞:(0)

目录

一,3354. 使数组元素等于零

二, 3355. 零数组变换 I

三,3356. 零数组变换 II

四,3357. 最小化相邻元素的最大差值


一,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);
    }
}


网站公告

今日签到

点亮在社区的每一天
去签到