LeetCode---386周赛

题目列表

3046. 分割数组

3047. 求交集区域内的最大正方形面积

3048. 标记所有下标的最早秒数 I

3049. 标记所有下标的最早秒数 II

一、分割数组

这题简单的思维题,要想将数组分为两个数组,且分出的两个数组中数字不会重复,很显然一个数字出现次数最多两次,代码如下

class Solution {
public:bool isPossibleToSplit(vector<int>& nums) {unordered_map<int,int>mp;for(auto x:nums)if(++mp[x]>2)return false;return true;}
};

二、求交集区域内的最大正方形面积

直接暴力枚举出所有两个矩阵的交集的正方形面积,求解出最大值,代码如下

class Solution {
public:long long largestSquareArea(vector<vector<int>>& bLeft, vector<vector<int>>& tRight) {int n=bLeft.size(),w=0;for(int i=1;i<n;i++){for(int j=i-1;j>=0;j--){//挑选四个直线,围成交集区域int x_l=max(bLeft[i][0],bLeft[j][0]);int x_r=min(tRight[i][0],tRight[j][0]);int y_top=min(tRight[i][1],tRight[j][1]);int y_bottom=max(bLeft[i][1],bLeft[j][1]);if(x_l<x_r&&y_top>y_bottom){//确保会有交集w=max(w,min(x_r-x_l,y_top-y_bottom));}}    }return 1LL*w*w;}
};

三、标记所有下标的最早秒数I

题目问最早秒数,我们正常来说都会想到贪心 / 从小到大枚举验证,其中贪心,大家可以去试着想想,因为需要从左往右遍历时间,而我们不知道后面changeIndices[]的情况,所以就不能去决定这一步去做什么操作会比较好,也就很难去贪心。

那么我们来看看枚举验证行不行?一旦数据不好,估计得验证O(n)次,大概率会超时,所以我们要降低时间复杂度,怎么做?--- 二分

1、是否满足二分条件,即单调性?

根据题目所给的条件,我们知道时间越多,我们越有可能将nums[i]减为零,越有可能标记所有下标,即秒数越多越能满足条件,符合单调性,可以二分

2、如何验证是否能在k秒内标记所有下标,即bool check(int k)函数如何写?(如果下面的内容不理解,可以先看看下面加粗的内容)

首先,由于changeIndices[]是不可预知的,即标记操作是不可控的,所以我们优先考虑什么时候标记下标的问题,根据贪心,我们肯定是越晚标记下标越好,这样会有更多的时间将nums[i]减为零,所以我们要知道每个下标的最晚标记时间

然后在来考虑是否能在下标 i 的最晚标记时间之前,将nums[i]减为零,这个就很简单了,我们只要维护一个cnt来记录到目前为止有多少时间,然后在到达某个最晚标记时间时,如果cnt>=nums[i],cnt = cnt - nums[i],否则直接返回false,如果所有下标都能被标记就返回true (很显然check函数的时间复杂度为O(n),所以暴力枚举会超时,需要二分)

如果大家不是很理解,可以将这题转换成考试来看,即一共有n门课程,nums[i]表示第 i 门课程的复习天数,changeIndices[i]表示第 i 天进行考试的课程,问复习完并考完所有课程的最少天数是多少?相信经历了这么多年考试的你们,会更容易理解复习和考试的关系(doge)

代码如下

/*
将问题转换成一共有n门课程,第i门课程的复习时间为nums[i]天
changeIndices[i]课程的考试时间为第i天
复习并考完所有课程的最小时间由于考试时间是固定的,我们需要优先考虑考试时间
=> 考试时间越靠后,就会有更加充分的时间用来复习
=> 具有单调性
=> 可以二分check函数如何去判断是否能复习考完所有的考试?
1、贪心,我们把每门课程的考试时间尽可能往后拖延  last[]记录每门课程的最迟考试时间
2、如果考试数目<=课程数,return false; // 可以优化的点否则我们从前往后遍历天数,优先复习考试时间近的科目,看能否在考试之前完成复习
*/class Solution {
public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();auto check=[&](int k)->bool{vector<int>last(n,-1); // 记录下标i的最晚标记时间,即最晚考试时间for(int i=0;i<k;i++)last[changeIndices[i]-1]=i;for(auto x:last)if(x<0) // 表示有的下标没有被标记的时间,即有的课程没有考试return false;int cnt = 0;for(int i=0;i<k;i++){int idx = changeIndices[i] - 1;if(last[idx]==i){//表示下标idx到了最后的被标记的时间,即课程到了考试的最后截止时间cnt-=nums[idx];if(cnt<0) return false;//没有足够的时间将nums[idx]置为0,即没有足够的时间复习课程}else{cnt++;}}return true;};int l=1,r=m;while(l<=r){int mid = l+(r-l)/2;if(check(mid)) r=mid-1;else l=mid+1;}return l>m?-1:l;}
};

四、标记所有下标的最早秒数II

有情提醒一下: 该题和第三题的题目并不一样。

在这题中,操作变得更加复杂了,但其实我们还是可以借鉴第三题的思路:

首先,这题依旧能够二分,因为时间越多,越有可能标记所有下标,但是check函数的思路不一样了,我们要优先考虑清零操作,因为它是不可控的(为了方便描述,这里将题目中的几个操作分别称为减一、清零、标记)。

【如果下面的内容看不太明白,依旧可以带入上一题说的考试模型,帮助你理解---减一操作:花费一天复习一门课,清空操作:花费一天速通一门课,标记:选择一天用来考试】

1)这里就要讨论一下:清零操作和减一操作什么时候用比较合适?

1、如果nums[i]用过减一操作,还需要用清零操作吗?没必要,因为如果能清零,就没必要在花多余的时间进行减一,可以将多出的时间给其他的nums[j]

2、如果nums[i]用过清零操作,也就不需要在进行减一操作了

结论:对于nums[i]要么执行清零操作,要么就执行减一操作,不能混用

2)根据贪心:我们肯定是能清零就尽量的去执行清零,让被清零的nums[i]有更多的时间被减为0

1、清零操作是越早越好还是越晚越好?肯定是越早越好,因为我们还需要有多余的时间去标记,所以我们需要从后往前遍历,去看是否有多余的时间去标记下标,所以我们要记录每个下标的最早清零时间

2、什么时候不需要用清零操作?

  • nums[i]==0时,不需要
  • nums[i]==1时,也不需要,因为减一操作也能做到清零,且可以在任意时间执行

除了上面的两种情况,还有一种特殊的情况,即用完清零操作之后就没时间进行标记了,这里我们不是只能进行对 i 下标进行nums[i]次减一操作,而是可以看之前进行清空操作的下标中nums[j]的最小值 是否 比nums[i]小,如果小,那么显然我们可以对 j 下标进行nums[j]次减一操作,同时nums[i]就会有时间进行清零和标记,这样的方案显然会更优----反悔贪心

我们从后往前遍历,同时维护用来标记/减一的时间cnt 和 需要减一和标记的总时间sum(都不包含进行清零操作的下标的标记时间)具体如何维护看下面的代码。

class Solution {
public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();long long total = n;for(auto x:nums) total += x;            vector<int>first_d(n,-1);for(int i=m-1;i>=0;i--)first_d[changeIndices[i]-1]=i;auto check=[&](int k)->bool{priority_queue<int,vector<int>,greater<int>> q;int cnt = 0;// 减一复习并考试的课程的所有时间long long slow = total;//记录减一操作的nums[i]及其标记需要的时间,一开始默认全用减一操作for(int i=k-1;i>=0;i--){int idx=changeIndices[i]-1;if(nums[idx]<=1||i!=first_d[idx]){cnt++;continue;}if(cnt==0){if(q.empty()||nums[idx]<=q.top()){//只能进行减一操作cnt++;continue;}slow += q.top()+1;q.pop();cnt += 2;}slow -= nums[idx]+1;cnt--;q.push(nums[idx]);}return cnt>=slow;};int l=1,r=m;while(l<=r){int mid=l+(r-l)/2;if(check(mid)) r=mid-1;else l=mid+1;}return l>m?-1:l;}
};

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

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

相关文章

DM数据库学习之路(十九)DM8数据库sysbench部署及压力测试

sysbench部署 安装依赖 yum -y install make automake libtool pkgconfig libaio-devel vim-common 上传sysbench源代码 sysbench_tool.tar 测试是否安装成功 $ /opt/sysbench/sysbench-master-dpi/src/lua $ ./sysbench --version sysbench 1.1.0 sysbench测试DM 测试…

反序列化逃逸 [安洵杯 2019]easy_serialize_php1

打开题目 题目源码&#xff1a; <?php$function $_GET[f];function filter($img){$filter_arr array(php,flag,php5,php4,fl1g);$filter /.implode(|,$filter_arr)./i;return preg_replace($filter,,$img); }if($_SESSION){unset($_SESSION); }$_SESSION["user&qu…

巧【二叉搜索树的最近公共祖先】【二叉搜索树的性质】Leetcode 235. 二叉搜索树的最近公共祖先

【二叉搜索树的最近公共祖先】【二叉搜索树性质】Leetcode 235. 二叉搜索树的最近公共祖先 【巧】解法1 利用二叉搜索树有序的性质解法2 采用二叉树求最近公共祖先的方法——后序遍历 ---------------&#x1f388;&#x1f388;235. 二叉搜索树的最近公共祖先 题目链接&#x…

[通用] iPad 用于 Windows 扩展屏解决方案 Moonlight + Sunshine + Easy Virtual Display

文章目录 前言推流端 Sunshine 安装设置接收端安装 Moonlight安装虚拟屏幕软件 Easy Virtual Display 前言 上期博客讲了如何利用原生的 NVIDIA’s GameStream 传输协议实现 iPad 当作 Windows 副屏&#xff0c;对于非N卡用户&#xff0c;有一个软件 Sunshine 可以代替 Nvidia…

Verilog Constructs、Verilog系统任务和功能

下表列出了Verilog构造在Vivado合成中的支持状态。 Verilog系统任务和功能 Vivado合成支持系统任务或功能&#xff0c;如下表所示。Vivado合成会忽略不支持的系统任务。 使用转换函数 使用以下语法对任何表达式调用$signed和$unsigned系统任务。 $signed&#xff08;expr&am…

鸿蒙学习day1基础语法 基础变量类型

在这里插入图片描述 什么是变量&#xff1a;变量就是一些数据 如125&#xff0c;‘字符串数据’ 通过一个符号来表示 变量的定义 方法 let 变量名&#xff1a;变量类型 ’ 各种数据’ ,let是关键字&#xff0c;系统给的用来定义变量的 let name: string 张亚洲; let age: …

安卓使用okhttpfinal下载文件,附带线程池下载使用

1.导入okhttp包 implementation cn.finalteam:okhttpfinal:2.0.7 2.单个下载 package com.example.downloading;import androidx.appcompat.app.AppCompatActivity;import android.os.Bundle; import android.util.Log; import android.view.View;import java.io.File;import c…

今日学习总结2024.3.3

今天也是全天自习的一天&#xff0c;非常充实 早上八点开始接着晚上的docker配置&#xff0c;并一边同步博客&#xff0c;还是遇到了卡壳 【未完结】nginxhexo搭建个人网站真实体验&#xff01;https://blog.csdn.net/m0_62742402/article/details/136425066 看了一个视频&…

SpringCloud-MQ消息队列

一、消息队列介绍 MQ (MessageQueue) &#xff0c;中文是消息队列&#xff0c;字面来看就是存放消息的队列。也就是事件驱动架构中的Broker。消息队列是一种基于生产者-消费者模型的通信方式&#xff0c;通过在消息队列中存放和传递消息&#xff0c;实现了不同组件、服务或系统…

平台工程: 用Backstage构建开发者门户 - 2

本文介绍了如何使用开源Backstage构建自己的开发者门户&#xff0c;并基于此实践平台工程。本系列共两篇文章&#xff0c;这是第二篇。原文: Platform Engineering: Building Your Developer Portal with Backstage — Part 2 在本教程第一部分中我们了解了Backstage这个用于构…

qsort使用

qsort 是用来排序的数据的库函数,底层使用的是快速排序的方式 排序方式有:选择,冒泡,插入,快速, 希尔...... 对于qsort这个库函数: void qsort(void* base,size_t num,size_t size,int (*compar)(const void*,const void*) 其中 void* base 是指针,指向的是待排序的数组的第…

强大的Docker入门知识

目录 一、Docker简介 1.1、Docker是 1.2、Docker通常会在以下情况下使用&#xff1a; 1.3、Docker和VMware区别 1.4、Docker 的优点 二、环境配置 2.1、代码操作 2.2、效果演示 2.3、配置镜像仓库 开始配置 三、基本命令 3.1、Docker基本命令 3.2、Docker镜像常用…

.idea文件详解

.idea文件的作用&#xff1a; .idea文件夹是存储IntelliJ IDEA项目的配置信息&#xff0c;主要内容有IntelliJ IDEA项目本身的一些编译配置、文件编码信息、jar包的数据源和相关的插件配置信息。一般用git做版本控制的时候会把.idea文件夹排除&#xff0c;因为这个文件下保存的…

JS进阶——深入对象

版权声明 本文章来源于B站上的某马课程&#xff0c;由本人整理&#xff0c;仅供学习交流使用。如涉及侵权问题&#xff0c;请立即与本人联系&#xff0c;本人将积极配合删除相关内容。感谢理解和支持&#xff0c;本人致力于维护原创作品的权益&#xff0c;共同营造一个尊重知识…

数据挖掘:航空公司的客户价值分析

需求分析 理解并掌握聚类分析方法&#xff0c;掌握数据的标准化&#xff0c;掌握寻找最佳聚类数&#xff0c;掌握聚类的绘图&#xff0c;掌握聚类分析的应用场景。 系统实现 实验流程分析 借助航空公司数据&#xff0c;对客户进行分类对不同类别的客户进行特征分析&#xf…

聊聊 HTTP 性能优化

作为用户的我们在 "上网冲浪" 的时候总是希望快一点&#xff0c;尤其是抢演唱会门票的时候&#xff0c;但是现实并非如此&#xff0c;有时候我们会遇到页面加载缓慢、响应延迟的情况。 而 HTTP 协议作为互联网世界的基础&#xff0c;从网站打开速度到移动应用的响应…

uniapp:使用DCloud的uni-push推送消息通知(在线模式)java实现

uniapp:使用DCloud的uni-push推送消息通知&#xff08;在线模式&#xff09;java实现 1.背景 今天开发app的时候遇到一个需求&#xff1a; 业务在出发特定条件的时候向对应的客户端推送消息通知。 为什么选择在线模式&#xff0c;因为我们使用的是德邦类似的手持终端&#xf…

一文带你了解MySQL之B+树索引的原理

前言 学完前面我们讲解了InnoDB数据页的7个组成部分&#xff0c;知道了各个数据页可以组成一个双向链表&#xff0c;而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表&#xff0c;每个数据页都会为存储在它里边儿的记录生成一个页目录&#xff0c;在通过主键查…

Java ZooKeeper-RocketMQ 面试题

Java ZooKeeper-RocketMQ 面试题 前言1、谈谈你对ZooKeeper的理解 &#xff1f;2、Zookeeper的工作原理&#xff08;Zab协议&#xff09;3、谈谈你对分布式锁的理解&#xff0c;以及分布式锁的实现&#xff1f;4、 zookeeper 是如何保证事务的顺序一致性的&#xff1f;5、 zook…

LeetCode --- 三数之和

题目描述 三数之和 代码解析 暴力 在做这一道题的时候&#xff0c;脑海里先想出来的是暴力方法&#xff0c;一次排序&#xff0c;将这个数组变为有序的&#xff0c;再通过三次for循环来寻找满足条件的数字&#xff0c;然后将符合条件的数组与之前符合条件的数组进行一一对比…