Başlangıç Dostu Rehber: LeetCode 3453 – ‘Separate Squares I’ Problemi (C++, Python, JavaScript)

Başlangıç Dostu Rehber: LeetCode 3453 – ‘Separate Squares I’ Problemi (C++, Python, JavaScript)

Programlama dünyasına yeni adım atanlar veya algoritma becerilerini geliştirmek isteyenler için LeetCode gibi platformlar paha biçilmez kaynaklardır. Bu rehberde, “Separate Squares I” olarak adlandırılan ve LeetCode 3453 numaralı problemi inceleyeceğiz. Bu problem, temel dizi manipülasyonu ve koşullu mantık becerilerini pekiştirmek için harika bir başlangıç noktasıdır. Amacımız, bu problemi adım adım anlayıp, C++, Python ve JavaScript dillerinde etkili çözümler sunarak konuya tamamen hakim olmanızı sağlamaktır.

Problemi Anlamak: LeetCode 3453 Nedir?

LeetCode 3453, “Separate Squares I” problemi, size verilen bir negatif olmayan tam sayılar dizisini belirli bir kurala göre yeniden düzenlemenizi ister. Bu kural, dizideki tüm tam kare sayıların, tam kare olmayan sayılardan önce gelmesini sağlamaktır. Önemli bir detay ise, tam kare sayılar kendi aralarında ve tam kare olmayan sayılar kendi aralarında göreceli sıralarını korumalıdır. Bu, problemin “stabil” bir sıralama veya bölme gerektirdiğini gösterir.

Neden ‘Separate Squares I’?

Bu tür problemler, genellikle daha karmaşık algoritmaların temelini oluşturur. “Separate Squares I” adlandırması, muhtemelen bu konunun ilk ve en basit versiyonu olduğunu ima eder. Bu problemi çözmek, diziler üzerinde iterasyon yapma, koşullu kontrol (bir sayının tam kare olup olmadığını belirleme) ve yeni bir dizi oluşturma gibi temel becerileri geliştirmenize yardımcı olur.

Problem Kategorisi: Diziler ve Bölme (Partitioning)

LeetCode 3453, temel olarak dizi manipülasyonu ve bölme (partitioning) kategorisine girer. Bir diziyi belirli bir kritere göre iki veya daha fazla bölüme ayırmak, birçok algoritma probleminde karşılaşılan yaygın bir senaryodur. Bu problemde kriterimiz, sayının tam kare olup olmamasıdır.

Hedef Kitle: Başlangıç Seviyesi Geliştiriciler

Bu rehber, özellikle algoritma ve veri yapılarına yeni başlayan, temel programlama bilgisine sahip ancak LeetCode problemlerine nasıl yaklaşacağını bilemeyen geliştiriciler için tasarlanmıştır. Karmaşık algoritmalar yerine, anlaşılması kolay ve verimli bir çözüm sunacağız.

Problem Tanımı ve Örnekler

Problemi daha iyi anlamak için girdi, çıktı formatlarını ve bazı örnek senaryoları inceleyelim.

Girdi ve Çıktı Formatı

* Girdi: Negatif olmayan tam sayılardan oluşan bir dizi (örneğin, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).
* Çıktı: Tam kare sayıların başta, tam kare olmayan sayıların sonda olduğu ve her iki grupta da göreceli sıranın korunduğu yeniden düzenlenmiş bir dizi.

Örnek 1: Basit Senaryo

* Girdi: nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
* Açıklama:
* Tam kare sayılar: 1 (1*1), 4 (2*2), 9 (3*3)
* Tam kare olmayan sayılar: 2, 3, 5, 6, 7, 8, 10
* Çıktı: [1, 4, 9, 2, 3, 5, 6, 7, 8, 10]
* Dikkat edin, 1, 4, 9 kendi aralarında (girdideki gibi) sıralarını korudu.
* 2, 3, 5, 6, 7, 8, 10 kendi aralarında (girdideki gibi) sıralarını korudu.

Örnek 2: Köşe Durumlar

* Girdi: nums = [2, 3, 5, 7, 11] (Hiç tam kare yok)
* Çıktı: [2, 3, 5, 7, 11] (Sıra değişmez)

* Girdi: nums = [1, 4, 9, 16] (Hepsi tam kare)
* Çıktı: [1, 4, 9, 16] (Sıra değişmez)

* Girdi: nums = [] (Boş dizi)
* Çıktı: [] (Boş dizi)

Kısıtlamalar

* Dizinin uzunluğu 0 <= N <= 10^5 olabilir.
* Dizideki her eleman 0 <= nums[i] <= 10^9 olabilir.
* 0 bir tam karedir (0*0 = 0).

İlk Yaklaşımlar ve Düşünce Süreci

Bir problemle karşılaştığınızda, hemen en optimal çözümü bulmaya çalışmak yerine, önce basit ve anlaşılır bir yaklaşımla başlamak faydalıdır.

Brute Force (Kaba Kuvvet) Yaklaşımı

Bu problem için "kaba kuvvet" olarak adlandırabileceğimiz bir yaklaşım, her elemanı tek tek kontrol edip, tam kare olanları bir listeye, tam kare olmayanları başka bir listeye eklemek ve sonra bu iki listeyi birleştirmektir.

1. Boş bir tamKareler listesi oluştur.
2. Boş bir tamKareOlmayanlar listesi oluştur.
3. Girdi dizisindeki her sayı için:
* Sayı tam kare mi diye kontrol et. (Bir sayının tam kare olup olmadığını anlamak için, karekökünü alıp tam sayı olup olmadığını kontrol edebiliriz.)
* Eğer tam kare ise, tamKareler listesine ekle.
* Değilse, tamKareOlmayanlar listesine ekle.
4. tamKareler listesini tamKareOlmayanlar listesinin önüne ekleyerek yeni bir sonuç dizisi oluştur ve döndür.

Brute Force'un Dezavantajları (Bu Problem İçin Değil)

Aslında, bu problem için yukarıdaki "kaba kuvvet" olarak adlandırdığımız yaklaşım, hem basitliği hem de verimliliği nedeniyle oldukça optimaldir. Çoğu problemde kaba kuvvet çözümleri çok yavaş veya bellek tüketimi açısından verimsiz olabilirken, bu problemde O(N) zaman karmaşıklığına ve O(N) uzay karmaşıklığına sahip olduğu için kabul edilebilir bir çözümdür. "Brute force" terimi burada, en basit ve direkt yolu ifade etmek için kullanılmıştır.

Daha Verimli Bir Yola İhtiyaç (Bu Problem İçin Gerekli Değil)

Eğer problem, ekstra bellek kullanımına izin vermeseydi (yani yerinde, in-place bir çözüm isteseydi) veya elemanların göreceli sırasını koruma şartı olmasaydı, iki işaretçi (two-pointer) gibi farklı teknikler düşünmemiz gerekebilirdi. Ancak bu problemde, göreceli sırayı koruma ve yeni bir dizi oluşturma izni, iki geçişli (two-pass) bu yöntemi en uygun hale getiriyor.

Optimal Çözüm: Algoritma Tasarımı

Yukarıda bahsettiğimiz iki geçişli yaklaşım, bu problem için hem anlaşılır hem de optimal bir çözümdür. Şimdi bu algoritmayı daha detaylı inceleyelim.

İki Geçişli (Two-Pass) Yaklaşım

Bu yaklaşım, diziyi iki kez tarayarak istenen sonucu elde eder.

1. Tam Kareleri Toplama: Diziyi baştan sona bir kez tararız. Karşılaştığımız her tam kare sayıyı yeni bir sonuç dizisine ekleriz.
2. Tam Kare Olmayanları Toplama: Diziyi tekrar baştan sona tararız. Bu sefer, karşılaştığımız her tam kare olmayan sayıyı sonuç dizisinin sonuna ekleriz.

Bu yöntem, her iki gruptaki (tam kareler ve tam kare olmayanlar) elemanların göreceli sırasını korur çünkü elemanlar orijinal dizide göründükleri sırayla eklenir.

