Bağçanı sulamaq üçün açılacaq kranların minimum sayı LeetCode Həlli

Problem bəyanat

Bağçanı Sulamaq üçün Açılacaq Kranların Minimum Sayı LeetCode Həlli – X oxunda bir ölçülü bağ var. Bağ nöqtədən başlayır 0 və nöqtədə bitir n. (yəni bağın uzunluğu n).

Var n + 1 nöqtələrdə yerləşən kranlar [0, 1, ..., n] bağda.

Bir tam verilir n və tam ədəd massivi ranges uzunluğu n + 1 hara ranges[i] (0 indeksli) deməkdir i-th kran ərazini sulaya bilər [i - ranges[i], i + ranges[i]] açıq olsaydı.

Qayıtmaq bu minimum sayı kranların Açıq olması lazım olan bütün bağçanın sulanması, Bağçanın sulanamadığı təqdirdə geri qaytarılması -1.

misal

Test işi 1:

Input:

n = 5

diapazonlar = [3, 4, 1, 1, 0, 0]

Pin

Izahat

0 nöqtəsindəki kran [-3,3] intervalını əhatə edə bilər.

1 nöqtəsindəki kran [-3,5] intervalını əhatə edə bilər.

2-ci nöqtədəki kran [1,3] intervalını əhatə edə bilər.

3-ci nöqtədəki kran [2,4] intervalını əhatə edə bilər.

4-ci nöqtədəki kran [4,4] intervalını əhatə edə bilər.

5-ci nöqtədəki kran [5,5] intervalını əhatə edə bilər.

Açılış Yalnız ikinci kran bütün bağı sulayacaq [0,5]

Yanaşma:

Birincisi, faydasız olduqları üçün bütün sıfırları aradan qaldırın. Sonra massiv bazasını birinci indeks, sonra ikinci indeks üzrə çeşidləyin. Bundan sonra, 1-ci döngədən istifadə edərək ilk kranı alırıq. Birinci toxunuşla biz ən uzaq son nöqtəsi olan növbəti kranı tapmağa çalışırıq. Növbəti kran əvvəlcədən vurma ilə üst-üstə düşməlidir. Növbəti kranı tapdıqdan sonra əvvəlki kranı yeniləyin.

Beləliklə, sual, əsasən, bütün bağı əhatə edə biləcək minimum kranları tələb edir.
Alqoritm:

1. dp[i] su üçün kranların minimum sayıdır [0, i].
   Initialize dp[i] maksimum = ilə n + 2
dp[0] = [0] çünki heç bir şeyi sulamaq üçün krana ehtiyacımız yoxdur.
2. Kranla su vermək üçün bağın ən sol nöqtəsini tapın i.
3. Kranla su vermək üçün bağın ən sağ nöqtəsini tapın i.
4. Su verə bilərik [left, right] bir toxunuşla,
   və su [0, left - 1] ilə dp[left - 1] kranlar.

Bağı Sulamaq üçün Açılacaq Kranların Minimum Sayının Kodu

Java Proqramı

class Solution {
    public int minTaps(int n, int[] A) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 2);
        dp[0] = 0;
        for (int i = 0; i <= n; ++i)
            for (int j = Math.max(i - A[i] + 1, 0); j <= Math.min(i + A[i], n); ++j)
                dp[j] = Math.min(dp[j], dp[Math.max(0, i - A[i])] + 1);
        return dp[n]  < n + 2 ? dp[n] : -1;
    }
}

C ++ Proqramı

class Solution {
public:
    int minTaps(int n, vector<int>& A) {
        vector<int> dp(n + 1, n + 2);
        dp[0] = 0;
        for (int i = 0; i <= n; ++i)
            for (int j = max(i - A[i] + 1, 0); j <= min(i + A[i], n); ++j)
                dp[j] = min(dp[j], dp[max(0, i - A[i])] + 1);
        return dp[n]  < n + 2 ? dp[n] : -1;
    }
};

Bağçanı Sulamaq üçün Açılacaq Kranların Minimum Sayı üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi: O(NR), Harada R = ranges[i] <= 100
Kosmik Mürəkkəblik: O(N)