本文主要是介绍2023-10-13 LeetCode每日一题(避免洪水泛滥),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2023-10-13每日一题
一、题目编号
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:
示例 2:
示例 3:
四、解题代码
class Solution {
public:vector<int> avoidFlood(vector<int>& rains) {vector<int> ans(rains.size(), 1);set<int> st;unordered_map<int, int> mp;for (int i = 0; i < rains.size(); ++i) {if (rains[i] == 0) {st.insert(i);} else {ans[i] = -1;if (mp.count(rains[i])) {auto it = st.lower_bound(mp[rains[i]]);if (it == st.end()) {return {};}ans[*it] = rains[i];st.erase(it);}mp[rains[i]] = i;}}return ans;}
};
五、解题思路
(1) 贪心+二分
这篇关于2023-10-13 LeetCode每日一题(避免洪水泛滥)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!