• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1326.灌溉花园的最少水龙头数目|MinimumNumberofTapstoOpentoWateraGa ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(let_us_code)
➤博主域名:https://www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/12213419.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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.

 

Example 1:

 

 


Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]
Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.
Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3
Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2
Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1
 

Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100


在 x 轴上有一个一维的花园。花园长度为 n,从点 0 开始,到点 n 结束。

花园里总共有 n + 1 个水龙头,分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ,其中 ranges[i] (下标从 0 开始)表示:如果打开点 i 处的水龙头,可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方,请你返回 -1 。

 

示例 1:

 

 

 

输入:n = 5, ranges = [3,4,1,1,0,0]
输出:1
解释:
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。
示例 2:

输入:n = 3, ranges = [0,0,0,0]
输出:-1
解释:即使打开所有水龙头,你也无法灌溉整个花园。
示例 3:

输入:n = 7, ranges = [1,2,1,0,2,1,0,1]
输出:3
示例 4:

输入:n = 8, ranges = [4,0,0,0,0,0,0,0,4]
输出:2
示例 5:

输入:n = 8, ranges = [4,0,0,0,4,0,0,0,4]
输出:1
 

提示:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100


Runtime: 148 ms
Memory Usage: 21.7 MB
 1 class Solution {
 2     func minTaps(_ n: Int, _ ranges: [Int]) -> Int {
 3         var rg:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: 2), count: n + 1)
 4         for i in 0...n
 5         {
 6             let s:Int =  i - ranges[i]
 7             let e:Int =  i + ranges[i]
 8             rg[i] = [s < 0 ? 0 : s, e < n ? e : n]
 9         }
10         rg = rg.sorted(by:{
11             if $0[0] == $1[0]
12             {
13                 return $0[1] < $1[1]
14             }
15             else
16             {
17                 return $0[0] < $1[0]
18             }
19         }
20         )
21         var ans:Int = 0
22         var i:Int = 0
23         var start:Int = 0
24         var end:Int = 0
25         while(start < n && i <= n)
26         {
27             while(i <= n && rg[i][0] <= start)
28             {
29                 end = max(end, rg[i][1])
30                 i += 1
31             }
32             if end <= start{return -1}
33             start = end
34             ans += 1
35         }
36         return ans
37     }
38 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift元组发布时间:2022-07-13
下一篇:
[Swift]LeetCode330.按要求补齐数组|PatchingArray发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap