我的博客

5318. 灌溉花园的最少水龙头数目 leetcode 1326 周赛 172 - python

目录
  1. 解答

https://leetcode-cn.com/contest/weekly-contest-172/problems/minimum-number-of-taps-to-open-to-water-a-garden/

在 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:

img

1
2
3
4
5
6
7
8
9
10
输入: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:

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

示例 3:

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

示例 4:

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

示例 5:

1
2
输入: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

解答

这题目 18 年初实习面试的时候被问过。线段覆盖问题。贪心算法。面试的时候我想的使用递归方法,这次写的是迭代。

思路是:
先把每个水龙头的范围转化成区间,弄成一个区间数组。
比如 示例 1

1685_example_1.png

转换成:

[[0, 3], [0, 5], [1, 3], [2, 4]]

这里做了两个优化:

  1. 长度为零的就忽略了
  2. 超出 0 到 n 范围的就截止到 [0, n] 区间内

然后我们可以在按照区间的左端点排序。(上面的数组已经是这个顺序了)

其实另外还有一个优化:如果一个区间被另一个区间完全覆盖了,那这个区间也是无效的,应该删掉,例如 [1, 3] 完全落在 [0, 3] 内。

结果这里就只剩下 [0, 5] 了:
[[0, 5]]

所以这个例子不好,可以看下示例 3

n = 7, ranges = [1,2,1,0,2,1,0,1]

经过上述操作后剩下的区间其实也只有刚好三个了:
[(0, 3), (2, 6), (6, 7)]
所以干脆去掉

之后的做法是:

如果这个区间数量是 0 或者第一个区间不能覆盖 0,直接返回 -1
然后就开始贪心:

  1. 第一个区间必选,ans 变量计已选的区间数
  2. 判断是否可以覆盖,如果可以,返回 ans
  3. 从下一个区间开始,所有可以选择的区间(如果这个区间的左端点小于等于上一个选中区间的右端点,就可以选)中找一个右端点最大的,选择,如果没有可选的,返回 -1

这个代码写的不够精炼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
# ranges 转化为区间
seg = []
for i in range(n+1):
if ranges[i] > 0:
seg.append((max(0, i - ranges[i]), min(n, i + ranges[i])))
# 去掉被其他区间覆盖的区间
s2 = {}
for s in seg:
if s[0] not in s2:
s2[s[0]] = []
s2[s[0]].append(s)
seg = []
for k in s2:
t = s2[k][0]
for xx in s2[k]:
if xx[1] > t[1]:
t = xx
seg.append(t)
s2 = {}
for s in seg:
if s[1] not in s2:
s2[s[1]] = []
s2[s[1]].append(s)
seg = []
for k in s2:
t = s2[k][0]
for xx in s2[k]:
if xx[0] < t[0]:
t = xx
seg.append(t)


seg.sort(key=lambda x: x[0]) # 按区间左端点排序


if not seg or seg[0][0] != 0: # 区间数量是 0 或者第一个区间不能覆盖 0,直接返回 -1
return -1

i = 0
ans = 1
while seg[i][1] != n:
nx = i
j = 1 + i
while j < len(seg) and seg[j][0] <= seg[i][1]:
if seg[nx][1] < seg[j][1]:
nx = j
j += 1
if nx == i:
return -1
ans += 1
i = nx
return ans

评论无需登录,可以匿名,欢迎评论!