当前位置: 首页 > article >正文

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)。


http://www.kler.cn/a/349583.html

相关文章:

  • Linux命令介绍:如何使用stat深入解析文件和文件系统状态
  • 江苏盐城中级职称申报条件及流程详解
  • ②PROFINET 转 EtherNet/IP, EtherCAT/Ethernet/IP/Profinet/ModbusTCP协议互转工业串口网关
  • python爬虫--某动漫信息采集
  • 2024软件测试面试题大全【含答案】
  • Vue3 响应式数据
  • vue-jsonp的使用和腾讯地图当前经纬度和位置详情的获取
  • 【Vue】扫盲(五)Vue 的生命周期与钩子函数详解
  • Java基础:面向对象编程3
  • LLM-生成器判别器的实现
  • Vue中计算属性computed—(详解计算属性vs方法Methods,包括案例+代码)
  • 如何使用Python爬虫处理JavaScript动态加载的内容?
  • JavaSE——集合8:Map接口
  • 数组合并与排序练习题
  • 管理者如何开展和布置工作?
  • 【Java 并发编程】单例模式
  • 牛的旅行——Floyd
  • 【K8S系列】Kubernetes 集群中的网络常见面试题
  • 【代码随想录Day43】动态规划Part11
  • Scala入门基础(10)高级函数