Leetcode---370周赛

题目列表

2923. 找到冠军 I

2924. 找到冠军 II 

2925. 在树上执行操作以后得到的最大分数 

2926. 平衡子序列的最大和

一、找到冠军I 

 

第一题模拟题,简单来说是看每一行(列)是否全是1,当然不包括自己比自己强的情况,需要特判

代码如下

class Solution {
public:int findChampion(vector<vector<int>>& grid) {int n=grid.size();for(int i=0;i<n;i++){int j;for(j=0;j<n;j++){if(i!=j&&grid[i][j]==0){break;}}if(j==n)return i;}return -1;}
};

二、找到冠军II

这题和上题相似,但是所给的数据内容不同。只要看图中是否只有一个结点的入度为0就行

代码如下

class Solution {
public:int findChampion(int n, vector<vector<int>>& edges) {vector<int>deg(n);for(auto&e:edges){int y=e[1];deg[y]++;}int ans=-1;for(int i=0;i<n;i++){if(!deg[i]){if(ans!=-1)return -1;ans=i;}}return ans;}
};

三、在树上执行操作以后得到的最大分数

 

这题的题目意思是让这棵树的每条路径和都>0,同时让自己获得的分数最大

如果正着思考,我们就要考虑选哪些点,使得我们获得的分数最大,同时保持树的健康,这样思考无论是从上往下走,还是从上往下走,我们都要去考虑遍历到的结点的上下两边的情况,比较麻烦

那么正难则反,如果我们逆着思考,即考虑选哪些结点留在树上,那么我们就可以边遍历,边找最小值,然后用 总价值 减去 留在书上的最小值 得到答案

代码如下

