Takip et

C++’ta Sabit Boyutlu Kayar Pencere Tekniğinde Ustalaşmak: LeetCode 1876 Örneği

Algoritma dünyasında, büyük veri kümeleri üzerinde belirli desenleri veya alt dizileri verimli bir şekilde bulmak sıkça karşılaşılan bir problem…

C++’ta Sabit Boyutlu Kayar Pencere Tekniğinde Ustalaşmak: LeetCode 1876 Örneği

Algoritma dünyasında, büyük veri kümeleri üzerinde belirli desenleri veya alt dizileri verimli bir şekilde bulmak sıkça karşılaşılan bir problem türüdür. Bu tür senaryolarda “Kayar Pencere” (Sliding Window) tekniği, özellikle diziler veya stringler üzerinde doğrusal zamanda çözümler sunarak performans açısından kritik bir rol oynar. Bu makalede, kayar pencere tekniğinin sabit boyutlu (fixed-size) versiyonuna odaklanacak, temel prensiplerini açıklayacak ve LeetCode 1876 “Substrings of Size Three with Distinct Characters” problemi üzerinden C++ ile pratik bir uygulama gerçekleştireceğiz. Bu sayede, bu güçlü algoritma paradigmasını derinlemesine anlayacak ve kendi projelerinizde nasıl kullanabileceğinizi keşfedeceksiniz.

Kayar Pencere Tekniği Nedir?

Kayar pencere tekniği, bir dizi veya string üzerinde belirli bir pencere (alt dizi veya alt string) tanımlayarak ve bu pencereyi veri üzerinde kaydırarak çalışan bir algoritma desenidir. Bu teknik, özellikle ardışık elemanlar üzerinde işlem yapılması gereken durumlarda, iç içe döngülerle oluşabilecek daha yavaş (örneğin O(N^2)) çözümlerin önüne geçerek O(N) veya O(N log N) gibi daha verimli çözümler sunar.

Tanım ve Amacı

Kayar pencere, verinin bir kısmını “görüp” üzerinde işlem yapmamızı sağlayan mantıksal bir aralıktır. Amacı, her bir olası alt diziyi veya alt stringi yeniden hesaplamak yerine, pencere bir adım kaydığında sadece giren ve çıkan elemanların etkisini dikkate alarak hesaplamaları güncellemek ve böylece tekrar eden işlemleri azaltmaktır. Bu, özellikle büyük veri setlerinde zaman karmaşıklığını önemli ölçüde düşürür.

Neden Kullanılır?

Kayar pencere tekniği, birçok problemde brute force (kaba kuvvet) yaklaşımlarının zaman aşımına uğramasına neden olan yüksek zaman karmaşıklığını aşmak için kullanılır. Örneğin, bir dizide belirli bir toplamı olan en uzun alt diziyi bulmak, bir stringdeki en uzun tekrarlamayan karakter alt stringini bulmak gibi problemler kayar pencere ile verimli bir şekilde çözülebilir. Temel faydası, hesaplamaların artımlı olarak yapılmasıdır.

Kayar Pencere Çeşitleri

Kayar pencere tekniği genellikle iki ana kategoriye ayrılır:

  • Sabit Boyutlu Kayar Pencere (Fixed-Size Sliding Window): Pencerenin boyutu baştan bellidir ve işlem boyunca değişmez. Bu makalede odaklandığımız tür budur.
  • Değişken Boyutlu Kayar Pencere (Variable-Size Sliding Window): Pencerenin boyutu, belirli bir koşul sağlanana kadar veya belirli bir hedef değere ulaşılana kadar dinamik olarak değişir.

Sabit Boyutlu Kayar Pencere Mantığı

Sabit boyutlu kayar pencere, belirli bir ‘K’ uzunluğunda bir pencereyi veri üzerinde baştan sona hareket ettirerek çalışır. Her adımda, pencerenin solundan bir eleman çıkarılır ve sağına yeni bir eleman eklenir. Bu sayede pencere içindeki elemanlar güncellenir ve ilgili hesaplamalar yeniden yapılır.

Pencere Oluşturma ve İlerleme

Pencere genellikle iki işaretçi ile temsil edilir: sol (başlangıç) ve sağ (bitiş). Başlangıçta, sağ işaretçisi K-1 indeksine kadar ilerletilerek ilk pencere oluşturulur. Daha sonra, her adımda hem sol hem de sağ işaretçileri birer birim ilerletilir. Bu, pencerenin sabit boyutunu korurken tüm veri üzerinde kaymasını sağlar.

Pencere İçindeki Elemanları Yönetme

