数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究C++中打开水龙头浇灌花园的最小次数
假设在x轴上有一个一维花园。花园的起始位置为0，结束位置为n。花园中有n+1个水龙头位于点[0, 1, ..., n]。如果我们有一个整数n和一个长度为n+1的整数数组ranges，其中ranges[i]是第i个水龙头在打开时可以浇灌的区域[i - ranges[i], i + ranges[i]]。
我们必须找到应该打开多少个水龙头才能浇灌整个花园，如果没有可能的解决方案，则返回-1。
因此，如果输入类似于n = 5，而ranges = [3,4,1,1,1,0]，则输出将为1，因为从第二个水龙头开始，它将覆盖整个区域[-3到5]。
为了解决这个问题，我们将遵循以下步骤：
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为(n + 1)的数组v，并将其填充为-1
初始化i := 0，当i <= n时，更新（i增加1），执行：
u := max(i - ranges[i], 0)
e := min(n, i + ranges[i])
v[u] := max(v[u], e)
如果v[0]等于-1，则：
返回-1
curr := v[0]
i := 0, next := 0
当curr < n时，执行：
当i <= curr时，执行：
next := max(next, v[i])
(i增加1)
如果next等于curr，则：
返回-1
curr := next
(ret增加1)
返回ret
让我们看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
int ret = 1;
vector<int> v(n + 1, -1);
for (int i = 0; i <= n; i++) {
int u = max(i - ranges[i], 0);
int e = min(n, i + ranges[i]);
v[u] = max(v[u], e);
}
if (v[0] == -1)
return -1;
int curr = v[0];
int i = 0;
int next = 0;
while (curr < n) {
while (i <= curr) {
next = max(next, v[i]);
i++;
}
if (next == curr)
return -1;
curr = next;
ret++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,4,1,1,1,0};
cout << (ob.minTaps(5, v));
}输入
5, {3,4,1,1,1,0}输出
1
更新于：2020年6月8日
浏览量：292
广告