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

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...