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

Leetcode---365周赛

题目列表

2873. 有序三元组中的最大值 I

2874. 有序三元组中的最大值 II

2875. 无限数组的最短子数组

2876. 有向图访问计数

 一、有序三元组中的最大值I

 看一眼该题的数据范围,直接三层for循环暴力枚举,时间复杂度O(n^3),代码如下

class Solution {
public:long long maximumTripletValue(vector<int>& nums) {long long ans=0;for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){for(int k=j+1;k<nums.size();k++){ans=max(ans,1LL*(nums[i]-nums[j])*nums[k]);}}}return ans;}
};

二、有序三元组的最大值II

题目同上一题,只有数据范围不同

同一个题,数据范围变大之后,再用暴力就会超时,我们要想想怎么优化时间复杂度 ?

这里有三种思路:

1.我们枚举i,看j,k怎么选?

2.我们枚举j,看i,k怎么选?

3.我们枚举k,看i,j怎么选?

假设我们选择方案一:枚举i(即先确定一个nums[ i ]),那么nums[ j ]和nums[ k ]要如何选?才能让三元组的值最大,显然nums[ j ]要选最小的,nums[ k ]选最大的,这样三元组值最大,但是还有一个条件j<k,这就很难办了, 因为我们不能确定要选择的最小值和最大值的位置关系,所以方案一不选

假设我们选择方案二:枚举j(即先确定一个nums[ j ]),那么nums[ i ]和nums[ k ]要如何选?才能让三元组的值最大,显然nums[ i ]选最大的,nums[ k ]也选最大的,这样三元组值最大,并且i<j<k,即我们选取的nums[ i ]和nums[ k ]是互不影响的,我们只要预处理出前i个元素的最大值,和后i个元素的最大值,就能在O(n)的时间复杂度内找到答案,代码如下

class Solution {
public:long long maximumTripletValue(vector<int>& nums) {int n=nums.size();long long ans=0;vector<int>pre(n+1),suf(n);pre[0]=0;for(int i=0;i<n;i++)pre[i+1]=max(pre[i],nums[i]);for(int i=n-1;i>=1;i--)suf[i-1]=max(suf[i],nums[i]);for(int j=0;j<n;j++)ans=max(ans,1LL*(pre[j]-nums[j])*suf[j]);return ans;}
};//当然这里的前缀最大值数组还可以优化掉
class Solution {
public:long long maximumTripletValue(vector<int>& nums) {int n=nums.size();long long ans=0;vector<int>suf(n);for(int i=n-1;i>=1;i--)suf[i-1]=max(suf[i],nums[i]);for(int j=1,pre=nums[0];j<n;j++){ans=max(ans,1LL*(pre-nums[j])*suf[j]);pre=max(pre,nums[j]);}return ans;}
};

假设我们选择方案三:枚举k(即先确定一个nums[ k ]),那么nums[ i ]和nums[ j ]要如何选?才能让三元组的值最大,即nums[ i ] - nums[ j ]要最大,那么这不就是在遍历的过程中,维护一个前缀最大值和一个最大高度差吗,(估计有人不太能理解,我画个折线图,大家应该能好懂一些,思路和121. 买卖股票的最佳时机很相似)

代码如下

class Solution {
public:long long maximumTripletValue(vector<int>& nums) {int n=nums.size();long long ans=0;for(int k=0,pre=0,diff=0;k<n;k++){ans=max(ans,1LL*diff*nums[k]);diff=max(diff,pre-nums[k]);pre=max(pre,nums[k]);}return ans;}
};

(大家可以试着将第二题的代码放到第一题去跑一跑,对比一下两者的时间,感受一下算法的魅力) 

三、无限数组的最短子数组

看到找最短的子数组的和等于target,第一个想到的就是滑动窗口,当然这题和正常的滑窗有点不同,它给的数组是个可以循环的无限长数组。

我们要弄明白两个问题:

1.我们需要一直遍历到无限远吗?不需要,我们的left端点只要在2倍的该数组里面遍历就行,因为一旦超过这个范围,后面的就又会开始循环之前遍历的结果,没有任何意义。

2.如果target>=sum(nums) ,我们的子数组还需要从0开始增加长度吗?不用,因为不论怎么枚举,子数组的长度都会有length(nums)*(target/sum(nums))的基础长度,我们只要关心target%sum(nums)这部分的最小子数组的长度就可以了,这样我们就将子数组差分成了两个部分,一个是以整个数组为单位的,一个是单独考虑的。

当然肯定有人会怀疑我们这种想法是不是太想当然了,万一这两部分不能形成一个子数组怎么办?好,这里我们就构造一个这样的子数组,我们假定找到了单独考虑的那部分子数组,然后我们继续向后延伸,由于数组是循环的,所以我们总能找到和原数组长度一样的,值相等的区间,如此循环就能构造出我们想要的最短子数组,即上面的想法正确

代码如下

