Leetcode 第 127 场双周赛题解
- Leetcode 第 127 场双周赛题解
- 题目1:3095. 或值至少 K 的最短子数组 I
- 思路
- 代码
- 复杂度分析
- 题目2:3096. 得到更多分数的最少关卡数目
- 思路
- 代码
- 复杂度分析
- 题目3:3097. 或值至少为 K 的最短子数组 II
- 思路
- 代码
- 复杂度分析
- 题目4:3098. 求出所有子序列的能量和
- 思路
- 代码
- 复杂度分析
Leetcode 第 127 场双周赛题解
题目1:3095. 或值至少 K 的最短子数组 I
思路
暴力。
代码
/*
* @lc app=leetcode.cn id=3095 lang=cpp
*
* [3095] 或值至少 K 的最短子数组 I
*/
// @lc code=start
class Solution
{
public:
int minimumSubarrayLength(vector<int> &nums, int k)
{
// 特判
if (*max_element(nums.begin(), nums.end()) >= k)
return 1;
int n = nums.size();
int minLen = INT_MAX;
for (int i = 0; i < n - 1; i++)
{
int res = 0;
for (int j = i; j < n; j++)
{
res |= nums[j];
if (res >= k)
{
minLen = min(minLen, j - i + 1);
break;
}
}
}
return minLen == INT_MAX ? -1 : minLen;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(n2),其中 n 是数组 nums 的长度。
空间复杂度:O(1)。
题目2:3096. 得到更多分数的最少关卡数目
思路
前缀和。
设 n = nums.size(),前缀和 preSum[i] 记录从第一关开始,到第 i 关的分数和。
如果 possible[i] = 1,该关的分为 1;如果 possible[i] = 0,该关的分为 -1。
构建好 preSum 数组后,遍历 0 < i < n:
莉叩酱的分数为 preSum[i] - preSum[0], 冬坂五百里的分数为 preSum[n] - preSum[i]。
如果当前莉叩酱的分数 > 冬坂五百里的分数,返回当前下标;遍历结束了还没找到,则返回 -1。
代码
/*
* @lc app=leetcode.cn id=3096 lang=cpp
*
* [3096] 得到更多分数的最少关卡数目
*/
// @lc code=start
class Solution
{
public:
int minimumLevels(vector<int> &possible)
{
int n = possible.size();
vector<int> preSum(n + 1, 0);
for (int i = 1; i <= n; i++)
{
int x = possible[i - 1] > 0 ? 1 : -1;
preSum[i] = preSum[i - 1] + x;
}
// 注意,每个玩家都至少需要完成 1 个关卡。
for (int i = 1; i < n; i++)
{
int score1 = preSum[i] - preSum[0];
int score2 = preSum[n] - preSum[i];
if (score1 > score2)
return i;
}
return -1;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(n),其中 n 是数组 nums 的长度。
题目3:3097. 或值至少为 K 的最短子数组 II
思路
用一个哈希表记录一个子数组的 or 值和取得该值子数组的左边界的最大值。
遍历数组 nums,设当前遍历的值为 nums[i]。
遍历哈希表的每一个键值对 [or_, left],求出新的与值 new_or = or_ | nums[i],更新键 new_or 的值:temp[new_or] = max(temp[new_or], left),取 left 的较大者。
最后,nums[i] 可以单独作为一个子数组,它的左边界是 i,所以哈希表还要插入 [nums[i], i]。
将这一轮遍历得到的新的哈希表赋值给老的哈希表,遍历当前哈希表的每一个键值对 [or_, left],如果 or_ >= k,更新答案 ans = min(ans, i - left + 1)。
代码
class Solution
{
public:
int minimumSubarrayLength(vector<int> &nums, int k)
{
int ans = INT_MAX;
unordered_map<int, int> d; // key 是右端点为 i 的子数组 OR, value 是该子数组左端点的最大值
for (int i = 0; i < nums.size(); i++)
{
unordered_map<int, int> temp;
for (auto &[or_, left] : d)
{
int new_or = or_ | nums[i];
temp[new_or] = max(temp[new_or], left);
}
temp[nums[i]] = i;
swap(d, temp);
for (auto &[or_, left] : d)
if (or_ >= k)
ans = min(ans, i - left + 1);
}
return ans != INT_MAX ? ans : -1;
}
};
复杂度分析
时间复杂度:O(nlogU),其中 n 为 nums 的长度,U=max(nums)。
空间复杂度:O(nlogU),其中 n 为 nums 的长度,U=max(nums)。
题目4:3098. 求出所有子序列的能量和
思路
排序 + 递归 + 记忆化搜索。
题解:https://www.bilibili.com/video/BV19t421g7Pd
代码
#
# @lc app=leetcode.cn id=3098 lang=python3
#
# [3098] 求出所有子序列的能量和
#
# @lc code=start
class Solution:
def sumOfPowers(self, nums: List[int], k: int) -> int:
MOD = 10 ** 9 + 7
nums.sort()
# i 是当前下标
# j 是还需要选多少个数
# pre 是上一个选的数
# min_diff 是目前选的数的能量(任意两数差的绝对值的最小值)
@cache
def dfs(i, j, pre, min_diff):
# 即使剩下的数全选,也不足 j 个
if j > i + 1:
return 0
if j == 0:
return min_diff
# 选
res1 = dfs(i - 1, j - 1, nums[i], min(min_diff, pre - nums[i]))
# 不选
res2 = dfs(i - 1, j, pre, min_diff)
return (res1 + res2) % MOD
return dfs(len(nums) - 1, k, inf, inf)
# @lc code=end
复杂度分析
时间复杂度:O(n4*k),其中 n 是数组 nums 的长度。
空间复杂度:O(n3*k),其中 n 是数组 nums 的长度。