class Solution {typedef long long LL;
public:long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {int n=values.size();vector<vector<int>>g(n);for(auto&e:edges){int x=e[0],y=e[1];g[x].push_back(y);g[y].push_back(x);}//该dfs函数用来计算一棵树的每条路径上的最小值之和function<LL(int,int)>dfs=[&](int x,int fa)->LL{LL res=0;for(int y:g[x]){if(y!=fa){res+=dfs(y,x);}}return res==0?values[x]:min((LL)values[x],res);//如果res=0说明是叶子节点,直接返回结点值};LL s=accumulate(values.begin(),values.end(),0LL);return s-dfs(0,-1);}
};

四、平衡子序列的最大和

正常来说,求子序列的最大元素和,用动态规划就行,这题有点特殊,需要优化时间复杂度,我们先来看看正常的动规的写法

思路:将题目给的不等式移项,得到num[ i ] - i >= nums[ j ] - j,这样我们就将两个相互影响的值,变成了只和自己有关的nums[i]-i,我们用数组b存放nums[i] - i

动规:

dp数组含义:dp[i]表示以i为结尾的最大元素和

递推公式:dp[i]=max(dp[j],0)+nums[i]        条件  j<i && b[j]<=b[i]

初始化具体在代码,答案为max(dp[i])

class Solution {
public:typedef long long LL;long long maxBalancedSubsequenceSum(vector<int>& nums) {int n=nums.size();LL ans=INT_MIN;vector<LL>dp(nums.begin(),nums.end());for(int i=0;i<n;i++){for(int j=i-1;j>=0;j--){if(nums[i]-i>=nums[j]-j)dp[i]=max(dp[j]+nums[i],dp[i]);}ans=max(dp[i],ans);}return ans;}
};

上面代码的时间复杂度是O(n^2),数据范围太大,过不了,那么如何优化时间复杂度?

上面代码最浪费时间的是 dp[i]=max(dp[j])+nums[i] 这行代码,即查找最大值速度慢了,那么我们怎么才能提高查找的速度?这里就要引入一个数据结构---树状数组,它其实和线段树相似,是线段树的"子集"。

如果没听过的,可以去了解一下,这里不具体讲它的原理

(这里推荐一个视频,讲得很简洁明了:五分钟丝滑动画讲解 | 树状数组_哔哩哔哩_bilibili )

树状数组适合维护前缀和/前缀最大值+单点更新这类题目,更新和查询的时间复杂度均为O(logn)

而求 max(dp[j]) 不就是维护前缀最大值吗?每当计算出一个dp[i],就去更新树状数组,简直完美

现在还有一点需要注意:我们怎么样去将b[i]和树状数组的下标映射起来,这里又有一个知识点:离散化【复制+排序+去重】具体看代码(这个就是几行代码的事,很简单的)

(这里有人可能会对将b[i]和树状数组的下标映射这点感到疑惑,因为我们上面分析的是对dp数组的前缀最大值进行维护才对,解释一下:我们的递推公式有两个条件,j<i && b[j]<=b[i],我们是从左往右遍历的,所以更新到树状数组中的值全部满足j<i的情况,即我们只要考虑b[j]<=b[i]这个条件就行,那么我们对b数组排序之后,映射到树状数组的下标后,自然就满足这个条件了,我们只要在比b[i]小的b[j]元素对应的dp[i]中求最大值就行,即求前缀最大值)

代码如下

typedef long long LL;
class BIT{    vector<LL>bit;
public:BIT(int n):bit(n,LLONG_MIN){}void updata(int i,LL data){while(i<bit.size()){bit[i]=max(bit[i],data);i+=(i&-i);}}LL pre_max(int i){LL res=LLONG_MIN;while(i>0){res=max(res,bit[i]);i&=(i-1);}return res;}
};
class Solution {
public:long long maxBalancedSubsequenceSum(vector<int>& nums) {int n=nums.size();vector<int>b(n);//离散化//1.复制for(int i=0;i<n;i++)b[i]=nums[i]-i;//2.排序sort(b.begin(),b.end());//3.去重b.erase(unique(b.begin(),b.end()),b.end());LL ans=LLONG_MIN;BIT tree(n+1);for(int i=0;i<n;i++){int j=lower_bound(b.begin(),b.end(),nums[i]-i)-b.begin()+1;//计算下标LL data=max(0LL,tree.pre_max(j))+nums[i];tree.updata(j,data);ans=max(ans,data);}return ans;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

xdcms漏洞合集-漏洞复现

目录 xdcms v3.0.1漏洞 环境搭建 代码审计 目录总览 配置文件总览 登陆处sql注入 漏洞分析 漏洞复现 注册处sql注入漏洞 漏洞分析 漏洞复现 getshell 任意文件删除 xdcms订餐网站管理系统v1.0漏洞 简介 环境搭建 全局变量的覆盖 漏洞分析 漏洞复现 后台任意…

Android平台上执行C/C++可执行程序,linux系统编程开发,NDK开发前奏。

Android平台上执行C/C可执行程序&#xff0c;linux系统编程开发&#xff0c;NDK开发前奏准备。 1.下载NDK&#xff0c;搭建NDK开发环境 下载地址 https://developer.android.com/ndk/downloads 下载过程中点击下面箭头的地方&#xff0c;点击鼠标右键&#xff0c;复制好下载…

分享vmware和Oracle VM VirtualBox虚拟机的区别,简述哪一个更适合我?

VMware和Oracle VM VirtualBox虚拟机的区别主要体现在以下几个方面&#xff1a; 首先两种软件的安装使用教程如下&#xff1a; 1&#xff1a;VMware ESXI 安装使用教程 2&#xff1a;Oracle VM VirtualBox安装使用教程 商业模式&#xff1a;VMware是一家商业公司&#xff0c;而…

ubuntu 安装redis详细教程

下载redis安装包 链接如下&#xff1a; http://redis.io/download 本例版本为&#xff1a;redis-7.2.3.tar.gz 下载安装包到目录/opt下&#xff0c;路径可修改&#xff0c;本例为/opt wget https://github.com/redis/redis/archive/7.2.3.tar.gz 解压安装包&#xff0c;并…

整理笔记——稳压直流电路知识

一、稳压直流电路的基本构成 稳压直流电路就是把生活中常用的220V交流电转换成稳压直流电。如生活中常见的手机充电器就是一个稳压直流电路。其主要功能是提供持续稳定且满足要求的电压。 直流稳压电路由一下几个模块组成&#xff1a; 下面具体分析下各个模块的功能。…

个人前端编程技巧总结

目录 1. 让界面位于当前屏幕的中心&#xff08;屏幕中心&#xff09;css代码示例 2. 界面透明但是内部元素不透明&#xff08;毛玻璃&#xff09;css代码示例 3. 将当前界面的参数传递到跳转的目标页面&#xff08;携参跳转&#xff09;js代码 1. 让界面位于当前屏幕的中心&…

API接口自动化测试

本节介绍&#xff0c;使用python实现接口自动化实现。 思路&#xff1a;讲接口数据存放在excel文档中&#xff0c;读取excel数据&#xff0c;将每一行数据存放在一个个列表当中。然后获取URL,header,请求体等数据&#xff0c;进行请求发送。 结构如下 excel文档内容如下&#x…

Python的版本如何查询?

要查询Python的版本&#xff0c;可以使用以下方法之一&#xff1a; 1.在命令行中使用python --version命令。这会显示安装在计算机上的Python解释器的版本号。 # Author : 小红牛 # 微信公众号&#xff1a;wdPython2.在Python脚本中使用import sys语句&#xff0c;然后打印sy…

Django(二、静态文件的配置、链接数据库MySQL)

文章目录 一、静态文件及相关配置1.以登录功能为例2.静态文件3.资源访问4.静态文件资源访问如何解决&#xff1f; 二、静态文件相关配置1. 如何配置静态文件配置&#xff1f;2.接口前缀3. 接口前缀动态匹配4. form表单请求方法补充form表单要注意的点 三、request对象方法reque…

【服务发现与配置】Consul特性及搭建

文章目录 一、前言二、概念2.1、什么是Consul&#xff1f;2.2、Consul具有哪些特点?2.3、Consul 架构图2.4、Consul的使用场景 三、安装3.1. 下载3.2. 解压3.3. 拷贝到usr目录下3.4. 查看 安装是否成功3.5. 启动 四、Consul 开机自启动4.1. 路径/usr/lib/systemd/system/&…

前端工程化(vue2)

一、环境准备 1.依赖环境&#xff1a;NodeJS 官网&#xff1a;Node.js 2.脚手架&#xff1a;Vue-cli 参考网址&#xff1a;安装 | Vue CLI 介绍&#xff1a;Vue-cli用于快速的生成一个Vue的项目模板。主要功能有&#xff1a;统一的目录结构&#xff0c;本地调试&#xff0…

电脑msvcp110.dll丢失怎么办,msvcp110.dll缺失的详细修复步骤

在现代科技发展的时代&#xff0c;电脑已经成为我们生活和工作中不可或缺的工具。然而&#xff0c;由于各种原因&#xff0c;电脑可能会出现一些问题&#xff0c;其中之一就是msvcp110.dll文件丢失。这个问题可能会导致一些应用程序无法正常运行&#xff0c;给我们的生活和工作…

muduo源码剖析之TcpClient客户端类

简介 muduo用TcpClient发起连接&#xff0c;TcpClient有一个Connector连接器&#xff0c;TCPClient使用Conneccor发起连接, 连接建立成功后, 用socket创建TcpConnection来管理连接, 每个TcpClient class只管理一个TcpConnecction&#xff0c;连接建立成功后设置相应的回调函数…

虚拟机复制后,无法ping通问题解决

虚拟机复制后&#xff0c;无法ping通问题解决 可能出现的现象 ssh工具连接不上虚拟机&#xff1b;虚拟机ping不通外网或者ping不通内网其它虚拟机&#xff1b; 原因 原虚拟机和新复制出来的虚拟机的ip地址重复&#xff1b;原虚拟机和新复制出来的虚拟机的MAC地址重复&#…

基于SSM的建筑装修图纸管理平台

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

【Hugging Face】如何下载模型文件

参考文章&#xff1a; 1、mac安装Homebrew - 知乎 2、 ssh连接 git lfs install git clone githf.co:bert-base-uncased -- 安装Homebrew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" -- 配置文件生效 source /Use…

本地数据库迁移到云端服务器

工具迁移xtrabackup 创建云服务器——通过云服务器提供的公网地址远程连接XShell——利用迁移工具将数据库从本地迁移到云服务器 &#xff08;1&#xff09;创建云服务器 &#xff08;2&#xff09;远程连接XShell &#xff08;3&#xff09;yum安装mysql &#xff08;4&…

多语言翻译软件 Mate Translate mac中文版特色功能

Mate Translate for Mac是一款多语言翻译软件&#xff0c;Mate Translate mac可以帮你翻译超过100种语言的单词和短语&#xff0c;使用文本到语音转换&#xff0c;并浏览历史上已经完成的翻译。你还可以使用Control S在弹出窗口中快速交换语言。 Mate Translate Mac版特色功能…

1、C语言面向对象引入类和对象的概念

什么是类和对象 类 类是用户自定义的一种数据类型&#xff0c;也称类类型——C语言中的结构体 对象 类的一种具象 代码测试 #include <stdio.h>//类 struct Animal{ char name[12];//成员属性 int age; char sex; void (*peat)();//成员方法 void (*pbeat)(); };void…

latex加密符号怎么打|同态加密|Paillier

最近在写论文的时候遇到了一点阻碍&#xff0c;因为论文中需要用到paillier加密算法&#xff0c;想用一个公式表达加密的过程&#xff0c;但是不知道怎么打加密符号。 加密符号如下所示&#xff1a; 其中a是被加密的数字 $[\![a]\!] $ 公式&#xff1a; \begin{equation} …