class Solution {
public:typedef long long LL;int minSizeSubarray(vector<int>& nums, int target) {LL sum=accumulate(nums.begin(),nums.end(),0LL);int n=nums.size();int s=0,ans=INT_MAX;for(int left=0,right=0;right<2*n;right++){s+=nums[right%n];while(s>(target%sum)){s-=nums[left%n];left++;}if(s==(target%sum)) ans=min(ans,right-left+1);}if(ans==INT_MAX)return -1;return ans+target/sum*n;}
};

四、有向图访问计数

这是一个求每个结点向下能访问多少个不同结点的问题,我们需要用拓扑排序将每个环从图中拆下来单独考虑,得到换上每个结点的访问个数,然后利用返图,计算不在环上的点的访问个数,

代码如下

class Solution {
public:vector<int> countVisitedNodes(vector<int>& edges) {int n=edges.size();vector<vector<int>>g(n);//反图vector<int>deg(n);//入度for(int i=0;i<n;i++){g[edges[i]].push_back(i);deg[edges[i]]++;}//拓扑排序queue<int>q;//存放入读为0的点for(int i=0;i<n;i++){if(deg[i]==0)q.push(i);}//将不在环上的结点从图中去掉,指的是将结点的入度设置为0while(!q.empty()){int x=q.front();q.pop();if(--deg[edges[x]]==0)q.push(edges[x]);}vector<int>ans(n);//计算不在环上的点function<void(int,int)>dfs=[&](int x,int depth){ans[x]=depth;for(int y:g[x]){if(deg[y]==0){//环上的点入度为-1,这里只遍历不在环上的点dfs(y,depth+1);}}};for(int i=0;i<n;i++){if(deg[i]<=0) continue;//先计算环上的点的个数vector<int>node;for(int x=i;;x=edges[x]){node.push_back(x);deg[x]=-1;//被计算过的环上的点的入度设为-1if(edges[x]==i)break;}for(int x:node){dfs(x,node.size());}}return ans;}
};

相关文章:

Leetcode---365周赛

题目列表 2873. 有序三元组中的最大值 I 2874. 有序三元组中的最大值 II 2875. 无限数组的最短子数组 2876. 有向图访问计数 一、有序三元组中的最大值I 看一眼该题的数据范围&#xff0c;直接三层for循环暴力枚举&#xff0c;时间复杂度O(n^3)&#xff0c;代码如下 class…...

Java使用opencv实现人脸识别、人脸比对

1. opencv概述 OpenCV是一个开源的计算机视觉库&#xff0c;它提供了一系列丰富的图像处理和计算机视觉算法&#xff0c;包括图像读取、显示、滤波、特征检测、目标跟踪等功能。 opencv官网&#xff1a;https://opencv.org/ opencv官网文档&#xff1a;https://docs.opencv.or…...

Redis HyperLogLog的使用

Redis HyperLogLog知识总结 一、简介二、使用 一、简介 Redis HyperLogLog是一种数据结构&#xff0c;用于高效地计算基数&#xff08;集合中唯一元素的数量&#xff09;。它的主要作用是用于在内存中高效地存储和计算大量数据的基数&#xff0c;而无需完全存储所有的数据。Hy…...

Apisix-Ingress服务发现详解

apisix Apache APISIX 是一个基于微服务 API 网关&#xff0c;其不仅可以处理南北向的流量&#xff0c;也可以处理东西向的流量即服务之间的流量。Apache APISIX 集成了控制面板和数据面&#xff0c;与其他 API 网关相比&#xff0c;Apache APISIX 的上游、路由、插件全是动态的…...

spring6-事务

文章目录 1、JdbcTemplate1.1、简介1.2、准备工作1.3、实现CURD①装配 JdbcTemplate②测试增删改功能③查询数据返回对象④查询数据返回list集合⑤查询返回单个的值 2、声明式事务概念2.1、事务基本概念①什么是事务②事务的特性 2.2、编程式事务2.3、声明式事务 3、基于注解的…...

JavaFx学习问题2--音频、视频播放失败情况

文章目录 一、路径注意事项&#xff1a;① 用相对路径的时候别忘了前面的斜杠② uri问题 二、播放不了的问题① 获取的媒体文件路径本身就是不对的② 必须是uri③ 特殊情况 额外收获: 一、路径注意事项&#xff1a; 完整代码如下: import javafx.application.Application; im…...

第55节—— redux-toolkit中的createReducer——了解

一、概念 当我们使用 Redux 开发应用程序时&#xff0c;一个非常重要的概念就是 reducer。一个 reducer 是一个纯函数&#xff0c;它接受先前的状态和一个动作&#xff0c;然后返回一个新状态。每个动作都会引起状态的变化&#xff0c;从而使应用程序状态管理更加清晰和可控。…...

JUC并发编程——JUC并发编程概述及Lock锁(重点)(基于狂神说的学习笔记)

基于bilibili狂神说JUC并发编程视频所做笔记 概述 什么是JUC JUC时java.util工具包中的三个包的简称 java.util.concurrent java.util.concurrent.atomic java.util.concurrent.locks 业务&#xff1a;普通的线程代码中&#xff0c;我们常使用Runnable接口 但Runnable没有返…...

深入了解 Java 中的时间信息定义、转换、比较和操作

1. 简介 在过去的传统Java日期处理中&#xff0c;经常面临着一些问题。比如&#xff0c;java.util.Date和java.util.Calendar在表示日期和时间时存在着一些奇怪的行为&#xff0c;如月份从0开始计数、对日期进行格式化的方式繁琐不直观等。这些问题给开发带来了一定的困扰。 …...

2023年中国智能矿山发展历程及趋势分析:智能矿山健康有序发展[图]

智能矿山系统对矿山生产提质增效的效果已经开始显现&#xff1a;对不合规、有风险的行动进行及时预警&#xff0c;减少安全事故发生概率&#xff0c;避免因停产整顿产生的巨额亏损&#xff1b;精细化管理整个生产流程&#xff0c;避免过往传统粗放的流程导致的浪费&#xff0c;…...

acwing算法基础之基础算法--整数离散化算法

目录 1 知识点2 模板 1 知识点 整个范围很大&#xff0c;但存在的数据点很少。比如从 − 1 0 9 -10^9 −109到 1 0 9 10^9 109&#xff0c;但总共只有 1 0 6 10^6 106个数。 可以采用离散化的思想来做&#xff0c;即将离散的大数值映射成连续的小数值&#xff08;一般是 1 , …...

基于SSM框架的安全教育平台

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

Kafka生产者使用案例

1.生产者发送消息的过程 首先介绍一下 Kafka 生产者发送消息的过程&#xff1a; 1)Kafka 会将发送消息包装为 ProducerRecord 对象&#xff0c; ProducerRecord 对象包含了目标主题和要发送的内容&#xff0c;同时还可以指定键和分区。在发送 ProducerRecord 对象前&#xff0c…...

EasyX图形库实现贪吃蛇游戏

⭐大家好&#xff0c;我是Dark Falme Masker,学习了动画制作及键盘交互之后&#xff0c;我们就可以开动利用图形库写一个简单的贪吃蛇小游戏&#xff0c;增加学习乐趣。 ⭐专栏&#xff1a;EasyX部分小游戏实现详细讲解 最终效果如下 首先包含头文件 #include<stdio.h> #…...

利用 Amazon CodeWhisperer 激发孩子的编程兴趣

我是一个程序员&#xff0c;也是一个父亲。工作之余我会经常和儿子聊他们小学信息技术课学习的 Scratch 和 Kitten 这两款图形化的少儿编程工具。 我儿子有一次指着书房里显示器上显示的 Visual Studio Code 问我&#xff0c;“为什么我们上课用的开发界面&#xff0c;和爸爸你…...

2023年中国分子筛稀土催化材料竞争格局及行业市场规模分析[图]

稀土催化材料能够起到提高催化剂热稳定性、催化剂活性、催化剂储氧能力&#xff0c;以及减少贵金属活性组分用量等作用&#xff0c;广泛应用于石油化工、汽车尾气净化、工业废气和人居环境净化、燃料电池等领域。 2015-2023年中国稀土催化材料规模及预测 资料来源&#xff1a;…...

vue3插件——vue-web-screen-shot——实现页面截图功能

最近在看前同事发我的vue3框架时&#xff0c;发现他们有个功能是要实现页面截图功能。 vue3插件——vue-web-screen-shot——实现页面截图功能 效果图如下&#xff1a;1.操作步骤1.1在项目中添加vvue-web-screen-shot组件1.2在项目入口文件导入组件——main.ts1.3在需要使用的页…...

简单总结Centos7安装Tomcat10.0版本

文章目录 前言JDK8安装部署Tomcat 前言 注意jdk与tomcat的兼容问题&#xff0c;其他的只要正确操作一般问题不大 Tomcat 是由 Apache 开发的一个 Servlet 容器&#xff0c;实现了对 Servlet 和 JSP 的支持&#xff0c;并提供了作为Web服务器的一些特有功能&#xff0c;如Tomca…...

ffmpeg中AVCodecContext和AVCodec的关系分析

怎么理解AVCodecContext和AVCodec的关系 AVCodecContext和AVCodec是FFmpeg库中两个相关的结构体&#xff0c;它们在音视频编解码中扮演着不同的角色。 AVCodecContext&#xff1a;是编解码器上下文结构体&#xff0c;用于存储音视频编解码器的参数和状态信息。它包含了进行音视…...

2023年中国门把手产量、销量及市场规模分析[图]

门把手行业是指专门从事门把手的设计、制造、销售和安装等相关业务的行业。门把手是门窗装饰硬件的一种&#xff0c;用于开启和关闭门窗&#xff0c;同时也具有装饰和美化门窗的作用。 门把手行业分类 资料来源&#xff1a;共研产业咨询&#xff08;共研网&#xff09; 随着消…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...