Pencere kayarken, pencereye yeni giren elemanlar ve pencereden çıkan elemanlar olur. Bu elemanların özelliklerini (örneğin frekanslarını, toplamlarını vb.) verimli bir şekilde takip etmek için genellikle hash map’ler (std::unordered_map), frekans dizileri veya set’ler (std::set) kullanılır. Pencereden çıkan elemanın etkisi kaldırılır, giren elemanın etkisi eklenir ve ardından pencere üzerindeki koşul kontrol edilir.

Sabit Boyutlu Kayar Pencere Adımları

  1. Pencerenin sol (sol) ve sağ (sağ) işaretçilerini başlatın (genellikle sol = 0, sağ = 0).
  2. sağ işaretçisini, pencere boyutu K olana kadar ilerletin. Bu süreçte pencereye giren elemanları işleyin.
  3. İlk K elemanlık pencere oluştuğunda, gerekli hesaplamayı yapın ve sonucu kaydedin.
  4. sağ işaretçisini bir adım daha ilerletin.
  5. Pencereden çıkan elemanı (s[sol]) işleyin (örneğin frekansını azaltın).
  6. Pencereye giren yeni elemanı (s[sağ]) işleyin (örneğin frekansını artırın).
  7. sol işaretçisini bir adım ilerletin.
  8. sağ işaretçisi dizinin sonuna ulaşana kadar 4-7 adımlarını tekrarlayın.

LeetCode 1876: Problemi Anlamak

Şimdi sabit boyutlu kayar pencere tekniğini somutlaştırmak için LeetCode 1876 problemine göz atalım.

Problem Tanımı

Size bir string s veriliyor. Göreviniz, uzunluğu 3 olan “iyi” alt stringlerin sayısını bulmaktır. Bir alt string, eğer tüm karakterleri birbirinden farklı ise “iyi” olarak kabul edilir. Örneğin, “abc” iyi bir alt stringdir, ancak “aba” veya “aaa” iyi değildir.

Giriş ve Çıkış Örnekleri

  • Giriş: s = "xyzzaz"
    • “xyz” – iyi
    • “yzz” – kötü (y ve z tekrar ediyor)
    • “zza” – kötü (z tekrar ediyor)
    • “zaz” – kötü (z tekrar ediyor)

    Çıkış: 1

  • Giriş: s = "aababcabc"
    • “aab” – kötü
    • “aba” – kötü
    • “bab” – kötü
    • “abc” – iyi
    • “bca” – iyi
    • “cab” – iyi

    Çıkış: 3

Brute Force Yaklaşımı ve Neden Verimsiz Olduğu

Brute force yaklaşımında, stringdeki her olası 3 karakterlik alt stringi alırız, ardından her bir alt stringin karakterlerinin birbirinden farklı olup olmadığını kontrol ederiz. Bu, iç içe döngüler gerektirecektir:

// Brute Force (pseudo-kod)
int count = 0;
for (int i = 0; i <= s.length() - 3; ++i) {
    string sub = s.substr(i, 3);
    if (sub[0] != sub[1] && sub[0] != sub[2] && sub[1] != sub[2]) {
        count++;
    }
}
return count;

Bu yaklaşım, her alt string için üç karakteri tekrar tekrar kontrol ettiği için O(N*K) zaman karmaşıklığına sahiptir, burada N stringin uzunluğu ve K alt stringin uzunluğudur (bu problemde K=3). Büyük stringler için bu, performans sorunlarına yol açabilir.

C++ ile Sabit Kayar Pencere Uygulaması

LeetCode 1876 probleminde, pencere boyutu sabittir (K=3). Bu, sabit boyutlu kayar pencere tekniği için ideal bir senaryo sunar.

Temel Algoritma Adımları

  1. Bir sayaç (goodSubstringsCount) başlatın.
  2. sol ve sağ işaretçilerini başlatın (sol = 0, sağ = 0).
  3. String üzerinde sağ işaretçisi ile ilerleyin.
  4. Her adımda, eğer pencerenin boyutu 3'e ulaşmışsa (yani sağ - sol + 1 == 3):
    • Pencere içindeki üç karakterin (s[sol], s[sol+1], s[sağ]) birbirinden farklı olup olmadığını kontrol edin.
    • Eğer farklıysa, goodSubstringsCount değerini artırın.
    • Pencereyi bir adım sağa kaydırmak için sol işaretçisini artırın.
  5. sağ işaretçisi stringin sonuna ulaşana kadar devam edin.

Kod Örneği (LeetCode 1876 için Tam Çözüm)

Aşağıdaki C++ kodu, LeetCode 1876 problemini sabit boyutlu kayar pencere tekniği ile çözer:

#include 
#include 
#include  // Alternatif olarak kullanılabilir, ancak bu problem için gereksiz

