且听疯吟

leetcode weekly contes 353

2023-07-11

leetcode weekly contes 353

本周的题目质量还可以，都不算太难，但是有不少值得深思的地方，需要仔细去思考，很多有可以优化的解法或者可以将其进行扩展的解法。

2769. 找出最大的可达成数字

给你两个整数 num 和 t 。

如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等，则称其为 可达成数字 ：

  • 每次操作将 x 的值增加或减少 1 ，同时可以选择将 num 的值增加或减少 1 。

返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。

示例 1：

输入：num = 4, t = 1
输出：6
解释：最大可达成数字是 x = 6 ，执行下述操作可以使其等于 num ：
- x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。 
可以证明不存在大于 6 的可达成数字。

示例 2：

输入：num = 3, t = 2
输出：7
解释：最大的可达成数字是 x = 7 ，执行下述操作可以使其等于 num ：
- x 减少 1 ，同时 num 增加 1 。此时，x = 6 且 num = 4 。 
- x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。 
可以证明不存在大于 7 的可达成数字。

提示：

  • 1 <= num, t <= 50

地址

https://leetcode.cn/contest/weekly-contest-353/problems/find-the-maximum-achievable-number/

题意

直接模拟

思路

  1. 最大值一定是 $x$ 每次减 $1$，$num$ 每次加 $1$，此时经过 $t$ 次操作后，可以知道满足 $x - t = num + t$，可以得到最终结果 $x = num + 2t$。
  2. 复杂度分析：
  • 时间复杂度：$O(1)$。
  • 空间复杂度：$O(1)$。

代码

[sol1-C++]
class Solution {
public:
    int theMaximumAchievableX(int num, int t) {
        return num + t * 2;
    }
};

2770. 达到末尾下标所需的最大跳跃次数

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。

你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：

  • 0 <= i < j < n
  • -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数 。

如果无法到达下标 n - 1 ，返回 -1 。

示例 1：

输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。

示例 2：

输入：nums = [1,3,6,4,1,2], target = 3
输出：5
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。

示例 3：

输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。

提示：

  • 2 <= nums.length == n <= 1000
  • -109 <= nums[i] <= 109
  • 0 <= target <= 2 * 109

地址

https://leetcode.cn/contest/weekly-contest-353/problems/maximum-number-of-jumps-to-reach-the-last-index/

题意

排序 + 动态规划

思路

  1. 由于每次跳跃只能从前往后跳，所以操作就比较简单了，设 $dp[i]$ 表示跳跃到 $i$ 的最小次数，此时可以得到递推公式如下:
    $$
    dp[i] = \min (dp[i], dp[i- j] + 1) \quad if \quad nums[i] - nums[j]| \le target
    $$
    依次遍历所有可能的跳跃状态即可。

  2. 复杂度分析：

  • 时间复杂度：$O(n^2)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(n, -1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] >= 0) {
                for (int j = i + 1; j < n; j++) {
                    if (abs(nums[i] - nums[j]) <= target) {
                        dp[j] = max(dp[j], dp[i] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }
};

2771. 构造最长非递减子数组

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。

让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。

你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。

以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

示例 1：

输入：nums1 = [2,3,1], nums2 = [1,2,1]
输出：2
解释：构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]
从下标 0 开始到下标 1 结束，形成了一个长度为 2 的非递减子数组 [2,2] 。 
可以证明 2 是可达到的最大长度。

示例 2：

输入：nums1 = [1,3,2,1], nums2 = [2,2,3,4]
输出：4
解释：构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]
整个数组形成了一个长度为 4 的非递减子数组，并且是可达到的最大长度。

示例 3：

输入：nums1 = [1,1], nums2 = [2,2]
输出：2
解释：构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums1[1]] => [1,1] 
整个数组形成了一个长度为 2 的非递减子数组，并且是可达到的最大长度。

