Leetcode 第 141 场双周赛题解

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 = 10³ 是 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{// 求从最低位开始的连续 1int p = 0;while (nums[i] >> p & 0x1)p++;// 把连续 1 的最后一位变成 0ans[i] = nums[i] ^ (1 << (p - 1));}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n * logX)，其中 n 是数组 nums 的长度，X = 10⁹ 是 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 种节目，答案乘以 y^j 即可。

代码

/** @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)。