class Solution {
public:
    int countGoodSubstrings(std::string s) {
        int n = s.length();
        if (n < 3) { // String 3 karakterden kısaysa, iyi alt string olamaz
            return 0;
        }

        int goodSubstringsCount = 0;
        
        // İlk pencereyi oluştur
        // Sol işaretçi 'i', sağ işaretçi 'i + 2' olacak şekilde
        for (int i = 0; i <= n - 3; ++i) {
            // Pencere: s[i], s[i+1], s[i+2]
            // Karakterlerin farklı olup olmadığını kontrol et
            if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) {
                goodSubstringsCount++;
            }
        }
        
        return goodSubstringsCount;
    }
};

Yukarıdaki kod, klasik kayar pencere yapısından biraz farklı görünse de, aslında aynı mantığı uygular. i değişkeni hem pencerenin solunu hem de pencerenin ilerlemesini temsil eder. i, i+1 ve i+2 her zaman sabit 3 boyutlu bir pencereyi oluşturur. Her iterasyonda, pencere bir birim sağa kayar ve karakter kontrolü yapılır.

Karakter Frekanslarını Takip Etme (Genel Durum)

LeetCode 1876'da pencere boyutu çok küçük (3) olduğu için karakter frekanslarını takip etmek yerine doğrudan karşılaştırma yapmak daha basittir. Ancak daha genel kayar pencere problemlerinde, pencere içindeki elemanların frekanslarını veya diğer özelliklerini takip etmek için std::unordered_map veya std::vector (ASCII karakterler için) kullanmak yaygındır. Örneğin, pencereye giren karakterin frekansını artırır, çıkan karakterin frekansını azaltırız.

// Daha genel bir kayar pencere yapısı (frekans takibi ile)
// Sadece örnek amaçlıdır, LeetCode 1876 için overkill
// int k = 3;
// std::unordered_map char_counts;
// int distinct_chars = 0;
// int good_substrings = 0;

// for (int right = 0; right < s.length(); ++right) {
//     char_counts[s[right]]++;
//     if (char_counts[s[right]] == 1) { // Yeni bir farklı karakter
//         distinct_chars++;
//     }

//     if (right >= k - 1) { // Pencere boyutu k'ye ulaştı
//         if (distinct_chars == k) { // Tüm karakterler farklı mı?
//             good_substrings++;
//         }

//         // Pencereyi kaydır: soldaki karakteri çıkar
//         char_counts[s[right - (k - 1)]]--;
//         if (char_counts[s[right - (k - 1)]] == 0) { // Karakter pencereden tamamen çıktı
//             distinct_chars--;
//         }
//     }
// }
// return good_substrings;

Bu genel yapı, daha karmaşık "farklı karakter sayısı K olan en uzun alt dizi" gibi problemler için daha uygundur.

Performans Analizi ve Optimizasyon

Kayar pencere tekniği, genellikle optimal zaman karmaşıklığına sahip çözümler sunar.

Zaman Karmaşıklığı (Time Complexity)

LeetCode 1876 problemindeki kayar pencere çözümümüz, string üzerinde sadece tek bir geçiş yapar. Her adımda sabit sayıda işlem (3 karakterin karşılaştırılması) gerçekleştirilir. Bu nedenle, zaman karmaşıklığı O(N)'dir, burada N stringin uzunluğudur. Bu, stringin boyutu ne kadar büyük olursa olsun oldukça verimli bir yaklaşımdır.

Uzay Karmaşıklığı (Space Complexity)

Çözümümüz, herhangi bir ek veri yapısı (hash map, set vb.) kullanmaz; sadece birkaç tamsayı değişkeni kullanırız. Bu nedenle, uzay karmaşıklığı O(1)'dir. Bu da hafıza kullanımı açısından oldukça verimli olduğu anlamına gelir.

Brute Force vs. Kayar Pencere Karşılaştırması

Daha önce bahsettiğimiz brute force yaklaşımı O(N*K) zaman karmaşıklığına sahipti. K=3 olduğu için bu O(3N) yani yine O(N) gibi görünse de, aslında her alt string için ayrı bir substr çağrısı ve karakter karşılaştırması yapar. Kayar pencere yaklaşımı ise her bir karakteri yalnızca bir kez (veya sabit sayıda kez) ziyaret eder ve işler. Bu nedenle, sabit bir K değeri için her ikisi de asimptotik olarak O(N) olsa da, kayar pencere yaklaşımı pratik uygulamalarda çok daha hızlıdır çünkü sabit katsayıları daha düşüktür.

Daha Fazla Optimizasyon İpuçları

LeetCode 1876 için çözüm zaten oldukça optimize edilmiş durumda. Ancak, daha genel kayar pencere problemlerinde:

  • Karakter frekanslarını takip etmek için std::unordered_map yerine, karakter seti küçük ve biliniyorsa (örneğin sadece küçük harfler) std::vector veya int[26] boyutunda bir dizi kullanmak daha hızlı olabilir.
  • Pencere içindeki durumu (örneğin farklı karakter sayısı) güncellerken gereksiz kontrollerden kaçının.

Kayar Pencere Tekniğinin Diğer Uygulama Alanları

Kayar pencere tekniği, sadece LeetCode 1876 gibi basit problemlerle sınırlı değildir. Birçok farklı senaryoda güçlü bir araç olarak karşımıza çıkar.

Maksimum/Minimum Toplamlı Alt Dizi Bulma

Belirli bir uzunluktaki (K) alt dizilerin toplamını bulmak ve bu toplamların maksimumunu veya minimumunu belirlemek kayar pencerenin klasik bir uygulamasıdır. Pencere kayarken, çıkan elemanın değeri toplamdan çıkarılır, giren elemanın değeri toplama eklenir.

Belirli Bir K Karakterli En Uzun Alt Dizi

Bir stringde en fazla K farklı karaktere sahip en uzun alt stringi bulma gibi problemler değişken boyutlu kayar pencere ile çözülür. Burada pencere boyutu dinamik olarak ayarlanır.

Anagram Problemleri

Bir stringin içinde başka bir stringin anagramlarını (aynı karakterlere sahip farklı sıralanmış hali) bulmak için kayar pencere ve frekans haritaları birlikte kullanılabilir. Pencere boyutu aranılan anagramın uzunluğu kadar sabit tutulur.

Veri Akışı İşleme

Gerçek zamanlı veri akışlarında, son 'N' saniye içindeki ortalama sıcaklık, son 'M' gelen paketin ortalama boyutu gibi metrikleri hesaplamak için kayar pencere mantığı kullanılır. Bu, büyük veri kümeleri üzerinde sürekli güncellenen istatistikler sağlamak için idealdir.

Sonuç

Sabit boyutlu kayar pencere tekniği, diziler ve stringler üzerinde çalışan algoritmik problemler için vazgeçilmez bir araçtır. LeetCode 1876 örneği üzerinden gördüğümüz gibi, bu teknik brute force yaklaşımlarına kıyasla önemli ölçüde daha verimli çözümler sunar. O(N) zaman ve O(1) uzay karmaşıklığı ile, büyük veri setlerinde bile hızlı ve kaynak dostu uygulamalar geliştirmemizi sağlar. Bu tekniği kavramak, algoritmik düşünme yeteneğinizi geliştirecek ve daha karmaşık rekabetçi programlama sorunlarını çözme konusunda size büyük avantaj sağlayacaktır. Unutmayın, pratik yapmak ve farklı kayar pencere problemlerini denemek, bu tekniğe gerçekten hakim olmanın anahtarıdır.

SSS (Sık Sorulan Sorular)

Kayar pencere her zaman daha mı hızlıdır?

Evet, genellikle kayar pencere tekniği, aynı problemi çözen brute force (kaba kuvvet) yaklaşımlarına göre asimptotik olarak daha hızlı veya en azından aynı asimptotik karmaşıklıkta çok daha düşük sabit katsayılara sahiptir. Bu, özellikle büyük veri setlerinde performans farkını belirgin hale getirir.

Sabit ve değişken boyutlu kayar pencere arasındaki fark nedir?

Sabit boyutlu kayar pencerede, pencerenin uzunluğu (K) baştan belirlenir ve işlem boyunca değişmez. Değişken boyutlu kayar pencerede ise, pencerenin boyutu belirli bir koşul sağlanana veya bir hedefe ulaşılana kadar dinamik olarak genişler veya daralır.

Hangi durumlarda kayar pencere kullanmalıyım?

Kayar pencere tekniğini, bir dizi veya stringin ardışık alt dizileri veya alt stringleri üzerinde belirli bir koşulu (örneğin maksimum toplam, belirli sayıda farklı karakter, anagram varlığı) kontrol etmeniz gerektiğinde kullanmalısınız. Genellikle "en uzun", "en kısa", "sayısını bul" gibi ifadeler içeren problemler bu tekniğe işaret edebilir.

Kayar pencere problemlerinde en sık yapılan hatalar nelerdir?

En sık yapılan hatalar arasında pencere sınırlarını yanlış ayarlamak (sol ve sağ işaretçilerinin doğru ilerletilmemesi), pencereye giren ve çıkan elemanların etkisini doğru bir şekilde güncelleyememek ve kenar durumları (boş string, pencere boyutundan küçük stringler) gözden kaçırmak yer alır.

Yorumlar
İçeriği beğendiniz mi? Bir tartışma başlatın veya görüşlerinizi paylaşın.
Yorum Yaz

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

E-posta Bülteni
Yazılım Topluluğuna Katılın
En son güncellemeleri, yaratıcı ipuçlarını ve özel kaynakları doğrudan e-posta kutunuza alın. Tasarım ve inovasyonun geleceğini birlikte keşfedelim.