Leetcode 第 141 场双周赛题解
Leetcode 第 141 场双周赛题解
- Leetcode 第 141 场双周赛题解
- 题目1：3314. 构造最小位运算数组 I
- 思路
- 代码
- 复杂度分析
- 题目2：3315. 构造最小位运算数组 II
- 思路
- 代码
- 复杂度分析
- 题目3：3316. 从原字符串里进行删除操作的最多次数
- 思路
- 代码
- 复杂度分析
- 题目4：3317. 安排活动的方案数
- 思路
- 代码
- 复杂度分析
Leetcode 第 141 场双周赛题解
题目1：3314. 构造最小位运算数组 I
思路
要让 ans[i] 满足：ans[i] OR (ans[i] + 1) == nums[i]，根据位运算的性质，可以知道 ans[i] < nums[i]。
从 0 开始枚举，如果有 x | (x + 1) == nums[i]，则 ans[i] = x，否则 ans[i] = -1。
代码
/*
* @lc app=leetcode.cn id=3314 lang=cpp
*
* [3314] 构造最小位运算数组 I
*/
// @lc code=start
class Solution
{
public:
vector<int> minBitwiseArray(vector<int> &nums)
{
int n = nums.size();
vector<int> ans(n, -1);
for (int i = 0; i < n; i++)
{
bool flag = false;
int x;
for (x = 0; x < nums[i]; x++)
{
if ((x | (x + 1)) == nums[i])
{
flag = true;
break;
}
}
ans[i] = flag ? x : -1;
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n * X)，其中 n 是数组 nums 的长度，X = 103 是 nums[i] 的取值范围。
空间复杂度：O(1)。
题目2：3315. 构造最小位运算数组 II
思路
可以发现，x ∣ (x+1) 的本质是把二进制最右边的 0 置为 1。
反过来，如果我们知道了 x ∣ (x+1) 的结果 101111，那么对应的 x 只能是这些：
- 100111。
- 101011。
- 101101。
- 101110。
因此我们找出 nums[i] 从最低位开始的连续 1，把连续 1 的最后一位变成 0，就是答案。
由于 x ∣ (x+1) 最低位一定是 1（因为 x 和 x+1 其中一定有一个奇数），所以如果 nums[i] 是偶数（质数中只有 2），那么无解，答案为 −1。
代码
/*
* @lc app=leetcode.cn id=3315 lang=cpp
*
* [3315] 构造最小位运算数组 II
*/
// @lc code=start
class Solution
{
public:
vector<int> minBitwiseArray(vector<int> &nums)
{
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
if (nums[i] == 2)
ans[i] = -1;
else
{
// 求从最低位开始的连续 1
int p = 0;
while (nums[i] >> p & 0x1)
p++;
// 把连续 1 的最后一位变成 0
ans[i] = nums[i] ^ (1 << (p - 1));
}
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n * logX)，其中 n 是数组 nums 的长度，X = 109 是 nums[i] 的取值范围。
空间复杂度：O(1)。
题目3：3316. 从原字符串里进行删除操作的最多次数
思路
定义 dp[i][j] 表示要使 pattern[0,…,j] 是 source[0,…,i] 的子序列，最多的删除次数。
分类讨论：
- 不选 source[i]，问题变成要使 pattern[0] 到 pattern[j] 是 source[0] 到 source[i−1] 的子序列，最多可以进行多少次删除操作，即 dp[i−1,j]。如果 i 在 targetIndices 中，那么删除次数加一。
- 如果 source[i]=pattern[j]，那么匹配（都选），问题变成要使 pattern[0] 到 pattern[j−1] 是 source[0] 到 source[i−1] 的子序列，最多可以进行多少次删除操作，即 dp[i−1,j−1]。
这两种情况取最大值。
代码
/*
* @lc app=leetcode.cn id=3316 lang=cpp
*
* [3316] 从原字符串里进行删除操作的最多次数
*/
// @lc code=start
class Solution
{
public:
int maxRemovals(string source, string pattern, vector<int> &targetIndices)
{
int n = source.length();
int m = pattern.length();
unordered_set<int> hashSet(targetIndices.begin(), targetIndices.end());
// dp[i][j] 表示要使 pattern[0,...,j] 是 source[0,...,i] 的子序列，最多的删除次数
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MIN));
// 初始化
dp[0][0] = 0;
for (int i = 0; i < n; i++)
{
int is_del = hashSet.count(i);
dp[i + 1][0] = dp[i][0] + is_del;
}
// 状态转移
for (int i = 0; i < n; i++)
for (int j = 0; j < min(i + 1, m); j++)
{
int is_del = hashSet.count(i);
dp[i + 1][j + 1] = dp[i][j + 1] + is_del;
if (source[i] == pattern[j])
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]);
}
return dp[n][m];
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n * m)，其中 n 为字符串 source 的长度，m 是字符串 pattern 的长度。
空间复杂度：O(n * m + t)，其中 n 为字符串 source 的长度，m 是字符串 pattern 的长度，t 是数组 targetIndices 的元素个数。
题目4：3317. 安排活动的方案数
思路
dp[i,j] 表示前 i 个人表演 j 个节目的方案数。转移有两种情况：
- 第 i 个人的节目在前面已经表演过了，那么有 j 个老节目可以选，因此 dp[i−1,j]×j。
- 第 i 个人要表演个新节目，那么有 (x−j+1) 个新节目可以选，因此 dp[i−1,j−1]×(x−j+1)
统计答案时，枚举一共表演了 j 种节目，答案乘以 yj 即可。
代码
/*
* @lc app=leetcode.cn id=3317 lang=cpp
*
* [3317] 安排活动的方案数
*/
// @lc code=start
class Solution
{
private:
const int MOD = 1e9 + 7;
public:
int numberOfWays(int n, int x, int y)
{
// dp[i][j] 表示前 i 个人表演 j 个节目的方案数
vector<vector<long long>> dp(n + 1, vector<long long>(x + 1, 0));
// 初始化
dp[0][0] = 1;
// 状态转移
for (int i = 1; i <= n; i++)
for (int j = 1; j <= x; j++)
{
// 第 i 个人的节目在前面已经表演过了,那么有 j 个老节目可以选
dp[i][j] = (dp[i][j] + dp[i - 1][j] * j) % MOD;
// 第 i 个人要表演个新节目，那么有 (x−j+1) 个新节目可以选
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * (x - j + 1)) % MOD;
}
long long ans = 0LL, mult = 1LL;
for (int j = 1; j <= x; j++)
{
mult = (mult * y) % MOD;
// 一共表演了 j 种节目，有 y^j 种打分方案
ans = (ans + dp[n][j] * mult) % MOD;
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n * x)。
空间复杂度：O(n * x)。