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
            {
                // 求从最低位开始的连续 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 = 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)。