資料結構
網路
關係資料庫管理系統 (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
廣告