提示：

  • 1 <= nums1.length == nums2.length == n <= 105
  • 1 <= nums1[i], nums2[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-353/problems/longest-non-decreasing-subarray-from-two-arrays/

题意

最长递增子序列

思路

  1. 典型的 $LIS$ 问题，由于要求子序列连续，所以题目本身就非常简单了，设 $dp[i][0]$ 表示前 $i$ 个元素且 $nums1[i]$ 为结尾的最长非递减子序列的长度，$dp[i][1]$ 表示前 $i$ 个元素且以 $nums2[i]$ 为结尾的最长非递减子序列的长度，此时我们可以得到递推公式如下:
    $$
    dp[i][0] = \max (dp[i][0], dp[i-1][0] + 1) \quad if \quad nums1[i] \ge nums1[i-1] \
    dp[i][0] = \max (dp[i][0], dp[i-1][1] + 1) \quad if \quad nums1[i] \ge nums2[i-1] \
    dp[i][1] = \max (dp[i][1], dp[i-1][0] + 1) \quad if \quad nums2[i] \ge nums1[i-1] \
    dp[i][1] = \max (dp[i][1], dp[i-1][1] + 1) \quad if \quad nums2[i] \ge nums2[i-1]
    $$

即为非常经典的动态规划问题，根据上述的递推公式进行遍历即可。

  1. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(1)$，其中 $1$ 。

代码

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> dp(2, 1);
        int res = 1;
        for (int i = 1; i < n; i++) {
            vector<int> ndp(2, 1);
            if (nums1[i] >= nums1[i - 1]) {
                ndp[0] = max(ndp[0], dp[0] + 1);
            }
            if (nums1[i] >= nums2[i - 1]) {
                ndp[0] = max(ndp[0], dp[1] + 1);
            }
            if (nums2[i] >= nums1[i - 1]) {
                ndp[1] = max(ndp[1], dp[0] + 1);
            } 
            if (nums2[i] >= nums2[i - 1]) {
                ndp[1] = max(ndp[1], dp[1] + 1);
            }
            dp = move(ndp);
            res = max({res, dp[0], dp[1]});
        }
        return res;
    }
};

2772. 使数组中的所有元素都等于零

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。

你可以对数组执行下述操作 任意次 ：

  • 从数组中选出长度为 k 的 任一 子数组，并将子数组中每个元素都 减去 1 。

如果你可以使数组中的所有元素都等于 0 ，返回 true ；否则，返回 false 。

子数组 是数组中的一个非空连续元素序列。

示例 1：

输入：nums = [2,2,3,1,1,0], k = 3
输出：true
解释：可以执行下述操作：
- 选出子数组 [2,2,3] ，执行操作后，数组变为 nums = [1,1,2,1,1,0] 。
- 选出子数组 [2,1,1] ，执行操作后，数组变为 nums = [1,1,1,0,0,0] 。
- 选出子数组 [1,1,1] ，执行操作后，数组变为 nums = [0,0,0,0,0,0] 。

示例 2：

输入：nums = [1,3,1,1], k = 2
输出：false
解释：无法使数组中的所有元素等于 0 。

提示：

  • 1 <= k <= nums.length <= 105
  • 0 <= nums[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-353/problems/apply-operations-to-make-all-array-elements-equal-to-zero/

题意

差分数组或者线段树

思路

  1. 根据题目可以知道每次需要将连续的 $k$ 个元素将去相同的 $x$，我们从第 $1$ 个元素开始遍历，
  • 如果 $nums[0] = 0$ 则此时我们不需要再进行操作直接检测下一个元素 $nums[1]$;
  • 如果 $nums[0] < 0$，则此时一定不满足题目要求，无法将其变为 $0$；
  • 如果 $nums[0] > 0$，则此时可以知道需要将 $nums[0\cdots{k-1}$ 依次减去 $nums[0]$ 这样才能保证 $nums[0] = 0$，如果 $nums[0\cdots{k-1}$ 中所有的元素减去 $nums[0]$ 之后存在元素小于 $0$ 时，此时该数组一定不能全部变为 $0$，接着我们再从 $nums[1]$ 开始计算起；
  • 依次遍历上述操作，直到 $nums[n - k]$ 为止，因为此时 $nums[n - k + 1]$ 开始往后无法满足连续的 $k$ 个元素了。
  1. 优先可以考虑线段树，思路就比较简单了，从前往后遍历数组的每个元素，如果当前元素 $nums[i]$：
  • 如果 $nums[i] = 0$ 则跳过，遍历下一个元素；
  • 如果 $nums[i] < 0$ 则数组不合法无法将其变为 $0$；
  • 如果 $nums[i] > 0$ 则将数组 $nums[i \cdots {i + k -1}]$ 全部减去 $nums[i]$，利用线段树的懒标记实现即可；
  1. 线段树的写法比较复杂，我们可以利用差分数组的，边计算边更新，计算当前 $nums[i]$ 的处的值为 $x$分为三种情况讨论:
  • $x = 0$， 此时符合要求；
  • $x < 0$，此时数组不合法，直接返回 $false$；
  • $x > 0$：
    • 如果 $i \le n - k$，边数当前元素还可进行减法操作更新，此时我们记录差分结束的位置为 $i + k$，在位置 $i+k$ 处更新；
    • 如果 $i > n - k$，边数当前元素不可再进行减法操作更新，此时我们直接判定该数组为非法，返回 $false$；
  1. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    bool checkArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> cnt(n + k + 1);
        int curr = 0;
        for (int i = 0; i < n; i++) {
            curr += cnt[i];
            int x = curr + nums[i];
            if (x < 0) return false;
            if (x > 0 && i > n - k) return false;
            cnt[i + k] += x;
            curr -= x;
        }
        return true;
    }
};

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode biweekly contes 108 leetcode weekly contes 354 →

扫描二维码，分享此文章