[Oracle] LeetCode 1326 Minimum Number of Taps to Open to Water a Garden
2022/8/26 2:23:15
本文主要是介绍[Oracle] LeetCode 1326 Minimum Number of Taps to Open to Water a Garden,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
There is a one-dimensional garden on the x-axis. The garden starts at the point 0
and ends at the point n
. (i.e The length of the garden is n
).
There are n + 1
taps located at points [0, 1, ..., n]
in the garden.
Given an integer n
and an integer array ranges
of length n + 1
where ranges[i]
(0-indexed) means the \(i\)-th tap can water the area [i - ranges[i], i + ranges[i]]
if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1
.
Solution
利用贪心的思想,我们先将区间 \([i-r[i], i+r[i]]\) \(push\_back\) 进去,然后进行 \(sort\). 主要思想就是我们固定左端点的时候,不断地去扩大右端点,然后以此时的右端点为左端点,再次求该时的最远右端点。
点击查看代码
class Solution { private: int ans=0; vector<vector<int>> itv; public: int minTaps(int n, vector<int>& ranges) { for(int i=0;i<n+1;i++){ itv.push_back({i-ranges[i], i+ranges[i]}); } sort(itv.begin(), itv.end()); int st=0, ed=0; int i=0; while(st<n){ while(i<itv.size() && itv[i][0]<=st){ ed = max(ed, itv[i][1]); i++; } if(st==ed)return -1; st = ed; ans++; } return ans; } };
这篇关于[Oracle] LeetCode 1326 Minimum Number of Taps to Open to Water a Garden的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升