Bir Sayının Tam Kare Olup Olmadığını Belirleme

Bir sayının tam kare olup olmadığını anlamak için en yaygın yöntemlerden biri şudur:
1. Sayının karekökünü al.
2. Karekökün bir tam sayı olup olmadığını kontrol et.

Örneğin, Python'da int(math.sqrt(num)) ** 2 == num şeklinde kontrol edebiliriz. C++ ve JavaScript'te de benzer mantıkla sqrt fonksiyonunu kullanabiliriz. 0 sayısının da bir tam kare olduğunu unutmayın (0 * 0 = 0).

Algoritma Adımları

1. isPerfectSquare(num) adında bir yardımcı fonksiyon tanımlayın. Bu fonksiyon, num'un tam kare olup olmadığını true veya false olarak döndürecektir.
* Eğer num < 0 ise, false döndür (problem negatif sayıları içermese de iyi bir pratik).
* Eğer num == 0 ise, true döndür.
* root = round(sqrt(num)) hesapla. round kullanmak, kayan nokta hassasiyet hatalarını minimize etmeye yardımcı olabilir.
* root * root == num ise true, aksi takdirde false döndür.
2. Boş bir result dizisi oluşturun.
3. Girdi nums dizisindeki her n elemanı için:
* Eğer isPerfectSquare(n) true ise, n'i result dizisine ekle.
4. Girdi nums dizisindeki her n elemanı için (ikinci geçiş):
* Eğer isPerfectSquare(n) false ise, n'i result dizisine ekle.
5. result dizisini döndür.

Örnek Üzerinden Adım Adım İnceleme

Girdi: nums = [1, 2, 3, 4, 5]

1. result = []
2. Birinci Geçiş (Tam Kareler):
* n = 1: isPerfectSquare(1) -> true. result = [1]
* n = 2: isPerfectSquare(2) -> false.
* n = 3: isPerfectSquare(3) -> false.
* n = 4: isPerfectSquare(4) -> true. result = [1, 4]
* n = 5: isPerfectSquare(5) -> false.
* Birinci geçiş sonunda: result = [1, 4]
3. İkinci Geçiş (Tam Kare Olmayanlar):
* n = 1: isPerfectSquare(1) -> true. (Bu zaten eklendi, atla)
* n = 2: isPerfectSquare(2) -> false. result = [1, 4, 2]
* n = 3: isPerfectSquare(3) -> false. result = [1, 4, 2, 3]
* n = 4: isPerfectSquare(4) -> true. (Bu zaten eklendi, atla)
* n = 5: isPerfectSquare(5) -> false. result = [1, 4, 2, 3, 5]
4. Döndürülen sonuç: [1, 4, 2, 3, 5]

Kod Örnekleri: C++, Python, JavaScript

Şimdi bu algoritmayı üç farklı dilde nasıl uygulayabileceğimize bakalım.

C++ Çözümü

#include 
#include 
#include  // Sadece test amaçlı, çözümde kullanılmaz

class Solution {
public:
    // Bir sayının tam kare olup olmadığını kontrol eden yardımcı fonksiyon
    bool isPerfectSquare(int num) {
        if (num < 0) {
            return false; // Negatif sayılar tam kare olamaz
        }
        if (num == 0) {
            return true; // 0 bir tam karedir (0*0)
        }
        long long root = round(sqrt(num)); // round kullanmak hassasiyet hatalarını azaltır
        return root * root == num;
    }

    std::vector separateSquares(std::vector& nums) {
        std::vector result;
        result.reserve(nums.size()); // Bellek tahsisini optimize et

        // Birinci geçiş: Tam kareleri topla
        for (int num : nums) {
            if (isPerfectSquare(num)) {
                result.push_back(num);
            }
        }

        // İkinci geçiş: Tam kare olmayanları topla
        for (int num : nums) {
            if (!isPerfectSquare(num)) {
                result.push_back(num);
            }
        }

        return result;
    }
};

