当前位置: 首页 > 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…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

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. 执行器…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...