Temel LeetCode algoritma probleminin 65. bölümü: çok önemli bir veri yapısı-dörtlü ağaç
Algoritmalar hakkında çok karmaşık makaleler nasıl yazılır. Son olarak, yazmaya en basit seviyeden başlamanın daha iyi olacağını düşünüyorum. Başlangıçtan itibaren, yapay zeka, makine öğrenimi algoritmaları ve çok sayıda matematik ve optimizasyon bilgisi gibi bazı ağır ağırlıklara sahip olacağım. Sanırım çok bunaltıcı olacak. Bunu yapamayabilirim, doğru.
Her soruya iki dilde, bir statik dil ve bir dinamik dilde çözüm getirmeyi planlıyorum.
Uygulama dilleri olarak C dili, Python ve Java'yı seçiyorum.Kısıtlı alan nedeniyle, diğer dilleri uygulamakla ilgilenen arkadaşlar, lütfen kendiniz deneyin.
LeetCode 427. Dörtlü Ağaç Oluşturun
Sorun Açıklaması:
N x N Boolean ağını depolamak için dörtlü ağaç kullanmak istiyoruz. Ağdaki her hücrenin değeri yalnızca doğru veya yanlış olacaktır. Ağacın kök düğümü, tüm ağı temsil eder. Her düğüm için, bu alandaki değerlerin tümü aynı olana kadar dört alt düğüme bölünecektir.
Her düğümün iki başka Boole değişkeni vardır: isLeaf ve val. isLeaf, bu düğüm bir yaprak düğüm olduğunda doğrudur. Val değişkeni, yaprak düğüm tarafından temsil edilen alanın değerini depolar.
Göreviniz, belirli bir ağı temsil etmek için bir dörtlü ağaç kullanmaktır.
Not:
Misal:
Aşağıdaki örnek, bu sorunu anlamanıza yardımcı olacaktır:
Aşağıdaki 8 x 8 ağı göz önüne alındığında, buna benzer bir dörtlü ağaç oluşturacağız:
Karşılık gelen dörtlü ağaç aşağıdaki gibi görünmelidir, her düğüm bir çift (isLeaf, val) ile temsil edilir.
Yaprak olmayan düğümler için val keyfi olabilir, bu nedenle bunun yerine * kullanın.
C ++ dil uygulaması:
Quadtree çok önemli bir veri yapısı, daha önce duymadıysanız şimdi hatırlayın. Genellikle görüntü işleme gibi iki boyutlu verilerde kullanılır ve verileri temsil etmek veya sıkıştırmak için kullanılabilir. Tanınmış HEVC / H.265 standardı, görüntüleri kodlamak ve çözmek için bir dörtlü ağaç kullanır. Görüntülere ek olarak, dörtlü ağaçlar özellikle seyrek verilerin temsili için iki boyutlu veri olarak temsil edilebilen diğer nesneler için kullanılabilir.
Şimdi konu başındayız.
Örnekte verilen çizelge zaten çok açık, bunun tipik bir özyinelemeli süreç olduğunu bulacağız, bunu özyinelemeli bir şekilde yapacağız.
kod aşağıdaki gibi gösterilir:
Özyineleme sürecinde, ızgaranın uzunluğunu soldan sağa, yukarıdan aşağıya, kademeli olarak azaltmalıyız. Örneğin, 8 * 8'lik bir ızgara ise, o zaman geçtiğimiz ızgara 8 * 8'den 4 * 4'e 2 * 2'ye, 1 * 1'e kadar olur. Dolayısıyla bu, özyineleme sırasında ızgaranın genişliğini ve konumunu ayarlamamızı gerektirir (nerede yukarı, aşağı, sol ve sağ olduğunu belirtir).
Orijinal fonksiyon gereksinimleri karşılamıyor, bu nedenle 5 parametreyi kabul eden bir yardımcı fonksiyon _doQuadTree () tanımlıyoruz, ilk parametre ızgaraya bir referanstır ve sonraki dört parametre başlangıç satırı alt simge ve sonraki bitiş satırıdır. Dizin (dahil değildir), başlangıç sütun dizini, bitiş sütun dizini (dahil değildir).
Çaprazlamadan önce analiz edelim, dörtlü ağaçta üç tür düğüm olacağını göreceğiz:
1. Izgarada tüm 0'lar varsa, bu, vali 0 olan bir yaprak düğümdür ve dört çocuğun tümü de boştur;
2. Izgarada tüm 1'ler varsa, bu, vali 1 olan bir yaprak düğümdür ve dört çocuğun tümü de boştur;
3. Izgara 1 ve 0'a sahipse, o zaman bir val, yaprak olmayan bir düğümdür ve dört çocuk boş değildir;
Bir ağaç için yaprak düğümlerinin sayısı genellikle çok fazladır ve yaprak düğümleri olarak ortak bir durum vardır, yani tüm 0 veya tüm 1 yaprak düğümleri yeniden kullanılabilir, bu da tasarruf sağlayabilir Çok fazla ek yük, sadece yerden tasarruf sağlamakla kalmaz.
Bu yüzden _falseLeafNode ve _trueLeafNode olmak üzere iki düğüm nesnesi tanımladık.
_DoQuadTree () çağrıldığında geçiş başlar. Kodun 32 ila 35. satırları tüm geçiş sürecidir. Büyük ızgaradan hücreye adım adım geçecektir.
Kod 29 ~ 30 satır. Bu koşul karşılanırsa, artık bir hücreye geçildiği anlamına gelir, o zaman belli ki hücredeki değere göre belirlenebilen bir yaprak düğümdür.
Kod 37 ~ 42 satır. Çapraz geçiş bittiyse, 37. satıra gider. Bu sırada, tüm kardeş ızgaraların val değerini ve isLeaf değerini alın. C ++ için, Tüm isLeaf toplamları 4 ise, bu, tüm ızgaraların yaprak düğümler olduğu anlamına gelir.Tüm değer değerlerinin toplamı 0'a eşitse, tüm ızgaranın 0 olduğu anlamına gelir. Benzer şekilde, val değerlerinin toplamı 4 ise Eğer, o zaman ızgaranın tamamı 1'dir, ki bu açıkça bir yaprak düğümdür. Aksine, ızgaranın tamamı yaprak olmayan bir düğümdür, bu nedenle yeni bir Node nesnesi oluşturulmalıdır. .
Python dilinin uygulanması:
Python dili ile C dilinin gerçekleşme prensibi temelde aynıdır. Fark, val ve isLeaf'i karşılaştırırken, python, == 'u birleştirerek val'yi doğrudan kolayca karşılaştırabilir.
kod aşağıdaki gibi gösterilir:
Java dilinin uygulanması:
Java uygulaması, C dili uygulamasıyla aynıdır. Fark hala val ve isLeaf arasındaki karşılaştırmadır. Java'nın Boolean türü, dört aritmetik işlemine bir integral türü olarak doğrudan katılamaz, ancak yalnızca karşılaştırma işlemlerini kullanabilir. Tüm değer değerlerinin eşit olup olmadığına karar verilirse, buradaki 35. satıra dikkat edin.
kod aşağıdaki gibi gösterilir:
