Yağış suyunun tutulması Leetcode həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit Çiy kərpic Airbnb Amazon alma Bloomberg ByteDance Cisco Citadel Verilənlər bazası DE Şou eBay Expedia Facebook Flipkart Goldman Sachs google Ağır Intel Intuit lyft microsoft Morgan Stanley Kahin PayPal İctimai Sapient Kvalifikasiya bölmə XidmətNow Snapchat Swiggy Tesla Twitch cuqquldamaq Über Viza VMware Yahoo Zenefits Zoho
Geyim Dinamik proqramlaşdırma Qalaq tiktok İki işarə Walmart Qlobal texnologiyaBaxılıb 108

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Yağış suyunun tutulması LeetCode Həlli - “Yağış suyunu tutmaq” hər bir çubuğun eninin 1 olduğu yüksəklik xəritəsini təmsil edən yüksəkliklər massivinin verildiyini bildirir. Biz yağışdan sonra tutulan suyun miqdarını tapmalıyıq.

Misal:

Yağış suyunun tutulması Leetcode həlliPin

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation:

  • Daha yaxşı başa düşmək üçün yuxarıdakı diaqramı yoxlayın.
  • Mavi hissə tutulan suyun miqdarını bildirir.
Input:  height = [4,2,0,3,2,5]
Output: 9

Explanation:

  • Ümumilikdə 9 vahid su tələyə düşüb.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir dinamik proqramlaşdırma.
  2. tapmaq lazımdır tutulan su miqdarı yağışdan sonra.
  3. Biz hər 1 vahid bar üçün yuxarıda tutulan suyun miqdarını tapacağıq və hər bir çubuq üçün tutulan bütün suyun ümumiləşdirilməsini edəcəyik.
  4. İndi hər bir bar üçün var iki hal:
    1. Nəzərə alın ki, hər iki tərəfdəki hər çubuğun hündürlüyü var az və ya bərabərdir çubuğun cari hündürlüyünə.
    2. Nəzərə alın ki, hər iki tərəfdə hündürlüyü olan ən azı 1 bar var ciddi şəkildə daha böyükdür çubuğun cari hündürlüyündən çoxdur.
  5. Üçün birinci halda, orada deməliyik heç bir su tələyə düşməyəcək cari çubuğun hər iki tərəfdəki bütün çubuqlardan daha yüksək hündürlüyə malik olduğundan, cari çubuğun üstündə.
  6. Üçün ikinci hal, tutmuş suyun miqdarı bərabərdir min(H1, H2) – H, burada H1 sol tərəfdə olan çubuqların maksimum hündürlüyü, H2 sağ tərəfdə mövcud olan çubuqların maksimum hündürlüyü, H isə çubuğun cari hündürlüyüdür.
  7. Hesablayın Maksimum Prefiks və Suffiks Cəmi, bu, hər bir çubuğun üstündə sıxılmış suyun miqdarını sabit vaxtda tapmağa kömək edir.
  8. İndi hər bir bar üçün cavabı əlavə edin min(H1, H2) – H, burada H1 və H2 müvafiq olaraq prefiks və şəkilçi cəmindən asanlıqla əldə edilə bilər.

Kodu

Yağış suyunun tutulması C++ Həlli:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pref(height.begin(),height.end());
        vector<int> suff(height.begin(),height.end());
        for(int i=1;i<n;i++){
            pref[i] = max(pref[i],pref[i-1]);
        }
        for(int i=n-2;i>=0;i--){
            suff[i] = max(suff[i],suff[i+1]);
        }
        int ans = 0;
        for(int i=1;i<n-1;i++){
            ans += max(0,min(pref[i-1],suff[i+1])-height[i]);
        }
        return ans;
    }
};

Yağış suyunun tutulması Java Həlli:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] pref = new int[n];
        int[] suff = new int[n];
        for(int i=0;i<n;i++){
            pref[i] = height[i];
            if(i>0){
                pref[i] = Math.max(pref[i],pref[i-1]);
            }
        }
        for(int i=n-1;i>=0;i--){
            suff[i] = height[i];
            if(i+1<n){
                suff[i] = Math.max(suff[i],suff[i+1]);
            }
        }
        int ans = 0;
        for(int i=1;i<n-1;i++){
            ans += Math.max(0,Math.min(pref[i-1],suff[i+1])-height[i]);
        }
        return ans;
    }
}

Yağış suyunun tutulması üçün mürəkkəblik təhlili Leetcode həlli

Zamanın mürəkkəbliyi

The zaman mürəkkəbliyi yuxarıdakı koddur O (N) bütün giriş massivini ən çox 3 dəfə keçdiyimiz üçün.

Kosmik Mürəkkəblik

The kosmik mürəkkəblik yuxarıdakı koddur O (N). Maksimum hündürlükləri prefiks və şəkilçi saxlamaq üçün əlavə N ölçülü massivdən istifadə edirik.

Crack Sistemi Dizayn Müsahibələri
Translate »