LeetCode---126双周赛

题目列表

3079. 求出加密整数的和

3080. 执行操作标记数组中的元素

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

3082. 求出所有子序列的能量和

一、求出加密整数的和

按照题目要求,直接模拟即可,代码如下

class Solution {
public:
    int sumOfEncryptedInt(vector<int>& nums) {
        int n=nums.size(),res=0;
        for(auto x:nums){
            int s = 0, mx = 0;
            while(x){
                mx=max(mx,x%10);
                s=s*10+1;
                x/=10;
            }
            res+=mx*s;
        }
        return res;
    }
};

二、执行操作标记数组中的元素

题目不难,依旧还是只需要模拟,但是代码量不少,要细心,思路如下:

对于每次查询的操作1:只要判断垓下标是否被标记,然后处理即可

对于每次查询的操作2:要把没有标记过的最小的k个数字标记,如果数字相同则下标小的先标记,很显然要排序(两个维度的排序---首先比较数值,其次比较下标),这里讲一个技巧:我们没必要将数值和下标打包在一起(即用pair)排序,我们可以直接对下标进行排序,具体看代码

如何表示一个数是否被标记?可以额外开一个数组,也可以直接在原数组上修改,将标记过的数记为-1

代码如下

class Solution {
public:
    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size();
        vector<long long> ans(m);
        vector<int>idx(n);
        long long s = 0;
        for(int i=0;i<n;i++) {
            idx[i]=i;
            s+=nums[i];
        }
        sort(idx.begin(),idx.end(),[&](int x,int y){
            return nums[x]!=nums[y]?nums[x]<nums[y]:x<y;
        });
        
        for(int i=0,j=0;i<m;i++){
            const auto& v = queries[i];
            int index = v[0], k = v[1];
            if(nums[index]>=0){
                s -= nums[index];
                nums[index] = -1;
            }
            while(k&&j<n){
                if(nums[idx[j]]<0){
                    j++;
                    continue;
                }
                s -= nums[idx[j]];
                nums[idx[j]]=-1;
                j++,k--;
            }
            ans[i]=s;
        }
        return ans;
    }
};

三、替换字符串中的问号使分数最小

这题是思维题:

首先我们要明白字母出现的顺序并不会影响它们对总分数的贡献(因为字母对分数的贡献仅仅只和该字母出现的次数有关,字母与其他字母之间是相互独立的),也就是说我们只要考虑每个 '?' 填哪个字母即可,根据cost的定义,我们优先考虑之前出现次数少的字母对 '?' 进行填充,当出现次数一样少时,我们优先考虑字典序小的字母,然后对选出的字母进行排序,最后按照 '?' 的位置进行替换即可。

代码如下

class Solution {
public:
    string minimizeStringValue(string s) {
        int n = s.size();
        string tmp;
        int cnt[26] = { 0 },c = 0;
        for(const auto& e:s){
            if(e!='?') cnt[e-'a']++;
            else c++;
        }
    
        auto cmp=[](const pair<int,int>& x,const pair<int,int>& y)->bool{
            return x.first!=y.first ? x.first > y.first : x.second > y.second;
        };
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp); //小堆
        for(int i=0;i<26;i++)
            pq.push({cnt[i],i});
        
        while(c--){
            auto [x,ch] = pq.top();
            pq.pop();
            pq.push({x+1,ch});
            tmp += 'a'+ch;
        }
        sort(tmp.begin(),tmp.end());
        for(int i=0,j=0;i<n;i++){
            if(s[i]=='?')
                s[i]=tmp[j++];
        }
        return s;
    }
};

四、求出所有子序列的能量和

这题找子序列中的子序列,看着很绕,其实就是找和为k的子序列能出现在多少个子序列中,即和为k的子序列做出的贡献,拿示例一举例:和为3的子序列有[1,2]和[3],其中[1,2]在2个子序列中出现,[3]在4个子序列中出现,所以答案为2+4=6。很显然每个和为3的子序列的贡献为2^(n-L),其中n为整个数组的长度,L为子序列的长度。

故答案的表达式为 sum(2^(n-L) * num_K_L) 1<=L<=n,num_K_L表示长为L,和为K的子序列个数

如何求长为L,和为K的子序列的个数?

这是一个背包问题,限制条件有两个:1、长为L  2、和为K

设f[i][L][c]表示前i个数中,长为L,和为c的子序列的个数

1、如果当前的数不在和为c的子序列中,则f[i][L][c]=f[i-1][L][c]

2、如果当前的数在和为c的子序列中,则f[i][L][c]=f[i-1][L-1][c-nums[i]]

所以f[i][L][c]=f[i-1][L][c]+f[i-1][L-1][c-nums[i-1]]

初始化:f[i][0][0]=1,因为长为0,和为0的子序列只能是空,只有一个

代码如下

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        int n=nums.size();
        const int MOD = 1e9+7;
        int f[n+1][n+1][k+1];
        memset(f,0,sizeof(f));
        //f[i][L][j] = f[i-1][L][j] + f[i-1][L-1][j-nums[i]]
        for(int i=0;i<=n;i++)
            f[i][0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=1;j<=k;j++){
                for(int L=1;L<=i+1;L++){
                    f[i+1][L][j] = (f[i][L][j] + (j>=nums[i]?f[i][L-1][j-nums[i]]:0))%MOD;
                }
            }
        }

        long long ans = 0, pow2 = 1;
        for(int i=n;i>0;i--){
            ans = (ans + f[n][i][k]*pow2)%MOD;
            pow2 = pow2*2%MOD;
        }
        return ans%MOD;
    }
};

// 优化空间
class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        int n=nums.size();
        const int MOD = 1e9+7;
        int f[n+1][k+1];
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=k;j>=nums[i];j--){
                for(int L=1+i;L>0;L--){
                    f[L][j] = (f[L][j] + f[L-1][j-nums[i]])%MOD;
                }
            }
        }

        long long ans = 0, pow2 = 1;
        for(int i=n;i>0;i--){
            ans = (ans + f[i][k]*pow2)%MOD;
            pow2 = pow2*2%MOD;
        }
        return ans%MOD;
    }
};

当然我们也可以根据题目直接定义状态:f[i][j]表示前i个数为数组的,元素和为k的能量值

1、如果nums[i]不在子序列和为k的序列中,那么它有选和不选两种可能,f[i+1][j]=f[i][j]*2

2、如果nums[i]在子序列和为k的序列中,那么它只能被选,f[i+1][j]=f[i][j-nums[i]]

举个例子[1,2,3],要求和为3,假设遍历到 i = 2 ,如果nums[i]=3不在我们想要的子序列中,那么它可以选,也可以不选,即f[i][j] * 2,如果nums[i]=3在我们想要的子序列中,那么它只能被选,即f[i][j-nums[i]]

所以状态转移方程为 f[i+1][j]=f[i][j] * 2+ f[i][j-nums[i]]

代码如下

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int MOD=1e9+7;
        int n=nums.size();
        vector<vector<long long>>f(n+1,vector<long long>(k+1));
        f[0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<=k;j++){
                f[i+1][j]=(f[i][j]*2+(j>=nums[i]?f[i][j-nums[i]]:0))%MOD;
            }
        }
        return f[n][k];
    }
};

//优化空间
class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int MOD=1e9+7;
        int n=nums.size();
        vector<long long>f(k+1);
        f[0]=1;
        for(int i=0;i<n;i++){
            for(int j=k;j>=0;j--){
                f[j]=(f[j]*2+(j>=nums[i]?f[j-nums[i]]:0))%MOD;
            }
        }
        return f[k];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/481807.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Oracle Data Guard常用命令

--查询数据库角色和保护模式 select database_role,switchover_status from v$database; --切换备库为主库&#xff08;切换后&#xff0c;主库为mount状态&#xff09; --TO PRIMARY alter database commit to switchover to primary; --SESSIONS ACTIVE alter database comm…

如何保障消息一定能发送到RabbitMQ?