// Örnek kullanım (main fonksiyonu LeetCode'da yoktur, test amaçlıdır)
/*
#include 
int main() {
    Solution sol;
    std::vector nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector result = sol.separateSquares(nums);
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl; // Çıktı: 1 4 9 2 3 5 6 7 8 10
    return 0;
}
*/

Python Çözümü

import math

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 0:
            return False
        if num == 0:
            return True
        
        # Karekökünü alıp tam sayı olup olmadığını kontrol et
        # int() fonksiyonu ondalık kısmı atar
        root = int(math.sqrt(num))
        return root * root == num

    def separateSquares(self, nums: list[int]) -> list[int]:
        result = []
        
        # Birinci geçiş: Tam kareleri topla
        for num in nums:
            if self.isPerfectSquare(num):
                result.append(num)
        
        # İkinci geçiş: Tam kare olmayanları topla
        for num in nums:
            if not self.isPerfectSquare(num):
                result.append(num)
                
        return result

# Örnek kullanım
# sol = Solution()
# nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# print(sol.separateSquares(nums)) # Çıktı: [1, 4, 9, 2, 3, 5, 6, 7, 8, 10]

JavaScript Çözümü

class Solution {
    /**
     * Bir sayının tam kare olup olmadığını kontrol eder.
     * @param {number} num
     * @return {boolean}
     */
    isPerfectSquare(num) {
        if (num < 0) {
            return false;
        }
        if (num === 0) {
            return true;
        }
        
        // Math.sqrt() karekökü verir, Math.round() yuvarlar
        const root = Math.round(Math.sqrt(num));
        return root * root === num;
    }

    /**
     * Diziyi tam kare ve tam kare olmayan sayılar olarak ayırır.
     * @param {number[]} nums
     * @return {number[]}
     */
    separateSquares(nums) {
        const result = [];
        
        // Birinci geçiş: Tam kareleri topla
        for (const num of nums) {
            if (this.isPerfectSquare(num)) {
                result.push(num);
            }
        }
        
        // İkinci geçiş: Tam kare olmayanları topla
        for (const num of nums) {
            if (!this.isPerfectSquare(num)) {
                result.push(num);
            }
        }
        
        return result;
    }
}

// Örnek kullanım
// const sol = new Solution();
// const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
// console.log(sol.separateSquares(nums)); // Çıktı: [1, 4, 9, 2, 3, 5, 6, 7, 8, 10]

Zaman ve Uzay Karmaşıklığı Analizi

Bir algoritmanın performansını değerlendirmek için zaman ve uzay karmaşıklıklarını analiz etmek önemlidir.

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

* isPerfectSquare fonksiyonu: sqrt işlemi genellikle O(log N) veya sabit zamanlı (işlemci mimarisine göre) kabul edilir. Burada her çağrıda sabit bir iş yapıldığı varsayılabilir.
* Ana separateSquares fonksiyonu: Diziyi iki kez tarıyoruz. Her tarama N eleman içerir. Her eleman için isPerfectSquare fonksiyonu çağrılır.
* Dolayısıyla, toplam zaman karmaşıklığı O(N)'dir, burada N dizinin uzunluğudur. Bu, dizinin boyutuyla doğrusal olarak artan bir performanstır ve büyük diziler için oldukça verimlidir.

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

* Yeni bir result dizisi oluşturuyoruz ve bu dizi orijinal dizideki tüm elemanları içeriyor.
* Bu nedenle, uzay karmaşıklığı O(N)'dir, burada N dizinin uzunluğudur.

Neden Optimal?

Bu çözüm, zaman karmaşıklığı açısından optimaldir çünkü dizideki her elemanı en az bir kez (hatta iki kez) kontrol etmemiz gerekmektedir. O(N)'den daha iyi bir zaman karmaşıklığı (örneğin O(log N) veya O(1)) bu problem için mümkün değildir, çünkü tüm elemanları incelemeden doğru bir bölme yapamayız. Uzay karmaşıklığı açısından da, göreceli sırayı koruma şartı ve yerinde (in-place) bir çözümün genellikle daha karmaşık olması nedeniyle, O(N) ek alan kullanmak "başlangıç dostu" bir problem için kabul edilebilir ve pratiktir.

Ekstra İpuçları ve En İyi Pratikler

LeetCode problemlerini çözerken ve genel olarak kod yazarken dikkat etmeniz gereken bazı noktalar:

Test Durumları Oluşturma

Kendi test durumlarınızı oluşturmak, kodunuzdaki hataları bulmanıza yardımcı olur.
* Boş dizi []
* Hepsi tam kare olan dizi [1, 4, 9]
* Hiç tam kare olmayan dizi [2, 3, 5]
* Karışık dizi [0, 1, 2, 3, 4]
* Büyük sayılar içeren dizi [100000000, 99999999, 400000000]

Kod Okunabilirliği ve Yorumlar

Kodunuzu başkalarının (veya gelecekteki sizin) kolayca anlayabileceği şekilde yazın. Anlaşılır değişken isimleri kullanın ve karmaşık mantık kısımlarını açıklayan yorumlar ekleyin.

LeetCode'da Pratik Yapma

* Zorluk Seviyeleri: Başlangıç seviyesi problemlerle başlayın ve yavaş yavaş zorluk seviyesini artırın.
* Çeşitlilik: Farklı problem kategorilerinden (diziler, stringler, ağaçlar, grafikler vb.) problemler çözmeye çalışın.
* Tartışma Bölümü: Bir problemi çözdükten sonra, diğer kullanıcıların çözümlerini ve tartışmaları okuyun. Bu, farklı yaklaşımları öğrenmek için harika bir yoldur.

Sonuç

"Separate Squares I" (LeetCode 3453) problemi, temel dizi manipülasyonu, koşullu mantık ve algoritma analizi becerilerinizi geliştirmek için mükemmel bir başlangıç noktasıdır. İki geçişli, yardımcı bir fonksiyon kullanan çözümümüz, hem anlaşılır hem de zaman ve uzay karmaşıklığı açısından optimaldir. C++, Python ve JavaScript dillerinde sunduğumuz örnekler, bu konsepti farklı programlama ortamlarında nasıl uygulayabileceğinizi göstermektedir. Bu tür problemleri çözerek, daha karmaşık algoritma zorluklarına hazırlanmak için sağlam bir temel oluşturursunuz. Unutmayın, pratik yapmak ve farklı çözümleri keşfetmek, bir programcı olarak gelişmenin anahtarıdır.

SSS (Sık Sorulan Sorular)

Bu problemi neden çözmeliyim?

Bu problem, diziler üzerinde iterasyon yapma, koşullu mantık uygulama ve bir diziyi belirli bir kritere göre bölme gibi temel programlama becerilerini pekiştirir. Ayrıca, algoritma karmaşıklığı analizi yapma yeteneğinizi geliştirir.

Daha karmaşık 'Separate Squares' problemleri var mı?

Evet, genellikle "I" eki, bu serinin ilk ve en basit problemi olduğunu gösterir. Daha karmaşık versiyonları, örneğin yerinde (in-place) çözüm gerektirebilir, belirli bir zaman veya uzay karmaşıklığı hedefleyebilir veya farklı bölme kriterleri içerebilir.

İki işaretçi tekniği başka nerelerde kullanılır?

İki işaretçi (Two-Pointer) tekniği, sıralı dizilerde eleman arama, dizileri birleştirme, palindrom kontrolü, belirli bir toplamı veren çiftleri bulma gibi birçok problemde yaygın olarak kullanılır. Bu problemde göreceli sıra koruma ve yeni dizi oluşturma izni olduğu için iki geçişli yaklaşım daha uygun olsa da, in-place çözümlerde iki işaretçi vazgeçilmezdir.

LeetCode'da yeni başlayanlar için başka hangi problemleri önerirsiniz?

Yeni başlayanlar için LeetCode'da "Two Sum" (1), "Valid Parentheses" (20), "Merge Two Sorted Lists" (21), "Remove Duplicates from Sorted Array" (26) gibi problemler oldukça popüler ve öğreticidir. Bu problemler, farklı temel veri yapıları ve algoritmik yaklaşımlar hakkında fikir verir.