且听疯吟

leetcode biweekly contest 127

2024-04-12

leetcode biweekly contest 127

放水的一周，开心的一周周赛。

3095. 或值至少 K 的最短子数组 I

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入：nums = [1,2,3], k = 2

输出：1

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入：nums = [2,1,8], k = 10

输出：3

解释：

子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：

输入：nums = [1,2], k = 0

输出：1

解释：

子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

提示：

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 50
  • 0 <= k < 64

地址

https://leetcode.cn/contest/biweekly-contest-127/problems/shortest-subarray-with-or-at-least-k-i/

题意

模拟

思路

  1. 直接枚举所有的子数组即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        res = inf
        for i in range(len(nums)):
            cur = 0
            for j in range(i, len(nums)):
                cur |= nums[j]
                if cur >= k and j - i + 1 < res:
                    res = j - i + 1
                    break
        return res if res != inf else -1
impl Solution {
    pub fn minimum_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
        let mut res = i32::MAX;
        let mut cur = 0;
        let len_nums = nums.len();


        for i in 0..len_nums {
            cur = 0;
            for j in i..len_nums {
                cur |= nums[j]; 
                if cur >= k && ((j - i + 1) as i32) < res {
                    res = (j - i + 1) as i32;
                    break;
                }
            }
        }
        if res == i32::MAX {
            -1 
        } else {
            res 
        }
    }
}

3096. 得到更多分数的最少关卡数目

给你一个长度为 n 的二进制数组 possible 。

莉叩酱和冬坂五百里正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式。一个玩家通过一个简单模式的关卡可以获得 1 分，通过困难模式的关卡将失去 1 分。

游戏的一开始，莉叩酱将从第 0 级开始 按顺序 完成一些关卡，然后冬坂五百里会完成剩下的所有关卡。

假设两名玩家都采取最优策略，目的是 最大化 自己的得分，莉叩酱想知道自己 最少 需要完成多少个关卡，才能获得比冬坂五百里更多的分数。

请你返回莉叩酱获得比冬坂五百里更多的分数所需要完成的 最少 关卡数目，如果 无法 达成，那么返回 -1 。

注意，每个玩家都至少需要完成 1 个关卡。

示例 1：

输入：possible = [1,0,1,0]

输出：1

解释：

我们来看一下莉叩酱可以完成的关卡数目：

  • 如果莉叩酱只完成关卡 0 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 分，冬坂五百里获得 -1 + 1 - 1 = -1 分。
  • 如果莉叩酱完成到关卡 1 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 - 1 = 0 分，冬坂五百里获得 1 - 1 = 0 分。
  • 如果莉叩酱完成到关卡 2 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 - 1 + 1 = 1 分，冬坂五百里获得 -1 分。

莉叩酱需要完成至少一个关卡获得更多的分数。

示例 2：

输入：possible = [1,1,1,1,1]

输出：3

解释：

我们来看一下莉叩酱可以完成的关卡数目：

  • 如果莉叩酱只完成关卡 0 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 1 分，冬坂五百里获得 4 分。
  • 如果莉叩酱完成到关卡 1 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 2 分，冬坂五百里获得 3 分。
  • 如果莉叩酱完成到关卡 2 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 3 分，冬坂五百里获得 2 分。
  • 如果莉叩酱完成到关卡 3 ，冬坂五百里完成剩下的所有关卡，那么莉叩酱获得 4 分，冬坂五百里获得 1 分。

莉叩酱需要完成至少三个关卡获得更多的分数。

示例 3：

输入：possible = [0,0]

输出：-1

解释：

两名玩家只能各完成 1 个关卡，莉叩酱完成关卡 0 得到 -1 分，冬坂五百里完成关卡 1 得到 -1 分。两名玩家得分相同，所以莉叩酱无法得到更多分数。

提示：

  • 2 <= n == possible.length <= 105
  • possible[i] 要么是 0 要么是 1 。

地址

https://leetcode.cn/problems/minimum-levels-to-gain-more-points/description/

题意

贪心

思路

  1. 由于游戏每次必须通关上一个环节才能进行下一个环节，因此直接统计当前游戏的得分 $cur$ 使得剩余的游戏得分小于 $cur$ 就返回。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def minimumLevels(self, possible: List[int]) -> int:
        tot = sum(1 if p == 1 else -1 for p in possible)
        cur = 0
        for i in range(0, len(possible) - 1):
            cur += 1 if possible[i] == 1 else -1
            if cur > tot - cur:
                return i + 1
        return -1
impl Solution {
    pub fn minimum_levels(possible: Vec<i32>) -> i32 {
        let mut tot = 0;
        for &p in possible.iter() {
            tot += if p == 1 {1} else {-1};
        }
        let mut cur = 0;
        for i in 0..possible.len() - 1 {
            cur += if possible[i] == 1 {1} else {-1};
            if cur > tot - cur {
                return (i + 1) as i32;
            }
        }
        -1
    }
}

3097. 或值至少为 K 的最短子数组 II

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入：nums = [1,2,3], k = 2

输出：1

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入：nums = [2,1,8], k = 10

输出：3

解释：

子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：

输入：nums = [1,2], k = 0

输出：1

解释：

子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

提示：

  • 1 <= nums.length <= 2 * 105
  • 0 <= nums[i] <= 109
  • 0 <= k <= 109

地址

https://leetcode.cn/contest/biweekly-contest-127/problems/shortest-subarray-with-or-at-least-k-ii/

题意

二分查找，滑动窗口

思路

  1. 典型的滑动窗口，对于当前索引 $i$ ，我们选择合适的窗口使得 $[j,i]$ 之间的子数组或值刚好大于等于 $k$ 即可，我们检测当前窗口的值 $cur$，如果当前的值大于等于 $k$ 则缩小左边的窗口，直到窗口内的或者刚好小于 $k$ 则终止，此时合适的最小的子数组的长度应该为 $i - j + 2$；
  2. 复杂度分析：
  • 时间复杂度：$O(n)$, $n$ 表示给定数组的长度；
  • 空间复杂度：$O(\log U)$;

代码

class Solution:
    def minimumSubarrayLength(self, nums: List[int], target: int) -> int:
        if target == 0:
            return 1
        
        res = inf
        cnt = [0] * 32
        cur = 0
        j = 0
        for i, x in enumerate(nums):
            for k in range(32):
                if (x & (1 << k)) != 0:
                    cnt[k] += 1
                if cnt[k] > 0:
                    cur |= 1 << k
                    
            if cur >= target:
                while j <= i and cur >= target:
                    for k in range(32):
                        if (nums[j] & (1 << k)) != 0:
                            cnt[k] -= 1
                            if cnt[k] == 0:
                                cur &= ~(1 << k)
                    j += 1
                j -= 1
                res = min(res, i - j + 1)
                for k in range(32):
                    if (nums[j] & (1 << k)) != 0:
                        cnt[k] += 1          
                        
        return res if res != inf else -1
impl Solution {
    pub fn minimum_subarray_length(nums: Vec<i32>, target: i32) -> i32 {
        if target == 0 {
            return 1;
        }
        
        let mut res = nums.len() + 1;
        let mut cnt = vec![0; 32];
        let mut cur = 0;
        let mut j = 0;
        for i in 0..nums.len() {
            for k in 0..32 {
                if (nums[i] & (1 << k)) != 0 {
                    cnt[k] += 1;
                }
                if cnt[k] > 0 {
                    cur |= 1 << k;
                }
            }
            
            if cur >= target {
                while j <= i && cur >= target {
                    for k in 0..32 {
                        if (nums[j] & (1 << k)) != 0 {
                            cnt[k] -= 1;
                            if cnt[k] == 0 {
                                cur &= !(1 << k);
                            }
                        }
                    }
                    j += 1
                }
                j -= 1;
                res = res.min(i - j + 1);
                for k in 0..32 {
                    if (nums[j] & (1 << k)) != 0 {
                        cnt[k] += 1;
                    }
                }
            }
        }

        if res > nums.len() {-1} else {res as i32}
    }
}

3098. 求出所有子序列的能量和

给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。

一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。

请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。

由于答案可能会很大，将答案对 109 + 7 取余 后返回。

示例 1：

输入：nums = [1,2,3,4], k = 3

输出：4

解释：

nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。

示例 2：

输入：nums = [2,2], k = 2

输出：0

解释：

nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。

示例 3：

输入：nums = [4,3,-1], k = 2

输出：10

解释：

nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。

提示：

  • 2 <= n == nums.length <= 50
  • -108 <= nums[i] <= 108
  • 2 <= k <= n

地址

https://leetcode.cn/contest/biweekly-contest-127/problems/find-the-sum-of-subsequence-powers/

题意

动态规划

思路

  1. 典型的动态规划题目，细节处理较多，写对不容易，非常经典的题目，确实佩服比赛中的某些人的手速场。赛后补充题目。题目的关键提示：假设现有子数组从小到大排序为 $[a_0,a_1,a_2,\cdots,a_{k-1}]$，那么数组中任意两个元素的绝对值的最小值一定为 $a_{i+1}-a_i$，即相邻两个元素的最小值，此时假设已知最小值 $x$，此时我们只需要保障任意两个相邻元素之间的差大于等于 $x$ 即可，此时如何我们枚举元素中任意两个元素作为最小值 即 $(x = nums[j] - nums[i]，i < j$，此时我们还需要在数组中找到 $k - 2$ 个元素才能构成长度为 $k$ 的数组，此时假设在 $i$ 的左侧找到 $m$ 个元素，则同时还需要再 $j$ 的右侧找到 $k-2-m$ 个元素即可，
    • 此时设 $f[t][l], g[t][l]$，$f[l][t]$ 表示在 $l，l < i$ 处找到满足要求的长度为 $t$ 的子数组的数目，$g[l][t]$ 表示在 $r,r>j$ 处找到长度为 $t$ 的子数组的数目, 则此时可以知道在 $i$ 的左侧可以找到长度为 $t$ 且相邻元素差值大于 $x$ 的子数目的数目为 $cntl[t] = \sum_{l=0}^{i-1}f[t][l]$,则此时可以知道在 $j$ 的右侧可以找到长度为 $t$ 且相邻元素差值大于 $x$ 的子数目的数目为 $cntr[t] = \sum_{l=0}^{i-1}g[t][l]$, 此时可以知道以 $i,j$ 为最小值的可以构成的子数组的总数目即为 $\sum_{t=0}^{k-2}cntl[t] \times cntr[k-2-t]$;
    • 我们分别枚举求出返回即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n^5)$，其中 $n$ 表示给数组的长度，可以用二分查找进一步优化为 $O(n^4\log n)$。
  • 空间复杂度：$O(n^2)$，其中 $n$ 表示给数组的长度。

代码

class Solution {
public:
    int sumOfPowers(vector<int>& nums, int m) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long mod = 1e9 + 7;
        long long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                vector<vector<long long>> f(n + 1, vector<long long>(n));
                vector<vector<long long>> g(n + 1, vector<long long>(n));
                int x = nums[j] - nums[i];
                /* left */
                for (int k = i - 1; k >= 0; k--) {
                    if (nums[i] - nums[k] > x) {
                        f[1][k] = 1;
                        for (int t = 2; t <= n; t++) {
                            for (int l = k - 1; l >= 0; l--) {
                                if (nums[k] - nums[l] > x) {
                                   f[t][l] = (f[t - 1][k] + f[t][l]) % mod;
                                }
                            }
                        }
                    }
                }
                /* right */
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] - nums[j] >= x) {
                        g[1][k] = 1;
                        for (int t = 2; t <= n; t++) {
                            for (int l = k + 1; l < n; l++) {
                                if (nums[l] - nums[k] >= x) {
                                    g[t][l] = (g[t][l] + g[t - 1][k]) % mod;
                                }
                            }
                        }
                    }
                }
                
                vector<long long> pre(n + 1), suf(n + 1);
                pre[0] = 1;
                suf[0] = 1;
                for (int k = 1; k <= n; k++) {
                    for (int l = 0; l < i; l++) {
                        pre[k] = (f[k][l] + pre[k]) % mod;
                    }
                    for (int l = j + 1; l < n; l++) {
                        suf[k] = (g[k][l] + suf[k]) % mod;
                    }
                }
                for (int k = 0; k <= m - 2; k++) {
                    res = (res + (long long) x * pre[k] * suf[m - 2 - k] % mod)% mod;
                }
            }
        }
        
        return res;
        
    }
};

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

Tags: 题解 力扣周赛赛
← leetcode weekly contest 390 leetcode contest 391 →

扫描二维码，分享此文章