Rust "Trapping Rain Water" problemi nasıl çözülür?

Raldexx · 10 Temmuz 2024

Merhabalar bu problem nasıl çözülüyor? Anlatır mısınız? (Rust ile)

Problem: [Hard] Trapping Rain Water
Açıklama:
Bir dizi yükseklik (height) verilmiş, her eleman bir sütun yüksekliğini temsil eder. Yağmur yağdıktan sonra ne kadar su tutulabileceğini hesaplaman gerekiyor.
Örnek:
Girdi:
Python Kodu kopyala.
Height = [0,1,0,2,1,0,1,3,2,1,2,1]
Çıktı Python Kodu kopyala.
6
Açıklama:
Verilen yüksekliklerin oluşturduğu sütunlar arasında su tutulabilecek boşluklar şu şekilde olur:
Soldan ikinci ile üçüncü arasında 1 birim su.
Dördüncü ile altıncı arasında 1 birim su.
Altıncı ile sekizinci arasında 2 birim su.
Dokuzuncu ile on birinci arasında 2 birim su.
Toplamda 6 birim su tutulabilir..

RufatM · 10 Temmuz 2024

Raldexx dedi:
Merhabalar bu problem nasıl çözülüyor? Anlatır mısınız? (Rust ile)

Problem: [Hard] Trapping Rain Water
Açıklama:
Bir dizi yükseklik (height) verilmiş, her eleman bir sütun yüksekliğini temsil eder. Yağmur yağdıktan sonra ne kadar su tutulabileceğini hesaplaman gerekiyor.
Örnek:
Girdi:
Python Kodu kopyala.
Height = [0,1,0,2,1,0,1,3,2,1,2,1]
Çıktı Python Kodu kopyala.
6
Açıklama:
Verilen yüksekliklerin oluşturduğu sütunlar arasında su tutulabilecek boşluklar şu şekilde olur:
Soldan ikinci ile üçüncü arasında 1 birim su.
Dördüncü ile altıncı arasında 1 birim su.
Altıncı ile sekizinci arasında 2 birim su.
Dokuzuncu ile on birinci arasında 2 birim su.
Toplamda 6 birim su tutulabilir..

Kod:

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = height.len() - 1;
        let mut left_max = 0;
        let mut right_max = 0;
        let mut water = 0;
        while left < right {
            if height[left] < height[right] {
                if height[left] >= left_max {
                    left_max = height[left];
                } else {
                    water += left_max - height[left];
                }
                left += 1;
            }
            else {
                if height[right] >= right_max {
                    right_max = height[right];
                }
                else {
                    water += right_max - height[right];
                }
                right -= 1;
            }
        }
        water
    }
}

bu kod üzerinden ilerleyelim. Kodun en başından başlayalım left ilk kişi right sonuncu kişi. left_max sol taraftaki en büyük tuzak,duvar ne derseniz artık right_max ise sağ taraftaki en büyük. water ise toplam su olarak düşünebilirsin. şimdi kodun ilk kısmına bakalım if height[left] < height[right] sol taraftaki duvar sağ tarafa göre daha alçaksa o zaman bi şart daha koyuyorum ben buraya diyorum ki if height[left] >= left_max eğer ki sol tarafın uzunluğu left_max yani en büyükten büyük beraber ise o zaman left_max sol tarafın büyüklüğüne eşit olacak. He yok tam tersi sağ kısım daha büyükse o zaman suyun seviyesi suyun olabileceği maksimum yükseklik ve suyun şuanki seviyesinin çıkarması kadar artacak. Ardından yine aynı işlemi bu sefer sağ taraf için yapacağız. Sol tarafdan sağa sağ tarafdan ise sola gitmesi gerek soldan başladığı için. Bu sebepten birinde +1 derken birinde -1 diyoruz. Şimdi [0,1,0,2,1,0,1,3,2,1,2,1] bu test case ile yeniden inceleyelim. Diğer şeyler 0 olacak right 11 olacak çünki indeksin sonu olduğu için. Ilk adımda bakıyoruz şimdi

Kod:

if height[left] < height[right] {
                if height[left] >= left_max {
                    left_max = height[left];
                } else {
                    water += left_max - height[left];
                }
                left += 1;
            }

gördüğün gibi bu koda göre bakarsak height

< height

olduğu için left kısmı 1 olacak. Şimdi ikinci şarta bakalım height

>= left_max bu da doğru olacak ve left_max şuanlık 1 olduğu için left_max - height

= bu da (0 - 1 ) olacak ki buda -1 yapıyor. Left 2 oldu. Şimdi artık kodun

Kod:

if height[right] >= right_max {
                    right_max = height[right];
                }
                else {
                    water += right_max - height[right];
                }
                right -= 1;

kodun bu kısmına bakalım height

> height

doğru mu doğru demek ki right 1 azalacak 10 olacak. Şuan özet geçtim ancak mantık kısacası böyle işleyecek. height

>= left_max olacak bundan sonra 3 adım boyunca height

< height

şartı olacak sonra yeniden 3 kez height

> height

olacak.

Not:Yanlış anlatmış olabilirim , yanlışımı düzeltirseniz iyi olur.

Rust "Trapping Rain Water" problemi nasıl çözülür?

Raldexx

Centipat

RufatM

Kilopat