我们知道&#xff0c;RabbitMQ的消息最终是存储在Queue上的&#xff0c;而在Queue之前还要经过Exchange&#xff0c;那么这个过程中就有两个地方可能导致消息丢失。第一个是Producer到Exchange的过程&#xff0c;第二个是Exchange到Queue的过程。 为了解决这个问题&#xff0c…

大学期末考试搜题软件?这4款足够解决问题 #知识分享#笔记#职场发展

当代大学生面临着繁重的学业压力和海量的知识点&#xff0c;如何高效地进行学习和搜题成了他们关注的焦点。幸运的是&#xff0c;随着科技的不断进步&#xff0c;我们有越来越多的日常搜题和学习软件可以帮助我们更好地应对这些挑战。在本文中&#xff0c;我将为大家介绍10款备…

皓学IT:WEB06_ EL表达式JSTL标签库

一、EL表达式 1.1.特点 是一个由java开发的工具包 用于从特定域对象中读取并写入到响应体开发任务&#xff0c;不能向域对象中写入。 EL工具包自动存在Tomcat的lib中&#xff08;el-api.jar&#xff09;&#xff0c;开发是可以直接使用&#xff0c;无需其他额外的包。 标准…

千万不要错过这9款能让你快速写作成长的宝藏软件…… #科技#学习方法#学习

很多小伙伴想要自己做自媒体&#xff0c;但是却不知道从何下手&#xff0c;今天我就和大家分享一波好用的一些自媒体工具。 1.红桃写作 这是一个微信公众号 面向专业写作领域的ai写作工具&#xff0c;写作助手包括&#xff0c;ai论文,ai开题报告、ai公文写作、ai商业计划书、…

每日五道java面试题之springboot篇(三)

目录&#xff1a; 第一题. Spring Boot 中的监视器是什么&#xff1f;第二题. 如何在 Spring Boot 中禁用 Actuator 端点安全性&#xff1f;第三题. 我们如何监视所有 Spring Boot 微服务&#xff1f;第四题. 什么是 WebSockets&#xff1f;第五题. 什么是 Spring Data ? 第一…

Qt教程 — 3.6 深入了解Qt 控件:Display Widgets部件(2)

目录 1 Display Widgets简介 2 如何使用Display Widgets部件 2.1 QTextBrowser组件-简单的文本浏览器 ​2.2 QGraphicsView组件-简单的图像浏览器 Display Widgets将分为两篇文章介绍 文章1&#xff08;Qt教程 — 3.5 深入了解Qt 控件&#xff1a;Display Widgets部件-CSDN…

使用POI以OLE对象的形式向excel中插入附件(pdf为例)

前言&#xff1a; 最近在使用easyExcel操作excel文件时&#xff0c;一直想找到一个方法可以往excel中填充附件&#xff0c;但是目前只发现POI可以插入附件&#xff0c;于是将方法记录如下&#xff1a; 实现&#xff1a; 这个方法主要是使用 Apache POI 的 HSSFWorkbook 类来…

带有GUI界面的电机故障诊断(MSCNN-BILSTM-ATTENTION模型,TensorFlow框架,有中文注释,带有六种结果可视化)

本次创作最主要是在MSCNN-BILSTM-ATTENTION模型&#xff08;可轻松替换为其它模型&#xff09;基础上&#xff0c;搭建GUI测试界面&#xff0c;方便对你想要测试的数据的进行测试&#xff0c;同时进行了全面的结果可视化&#xff1a;1.训练集和测试集的准确率曲线&#xff0c;2…

第28章 ansible的使用

第28章 ansible的使用 本章主要介绍在 RHEL8 中如何安装 ansible 及 ansible的基本使用。 ◆ ansible 是如何工作的 ◆ 在RHEL8 中安装ansible ◆ 编写 ansible.cfg 和清单文件 ◆ ansible 的基本用法 文章目录 第28章 ansible的使用28.1 安装ansible28.2 编写ansible.cfg和清…

v3-admin-vite 整合pont

