x축에 1차원 정원이 있다고 가정합니다. 정원의 시작 위치는 0이고 끝 위치는 n입니다. 정원의 [0, 1, ..., n] 지점에 n + 1개의 탭이 있습니다. 우리가 정수 n과 길이 n + 1의 정수 배열 범위가 있고 여기서 범위[i]는 i번째 수돗물이 될 수 있습니다. [i - 범위[i], i + 범위[i]] 엽니다.
정원 전체에 물을 공급할 수 있는 최소 수도꼭지 수를 찾아야 합니다. 가능한 솔루션이 없으면 -1을 반환합니다.
따라서 입력이 n =5이고 범위 =[3,4,1,1,1,0]인 경우 출력은 1이 됩니다. 두 번째 탭에서와 같이 전체 접지 [-3 5까지].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
크기(n + 1)의 배열 v를 정의하고 -1로 채웁니다.
-
i:=0 초기화의 경우, i <=n일 때 업데이트(i를 1만큼 증가), -
수행-
u :=i의 최대값 - 범위[i] 및 0
-
e :=n 및 i + 범위의 최소값[i]
-
v[u] :=v[u] 및 e의 최대값
-
-
v[0]이 -1과 같으면 -
-
반환 -1
-
-
커 :=v[0]
-
나는 :=0, 다음 :=0
-
curr
-
내가 <=curr, 하는 동안 -
-
다음 :=다음 및 v[i]
의 최대값 -
(i를 1씩 증가)
-
-
다음이 curr과 같으면 -
-
반환 -1
-
-
curr :=다음
-
(ret 1 증가)
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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