Joseri的小站

用代码改变世界

0%

Leetcode周赛424

发表于
本文字数： 3k 阅读时长 ≈ 3 分钟

这次周赛依然只做出了三题：
T1-10min 2wa
T2-5min
T3-17min 1wa
复盘一下：

T1

https://leetcode.cn/problems/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 ，则认为选出的初始位置和移动方向 有效 。
      返回可能的有效选择方案数目。
  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
  • 至少存在一个元素 i 满足 nums[i] == 0 。

分析

由于数据量比较小，很多人都是模拟做的。但是模拟的代码也比较复杂，涉及到左右方向转换。所以可以找下规律，发现当nums[i] == 0的时候，如果左右两边的数的和相等，那么就可以往两个方向任选一个方向走即可。于是直接这样写了，然后wa了。

其实还可以发现，当左右两边的数的和 suml和sumr，如果|suml - sumr| == 1 ，那么也能成立，但是只能往大的一边走。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countValidSelections(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(auto x: nums) sum += x;
        int cur = 0;
        int ans = 0;
        for(int i = 0; i < n; i ++ ) {
            cur += nums[i];
            if(nums[i] == 0) {
                if(cur == sum - cur) ans += 2; // 左右两边相等
                else if(abs(cur - (sum - cur)) == 1) ans += 1; // 左右两边差1
            }
        }
        return ans;
    }
};

T2

https://leetcode.cn/problems/zero-array-transformation-i/

题面

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
对于每个查询 queries[i]：

  • 在 nums 的下标范围 [li, ri] 内选择一个下标子集。
  • 将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。
如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。
数组的 子集 是对数组元素的选择（可能为空）。

分析

差分数组模版题，每个位置都有对应操作完的最大值，如果数组该位置超过了最大阈值，则不成立。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size();
        vector<int> diff(n + 1), cnt(n + 1);
        for(int i = 0; i < m; i ++ ) {
            int l = queries[i][0], r = queries[i][1];
            diff[l] ++, diff[r + 1] --;
        }
        cnt[0] = diff[0];
        for(int i = 1; i < n; i ++ ) {
            cnt[i] = cnt[i - 1] + diff[i];
        }
        for(int i = 0; i < n; i ++ ) {
            if(nums[i] > cnt[i]) return false;
        }
        return true;
    }
};

T3

https://leetcode.cn/problems/zero-array-transformation-ii/description/

题面

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示在 nums 上执行以下操作：

  • 将 nums 中 [li, ri] 范围内的每个下标对应元素的值 最多 减少 vali。
  • 每个下标的减少的数值可以独立选择。

零数组 是指所有元素都等于 0 的数组。

返回 k 可以取到的 最小****非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。
提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 5 * 105
  • 1 <= queries.length <= 105
  • queries[i].length == 3
  • 0 <= li <= ri < nums.length
  • 1 <= vali <= 5

分析

二分答案+差分数组。
差分数组顾名思义，类似T2的操作，只是这里从加减1变成了常数。可以在o(1)时间内完成区间上加减定值。
由于k越大，越能满足题意，且题意为找一个最小的k，所以这一题的答案据有单调性，可以二份答案区间。这里其实k的取值可以是[1, m]，所以右边界可以设置为 m + 1 。当最终得到m+1则证明没有valid答案。
这里二分枚举答案区间，如果在区间内就把右端点 r = mid; 如果不在区间内就把左断点 l = mid + 1;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& q) {
        int n = nums.size(), m = q.size();
        int l = 0, r = m + 1;
        auto check = [&](int k) -> bool {
            vector<int> diff(n + 1), cnt(n + 1);
            for(int i = 0; i < k; i ++ ) {
                int l = q[i][0], r = q[i][1], val = q[i][2];
                diff[l] += val;
                diff[r + 1] -= val;
            }
            for(int i = 0; i < n; i ++ ) {
                cnt[i] = cnt[max(0, i - 1)] + diff[i];
                if(cnt[i] < nums[i]) return false;
            }
            return true;
        };
        while(l < r) {
            int mid = (l + r) / 2;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        return l == m + 1 ? -1 : l;
    }
};

T4

TODO….

您的支持将鼓励我继续创作！