Leetcode: İki Toplamlı Sezgisel Bir Yaklaşım

Kendinizi Spot-On Change Hotel'in içindeki bir hediyelik eşya dükkanının gururlu sahibi olarak hayal edin. Kasayı kapatırken 8 Euro'luk fazlalık fark ediyorsunuz. Bir misafirin para üstünü tam olarak almadığı anlaşılıyor. Bu, otelin itibarını zedeleyebilir. Bunu önlemek için yanlış değişikliğin gizemini çözmeye karar veriyorsunuz. Mağazanın kasa sistemini açtığınızda hatanın iki farklı hesapta meydana geldiğini keşfedersiniz!

Bir plan yaparsınız: Her odayı ziyaret edin ve konuklara mağazada hangi para üstünü aldıklarını sorun, ta ki ikisinin yanlış faturalı olduğunu bulana kadar. Birinci kata gelen bir konuk, bozuk para olarak 4 avro aldığını bildirdi. 4 Euro'ya eklendiğinde 8 sonucunu veren bir sayı bulmanız gerektiğini hesaplıyorsunuz. İkinci kata çıktığınızda misafirin üstü 5 Euro oluyor. 4 + 5'in sonucu 9 olur, yani bu olamaz... Beşinci kat, altıncı... Onuncu, HAYIR, HAYIR, HAYIR!

İlk denemede değeri bulamadığınız için ikinci kata iniyorsunuz ve tüm konuklara para üstlerini tekrar sormaya başlıyorsunuz, böylece bir sonraki başlangıç katındaki değerle karşılaştırabilirsiniz, yorucu değil mi? BT? Bilgisayar bilimlerinde bu arama yöntemine kaba kuvvet denir; bu, bir öğeyi dizideki aşağıdakilerle karşılaştırarak çalışan son derece yavaş bir arama yöntemidir.

Bu çok zaman tüketir ve verimli değildir; Spot-On Change Hotel'in tüm katlarında birkaç kez yukarı aşağı gittiğinizi hayal edin! Bu sizin için pratik olmadığı gibi bilgisayar için de pratik değildir.

Bir yazılım programında bu katlarda yukarı ve aşağı gitmenin nasıl olacağını merak ediyorsanız, JavaScript'te şöyle görünür:

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

Durumu sakin bir şekilde değerlendirdikten sonra, para üstü yanlış olan iki misafiri bulmanın daha etkili bir yolu olduğunu fark edersiniz.

Başlangıçtaki matematiksel sezginizi 9 avronun x + y'ye eşit olduğu yönünde geliştirirsiniz. Biraz aritmetik uyguladığınızda şunu fark edersiniz: x + y = 9, y = 9 — x demekle aynı şeydir ve bu, aramanızın verimliliğini arttırırken büyük fark yaratır.

Stratejinizde değişen bir diğer şey ise artık misafirlerin size söylediği değerleri bir not defterine yazacaksınız, böylece misafirler için aynı değeri iki kez sormanıza gerek kalmayacak ve harcama yapmanıza gerek kalmayacak. gün merdivenlerden inip çıkıyor. (Asansörün bozulması için ne kadar kötü bir zaman!).

Elinizdeki yeni aletlerle birinci kata çıkıyorsunuz ve burada bir misafir size 5 avroluk bozuk paraları olduğunu söylüyor. Bunu, 0 konumunda 5 değerini belirten {5: 0} olarak kaydedersiniz. Denklemde x'i 5 ile değiştirerek, y = 8–5 hesaplarsınız ve sonuçta y = 3 elde edersiniz. Not defteriniz hala boş olduğundan, 8 sonucunu elde etmek için 5'in tamamlayıcısı olan 3 sayısını kaydetmediniz. Daha sonra 5 sayısını not defterinize yazın (her zaman o anda doğrulanan sayıyı yazmayı unutmayın, tamamlayıcısını değil; tümleyeni yalnızca yazdığınız hedef sayıyla karşılaştırmak için kullanacaktır). Para üstü olarak 2 avro alacağınızı söyleyen ikinci konuğa geçersiniz. Formülü tekrar uygularsak: y = 8–2 => y = 6, kaydınızı kontrol edersiniz, burada herhangi bir 6 rakamı bulamazsınız. Böylece kaydınıza 2'yi eklersiniz, bu da artık {5:0 olur, 2:1}. Aramaya devam eden bir sonraki konuk, 3 avro para üstü aldığını bildirdi. Tekrar hesaplarsınız: y = 8–3 => y = 5. Bingo! Not defterinizde kayıtlı bir 5 var! 0. kattaki misafir, 2. kattaki misafirin tamamlayıcısıdır! Bu yaklaşım karma tablosu olarak bilinir ve hem sizin hem de bilgisayar için çok daha hızlı ve verimlidir. JavaScript'te bu şu şekilde uygulanacaktır:

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Bu, Leetcode'un basit bir problemidir ve ancak arkasındaki kavramları anladıktan sonra kolaylaşır. Sorunu kendi başınıza çözmeye çalışmanızı ve çözüme geçmeden önce arkasında sezgi oluşturmaya, kendi analojinizi oluşturmaya, incelemeye ve sözde kod yazmaya biraz zaman ayırmanızı öneririm.

Umarım benzetmem iki toplam mücadelesinin ardındaki kavramları daha iyi anlamanıza yardımcı olmuştur.

Bir dahaki sefere görüşürüz!