用C ++打开花园浇水的最小水龙头数量
我们必须找到打开整个花园的水龙头的最小数量,如果没有可能的解决方案,则返回-1。
因此,如果输入为n=5,范围=[3,4,1,1,1,0],则输出为1,从第二次抽头开始,它将覆盖整个地面[-3至5]。
为了解决这个问题,我们将遵循以下步骤-
为了解决这个问题,我们将遵循以下步骤-
定义大小为(n+1)的数组v并用-1填充
对于初始化i:=0,当i<=n时,更新(将i增加1),请执行-
u:=i的最大值-range[i]和0
e:=n和i+范围的最小值[i]
v[u]:=v[u]和e的最大值
如果v[0]与-1相同,则-
返回-1
curr:=v[0]
i:=0,下一个:=0
而curr<n时,执行-
返回-1
下一个:=下一个和v[i]的最大值
(将i增加1)
当我<=curr时,做-
如果next与curr相同,则-
curr:=下一个
(增加ret1)
返回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