需求 目前后端的Admin模板使用的是v3-admin-vite&#xff0c;需要整合pont接口&#xff0c;方便前后端统一一体化开发 安装PONT 按照官方的文档&#xff0c;将pont engine安装好&#xff0c;然后在项目根目录执行pont start。注意生成代码路径要修改一下&#xff0c;因为v3-a…

AI新工具(20240322) 免费试用Gemini Pro 1.5;先进的AI软件工程师Devika;人形机器人Apptronik给你打果汁

✨ 1: Gemini Pro 1.5 免费试用Gemini Pro 1.5 Gemini 1.5 Pro是Gemini系列模型的最新版本&#xff0c;是一种计算高效的多模态混合专家&#xff08;MoE&#xff09;模型。它能够从数百万个上下文Token中提取和推理细粒度信息&#xff0c;包括多个长文档和数小时的视频、音频…

Excel数字乱码怎么回事 Excel数字乱码怎么调回来

在日常工作中&#xff0c;Excel是我们最常使用的数据处理软件之一&#xff0c;它强大的功能使得数据处理变得既简单又高效。然而&#xff0c;用户在使用Excel时偶尔会遇到数字显示为乱码的问题&#xff0c;这不仅影响了数据的阅读&#xff0c;也大大降低了工作效率。那么&#…

Docker-Image

Docker Docker 镜像是什么为什么需要镜像镜像命令总览docker imagesdocker tagdocker pulldocker pushdocker rmidocker savedocker loaddocker image inspectdocker historydocker importdocker image prunedocker build Docker 镜像是什么 Docker image 本质上是一个 read-on…

一文全面了解 wxWidgets 程序国际化(i18n)处理

尽管应用程序的国际化&#xff08;简称i18n&#xff09;远不止是将文本消息翻译成另一种语言的消息——日期、时间和货币格式也需要更改&#xff0c;一些语言是从左到右书写&#xff0c;而另一些是从右到左书写&#xff0c;字符编码可能不同&#xff0c;以及许多其他可能需要更…

一文带你弄懂JVM与JAVA体系结构

文章目录 1.JVM 与 Java 体系结构1.1. 前言1.2. 一些参考书目1.3. Java 及 JVM 简介1.4. Java 发展的重大事件1.5. 虚拟机与 Java 虚拟机1.6. JVM 的整体结构1.7. Java 代码执行流程1.8. JVM 的架构模型1.9. JVM 的生命周期 1.JVM 与 Java 体系结构 1.1. 前言 作为 Java 工程…

NLP 笔记:Latent Dirichlet Allocation (介绍篇)

1 问题介绍 假设我们有一堆新闻&#xff0c;每个新闻都有≥1个主题 我们现在只知道新闻的内容&#xff0c;我们希望一个算法&#xff0c;帮我们把这些新闻分类成主题人类可以根据每个每个文章里面的单词判断主题&#xff0c;那计算机怎么做呢&#xff1f; ——>LDA(Latent D…

大小端是什么?怎么判断?(百度笔试题)

目录 一、前言二、什么是大小端&#xff1f;三、为什么有大小端之分呢&#xff1f;四、判断机器是大端还是小端--百度笔试题 一、前言 先看一段代码&#xff1a; #include<stdio.h> int main() {int n 0x11223344;return 0; }二、什么是大小端&#xff1f; 其实超过⼀…

【JavaSE】抽象类和接口

目录 前言 1. 抽象类 1.1 认识抽象类 1.2 抽象类的特征 1.3 抽象类的作用 2. 接口 2.1 接口的概念 2.2 接口的语法 2.3 接口的使用 2.4 接口的特性 2.5 接口的好处 2.6 接口之间的继承 结语 前言 今天我们来讲Java中的抽象类和接口&#xff0c;它们在面向对象中发…

前端应用开发实验:条件渲染和循环渲染

目录 实验目的相关知识点实验内容图片的隐藏和显示代码实现效果 电影票房排序代码实现效果 代办事项记录代码实现效果 实验目的 (1)熟练掌握v-on 指令的用法&#xff0c;学会使用v-on 指令监听DOM元素的事件&#xff0c;并通过该事件触发调用事件处理程序。 (2)掌握v-on指令修…