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

LeetCode:1488. 避免洪水泛滥(2023.10.13 C++)

目录

1488. 避免洪水泛滥

实现代码与解析:

贪心

原理思路:


1488. 避免洪水泛滥

题目描述:

        你的国家有无数个湖泊,所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的,那么它就会装满水。如果第 n 个湖泊下雨前是 满的 ,这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。

给你一个整数数组 rains ,其中:

  • rains[i] > 0 表示第 i 天时,第 rains[i] 个湖泊会下雨。
  • rains[i] == 0 表示第 i 天没有湖泊会下雨,你可以选择 一个 湖泊并 抽干 这个湖泊的水。

请返回一个数组 ans ,满足:

  • ans.length == rains.length
  • 如果 rains[i] > 0 ,那么ans[i] == -1 。
  • 如果 rains[i] == 0 ,ans[i] 是你第 i 天选择抽干的湖泊。

如果有多种可行解,请返回它们中的 任意一个 。如果没办法阻止洪水,请返回一个 空的数组 。

请注意,如果你选择抽干一个装满水的湖泊,它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊,那么将无事发生。

示例 1:

输入:rains = [1,2,3,4]
输出:[-1,-1,-1,-1]
解释:第一天后,装满水的湖泊包括 [1]
第二天后,装满水的湖泊包括 [1,2]
第三天后,装满水的湖泊包括 [1,2,3]
第四天后,装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水,也没有湖泊会发生洪水。

示例 2:

输入:rains = [1,2,0,0,2,1]
输出:[-1,-1,2,1,-1,-1]
解释:第一天后,装满水的湖泊包括 [1]
第二天后,装满水的湖泊包括 [1,2]
第三天后,我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后,我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后,装满水的湖泊包括 [2]。
第六天后,装满水的湖泊包括 [1,2]。
可以看出,这个方案下不会有洪水发生。同时, [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

示例 3:

输入:rains = [1,2,0,1,2]
输出:[]
解释:第二天后,装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后,湖泊 1 和 2 都会再次下雨,所以不管我们第三天抽干哪个湖泊的水,另一个湖泊都会发生洪水。

提示:

  • 1 <= rains.length <= 105
  • 0 <= rains[i] <= 109

实现代码与解析:

贪心

class Solution {
public:vector<int> avoidFlood(vector<int>& rains) {int n = rains.size();vector<int> res(n, 1); // 没雨的日子就算不抽水,也要选一个湖泊1unordered_map<int, int> full; // <满的湖泊编号,在第几天满的>set<int> no_rain_days; // 从小到大排序, 无水的日子,可以抽水的机会日子for (int i = 0; i < n; i++) {if (rains[i] == 0) no_rain_days.insert(i); // 无雨,先把抽水的机会存起来else {res[i] = -1;if (full.count(rains[i])) { // 已经满了,再有雨就要洪水了,用掉一次抽水机会auto it = no_rain_days.upper_bound(full[rains[i]]); // 在满后的第一个无雨日抽水,这里是满足贪心规则,为了后面操作的最优选择if (it == no_rain_days.end()) return {}; // 如果满后没有无水日,那么ggres[*it] = rains[i]; // 记录结果,这天我们抽水的湖泊编号no_rain_days.erase(it); // 这个机会用了,去除}full[rains[i]] = i; // 今天下雨了,灌满}}return res;}
};

原理思路:

        感觉注释写的非常详细了。

相关文章:

LeetCode:1488. 避免洪水泛滥(2023.10.13 C++)

目录 1488. 避免洪水泛滥 实现代码与解析&#xff1a; 贪心 原理思路&#xff1a; 1488. 避免洪水泛滥 题目描述&#xff1a; 你的国家有无数个湖泊&#xff0c;所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的&#xff0c;那么它就会装满水。如果第 n 个湖泊下雨前是…...

SpringBoot 时 jar 报错 没有主清单属性

SpringBoot 时 jar 报错 没有主清单属性 参考资料 使用阿里版 Spring Initializr 创建的项目。 springboot 2.6.13 JDK 1.8 这里自动开了skip。 注释后打的 jar 包就可以运行了。 <build><finalName>${name}</finalName><plugins><plugin><…...

C/S架构学习之多进程实现TCP并发服务器

多进程实现TCP并发服务器的实现流程&#xff1a;一、自定义信号处理函数&#xff08;sig_func函数&#xff09;&#xff1a; void sig_func(int signum){wait(NULL);}wait函数: #include <sys/types.h>#include <sys/wait.h>pid_t wait(int *wstatus);/*功能&#…...

VSCode 快速移动光标至行尾

最近在用vscode进行C编程&#xff0c;经常需要把光标跳到行尾去添加符号。 手动到行尾太麻烦了。 一种快捷方式是&#xff1a;用键盘上的“END”快捷键。 但是用这个键也不是很方便&#xff0c;因为“end”键离主键盘区太远。 另一种便捷的方式是&#xff1a;给vscode设置自定义…...

ACP.复盘方法

复盘要怎么做的有水准&#xff0c;让领导满意&#xff0c;方式方法很重要。今天给你们安利5种复盘方法&#xff0c;保准你省事&#xff0c;领导还满意。 一、KPT复盘法 7月份年中一直在做和复盘相关的事&#xff0c;像公司的OKR复盘、年中战略规划&#xff0c;不过日常很多生…...

Springboot 订餐管理系统idea开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 springboot 订餐管理系统是一套完善的信息系统&#xff0c;结合springboot框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用springboot框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有 完整的源代码和数据库&…...

判断当前Activity是否有DialogFragment显示

DialogFragment一种情况是在当前Activity上启动&#xff0c;一种情况是在Fragment上启动&#xff0c;判断当前fragmentManager上是否有&#xff0c;以及遍历判断子fragment上是否有&#xff0c;即可确定是否有DialogFragment展示。 使用方式&#xff1a; // supportFragmentMa…...

开发一个npm组件包(2)

通过vueelement 原来后台 开发npm包的时候 会遇到一下几个问题 入口文件变化为package/index 需要再配置打包方法 package.json下 "scripts": {"package": "vue-cli-service build --target lib ./src/package/index.js --name managerpage --dest…...

迅为RK3568开发板Scharr滤波器算子边缘检测

本小节代码在配套资料“iTOP-3568 开发板\03_【iTOP-RK3568 开发板】指南教程\04_OpenCV 开发配套资料\33”目录下&#xff0c;如下图所示&#xff1a; 在 Sobel 算子算法函数中&#xff0c;如果设置 ksize-1 就会使用 3x3 的 Scharr 滤波器。Scharr 算子是 Soble 算子在 ksize…...

HJ86 求最大连续bit数

目录 一、题目 二、代码 一、题目 求最大连续bit数_牛客题霸_牛客网 二、代码 #include <iostream> #include<stack> #include<vector> using namespace std; void TEN_to_TWO(int x, vector<int>& data) { //10进制转换成二进制stack<int&…...

Grafana 10 新特性解读:体验与协作全面提升

作者&#xff1a;徽泠(苏墨馨) 为了庆祝 Grafana 的 10 年里程碑&#xff0c;Grafana Labs 推出了 Grafana 10&#xff0c;这个具有纪念意义的版本强调增强用户体验&#xff0c;使各种开发人员更容易使用。Grafana v10.0.x 为开发者与企业展示卓越的新功能、可视化与协作能力&…...

Django实现音乐网站 ⒆

使用Python Django框架做一个音乐网站&#xff0c; 本篇主要为排行榜功能及音乐播放器部分功能实现。 目录 推荐排行榜优化 设置歌手、单曲跳转链接 排行榜列表渲染优化 视图修改如下&#xff1a; 模板修改如下&#xff1a; 单曲详情修改 排行榜列表 设置路由 视图处理…...

20基于MATLAB的车牌识别算法,在环境较差的情景下,夜间识别度很差的车牌号码可以精确识别出具体结果,程序已调通,可直接替换自己的数据跑。

基于MATLAB的车牌识别算法&#xff0c;在环境较差的情景下&#xff0c;夜间识别度很差的车牌号码可以精确识别出具体结果&#xff0c;程序已调通&#xff0c;可直接替换自己的数据跑。 20matlab车牌识别 (xiaohongshu.com)...

vue音频制作

Vue 音频制作指的是使用 Vue.js 框架开发音频制作相关的 Web 应用程序。Vue.js 是一种现代化的 JavaScript 框架&#xff0c;它可以帮助开发者更快速、更高效地构建交互式的 Web 应用程序。 音频制作在 Vue.js 中的实现可以通过使用一些开源音频库和插件来实现&#xff0c;如 …...

好莱坞编剧大罢工终于结束;与OpenAI创始人共进早餐;使用DALL-E 3制作绘本分享;生成式AI的基础设施架构 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f525; 好莱坞编剧大罢工终于结束&#xff1a;简单说就是AI妥协了 https://www.wgacontract2023.org/the-campaign/summary-of-the-2023-wga-…...

buuctf week2-web-ez_sql

闭合之后尝试判断字段数&#xff0c;存在WAF&#xff0c;使用大小写绕过&#xff08;后面的sql语句也需要进行大小写绕过&#xff09; ?id1 Order by 5-- 测出有5列 ?id1 Order by 6-- 查一下数据库名、版本、用户等信息 ?id1Union Select database(),version(),user(),4,…...

实验2.1.2 交换机的常用配置

项目2 交换技术的位置 活动2 交换机的常用配置 一、具体要求&#xff1a; &#xff08;1&#xff09;添加1台计算机&#xff0c;将标签名更改为PC1。 &#xff08;2&#xff09;添加1台S3700-26C-HI交换机&#xff0c;标签名为SWA&#xff0c;将交换机的名称设置为SWA。 &am…...

功率放大器应用场景分析报告

功率放大器作为一种能够将低电压信号放大到高电压水平的关键设备&#xff0c;在多个领域中发挥着重要作用。报告通过对实验研究、射频通信、能源与电力系统、医疗诊断与治疗以及工业自动化等领域的综合分析&#xff0c;下面西安安泰为大家介绍功率放大器的应用场景。 实验研究 …...

解决 Centos 安装 Python 3.10 的报错: Could not import runpy module

操作环境&#xff1a;CentOS 7、Gcc 4.8.5、Python 3.10.0 系统上已经有 2.x&#xff0c;3.6 版本的 Python 了&#xff0c;但是还是想装一个 3.10 的。因为刚写的脚本文件是较高版本的&#xff0c;在 3.6 上无法正常运行&#xff0c;Python 语法不是很了解&#xff0c;只能从…...

HTML5简介-HTML5 新增语义化标签-HTML5 新增多媒体标签

一、HTML5简介 HTML5&#xff0c;全称为HyperText Markup Language 5&#xff0c;是HTML的第五个版本&#xff0c;由万维网联盟&#xff08;World Wide Web Consortium&#xff0c;W3C&#xff09;和Web Hypertext Application Technology Working Group&#xff08;WHATWG&am…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...