首页 > 其他分享 >Leetcode 第 126 场双周赛题解

Leetcode 第 126 场双周赛题解

时间:2024-03-29 10:02:56浏览次数:23  
标签:lc nums int 题解 复杂度 ids 双周 Leetcode dp

Leetcode 第 126 场双周赛题解

Leetcode 第 126 场双周赛题解

题目1:3079. 求出加密整数的和

思路

代码

/*
 * @lc app=leetcode.cn id=3079 lang=cpp
 *
 * [3079] 求出加密整数的和
 */

// @lc code=start
class Solution
{
public:
    int sumOfEncryptedInt(vector<int> &nums)
    {
        int sum = 0;
        for (int &num : nums)
            sum += encrypt(num);
        return sum;
    }
    // 加密函数
    int encrypt(int x)
    {
        string s = to_string(x);
        int maxDigit = 0;
        for (char &c : s)
            maxDigit = max(maxDigit, c - '0');
        int res = 0;
        for (int i = 0; i < s.length(); i++)
        {
            res *= 10;
            res += maxDigit;
        }
        return res;
    }
};
// @lc code=end

复杂度分析

时间复杂度:O(n*m),其中 n 是数组 nums 的长度,m 是每个元素的位数。

空间复杂度:O(1)。

题目2:3080. 执行操作标记数组中的元素

思路

由于要按照元素从小到大标记,但又不能直接对数组排序(因为有对特定 index 的标记),我们可以创建一个 ids 数组,其中 ids[i]=i,然后对该数组按照 nums[ids[i]] 从小到大排序。注意要使用稳定排序,因为相同元素值的下标需要按照下标从小到大排。也可以使用不稳定排序(如快速排序),但要对于相同元素值按照下标从小到大排序。

设 nums 的元素和为 s。对于每个询问,我们先将 s 减少 nums[index],然后将 nums[index] 置为 0,就相当于标记了这个数(因为题目保证数组元素都是正数)。然后依照 ids 找 k 个最小的没有被标记的数,将其标记,标记的同时维护 s。

代码

/*
 * @lc app=leetcode.cn id=3080 lang=cpp
 *
 * [3080] 执行操作标记数组中的元素
 */

// @lc code=start
class Solution
{
public:
    vector<long long>
    unmarkedSumArray(vector<int> &nums, vector<vector<int>> &queries)
    {
        int n = nums.size();
        long long s = accumulate(nums.begin(), nums.end(), 0LL);
        vector<int> ids(n);
        iota(ids.begin(), ids.end(), 0);
        // ranges::stable_sort(ids, [&](int i, int j) { return nums[i] < nums[j]; });
        sort(ids.begin(), ids.end(), [&](const int i, const int j)
             { if (nums[i] != nums[j]) return nums[i] < nums[j];
                else return i < j; });
        vector<long long> ans;
        int idx = 0;
        for (vector<int> &query : queries)
        {
            int index = query[0], k = query[1];
            s -= nums[index];
            nums[index] = 0; // 标记
            for (; idx < n && k; idx++)
            {
                index = ids[idx];
                if (nums[index] > 0) // 未被标记
                {
                    s -= nums[index];
                    nums[index] = 0; // 标记
                    k--;
                }
            }
            ans.push_back(s);
        }

        return ans;
    }
};
// @lc code=end

复杂度分析

时间复杂度:O(nlogn),其中 n 是数组 nums 的长度。

空间复杂度:O(n),其中 n 是数组 nums 的长度。

题目3:3081. 替换字符串中的问号使分数最小

思路

在这里插入图片描述

算法:

  1. 统计字母出现次数 freq,和字母组成 pair 加到一个最小堆中。
  2. 设问号出现了 cnt 次。循环 cnt 次,每次取出堆顶字母(它是目前出现次数最小的)加入一个字符串 tmp 中,然后把该字母的出现次数加一,重新入堆。
  3. 把 tmp 从小到大排序,因为题目要求字典序最小。
  4. 遍历 s 中的问号,按顺序填入 tmp 中的字母。

代码

/*
 * @lc app=leetcode.cn id=3081 lang=cpp
 *
 * [3081] 替换字符串中的问号使分数最小
 */

// @lc code=start

// 贪心 + 优先队列

class Solution
{
public:
    string minimizeStringValue(string s)
    {
        vector<int> freq(26, 0);
        for (char &c : s)
            if (c != '?')
                freq[c - 'a']++;
        priority_queue<pair<int, char>, vector<pair<int, char>>, greater<>> pq;
        for (int i = 0; i < 26; i++)
            pq.emplace(freq[i], i + 'a');

        int cnt = count(s.begin(), s.end(), '?');
        string tmp;
        for (int i = 0; i < cnt; i++)
        {
            auto [f, ch] = pq.top();
            pq.pop();
            tmp.push_back(ch);
            pq.emplace(f + 1, ch);
        }
        // 排序,因为要求字典序最小
        sort(tmp.begin(), tmp.end());
        for (int i = 0, j = 0; i < s.length(); i++)
            if (s[i] == '?')
                s[i] = tmp[j++];
        return s;
    }
};
// @lc code=end

复杂度分析

在这里插入图片描述

题目4:3082. 求出所有子序列的能量和

思路

在这里插入图片描述

二维 01 背包:

在这里插入图片描述

代码

/*
 * @lc app=leetcode.cn id=3082 lang=cpp
 *
 * [3082] 求出所有子序列的能量和
 */

// @lc code=start
class Solution
{
private:
    const int mod = 1e9 + 7;

public:
    int sumOfPower(vector<int> &nums, int k)
    {
        int n = nums.size();
        // dp[i][j][c]: 前 i 个物品,所选物品体积和是 j,选了 c 个物品的方案数
        int dp[n + 1][k + 1][n + 1];
        // 初始化
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= n; i++)
            dp[i][0][0] = 1;
        // 状态转移
        for (int i = 0; i < n; i++)
        {
            for (int j = k; j >= 0; j--)
            {
                for (int c = n; c > 0; c--)
                {
                    // 二维0/1背包
                    dp[i + 1][j][c] = dp[i][j][c]; // 不选
                    if (j >= nums[i])
                    {
                        // 选
                        dp[i + 1][j][c] = (dp[i + 1][j][c] + dp[i][j - nums[i]][c - 1]) % mod;
                    }
                }
            }
        }
        // 贡献法
        int ans = 0;
        long p = 1;
        for (int c = n; c >= 0; c--)
        {
            ans = (ans + dp[n][k][c] * p % mod) % mod;
            p = (p * 2) % mod;
        }
        return ans;
    }
};
// @lc code=end

复杂度分析

时间复杂度:O(n2k),其中 n 是数组 nums 的长度。

空间复杂度:O(n2k),其中 n 是数组 nums 的长度。

标签:lc,nums,int,题解,复杂度,ids,双周,Leetcode,dp
From: https://blog.csdn.net/ProgramNovice/article/details/137113535

相关文章

  • Leetcode 第 388 场周赛题解
    Leetcode第388场周赛题解Leetcode第388场周赛题解题目1:3074.重新分装苹果思路代码复杂度分析题目2:3075.幸福值最大化的选择方案思路代码复杂度分析题目3:3076.数组中的最短非公共子字符串思路代码复杂度分析题目4:3077.K个不相交子数组的最大能量值思路代码......
  • 大一下第四周ACM实验课题解
    7-1ACM宣传作者杜祥军单位青岛大学LB大神想组织集训队去学校各处宣传ACM,但是大神不想让队员们走太多路,因此想写代码计算一下,到各地宣传再回到博知401的最短路径总和是多少。已知:学校一共有n个宣传点,博知401是标号为1的点。剩下n-1个点每个点各派1位队员,询问每个队员到达宣......
  • 题解:CF1623B Game on Ranges
    题意理解(建议先自己把原题描述看一遍再来看我的理解)有一个集合,这个集合的元素是区间,一开始集合里只有一个元素就是\([1,n]\)的区间,对这个集合我们可以选择其中的一个元素(区间),然后在区间内选一个数d,以\([l,d-1]\)和\([d+1,r]\)这两个区间替换掉我们选择的这个区间(\(l\)和......
  • 【LeetCode】1607. 没有卖出的卖家
    题目表:Customer+---------------+---------+|ColumnName|Type|+---------------+---------+|customer_id|int||customer_name|varchar|+---------------+---------+customer_id是该表具有唯一值的列。该表的每行包含网上商城的每一位顾客的......
  • 【LeetCode】1873. 计算特殊奖金
    题目表:Employees+-------------+---------+|列名|类型|+-------------+---------+|employee_id|int||name|varchar||salary|int|+-------------+---------+employee_id是这个表的主键(具有唯一值的列)。此表的每一行......
  • 【Gradle测试】OOM问题解决方案
    文章目录概要问题场景问题复现解决方案相关资源概要分享开发过程中遇到的Gradle测试OOM问题的解决方案。问题场景当运行Gradle测试的时候,如果测试用例比较多,并且运行过程中创建的对象所占用的内存超过了Gradle测试默认的最大内存,则会发生OOM。问题复现由于本地......
  • P1037 [NOIP2002 普及组] 产生数 python 题解
    原题链接:产生数原理解释本题就是基本的dfs,对每一个数遍历深搜,得到他能变化的所有情况,最后相乘就是结果,网上都是c的解法,需要用到高精度,但是python可以处理大数,不需要。vis[]判断该数是否变换过,防止重复以n=123,k=2,变换列表x=[1,3],y=[3,4],即1->3,3->4:先遍历1:遍历......
  • CF1392H ZS Shuffles Cards 题解
    题目传送门前置知识概率DP解法设\(f_{i}\)表示有\(i\)张数字牌没进入\(S\),即\(S\)中只有\(n-i\)张数字牌时的期望轮数,有\(f_{i}=\frac{i}{i+m}f_{i-1}+\frac{m}{i+m}(f_{i}+1)\),解得\(f_{i}=f_{i-1}+\frac{m}{i}\),边界为\(f_{0}=1\)。由于每一张数字牌在joke......
  • 20240328每日一题题解
    20240328每日一题题解摘要本文对于2024年3月28日的每日一题进行了问题重述,并将问题拆解为五个步骤,分别进行了详细的讨论与求解,实现了整型与字符串类型的互相转换。并且还指出,在编写C++程序时,需要观察数据范围,在有必要时使用长整型(longlong)存储数据,以免出现整型溢出现象。关键......
  • Spring Boot 工程开发常见问题解决方案,日常开发全覆盖
    本文是SpringBoot开发的干货集中营,涵盖了日常开发中遇到的诸多问题,通篇着重讲解如何快速解决问题,部分重点问题会讲解原理,以及为什么要这样做。便于大家快速处理实践中经常遇到的小问题,既方便自己也方便他人,老鸟和新手皆适合,值得收藏......