lombak şehidi

 Problem surada . Cozum Ilk akla gelen naive cozumle baslayalim.  Verilen stringi itere ederiz.  Simdiye kadar gorulen karakterleri tutmak icin bir cache olustururuz.  cur_maks ve maks adinda iki degiskende mevcut tekrar etmeyen substring uzunlugunu ve global maks degerini tutariz. Eger eldeki karakter cache'te var ise cur_maks ve cache'i resetleriz. Yok ise, cur_maks degerini artirir ve de global maks ile kiyaslayip guncelleriz.  Mesela bu yontem "abcabcbb" icin calisir. Yani leetcode'da Run Code yaptigimda pass etmisti. Ama submit ettigimizde gorecegiz ki bazi case'ler icin calismiyor.  Ornek olarak, "dvdf" icin 2 degerini elde ederiz. Cunku dv ile basladik guzel sonra tekrar d gelince reset attik. Ve d geldigi noktadan ilerlemeye devam ettik. Ama aslinda d'yi ilk gordugumuz yere geri donmemiz gerekiyordu. Cunku 0 noktasindan degil de 1 noktasindan baslarsak en uzun tekrarsiz sunstringi elde ederiz.  Revizyon Yukarida bahsettigimiz metodu biraz

Problem surada . Cozum Planimiz soyle: verilen linked list'leri sayiya cevirip, sayilari toplayip, tekrar linked liste'e cevirip geri dondurecegiz.  Oncelikle sayiya cevirelim: 2 --> 4 --> 3 2'den baslayarak, elde edecegimiz deger 342 olmali. Yani 2 + 40 + 300. Yani her adimda mevcut node degerini basamak carpani ile carpip toplayacagiz. Ve de basamak carpanini de 10 ile carparak guncelleyecegiz. def toDecimal(node):     ret = 0     multiplier = 1     cur = node     # listenin sonuna kadar gidelim     while cur:          # her adimda basamak degerini hesapla ve toplama ekle          ret += multiplier * cur.val          # basamak degeri her adimda 10 kat artiyor          multiplier *= 10           # listeyi ilerletmeyi unutursak bu donguden cikamayiz          cur = cur.next     # sonucu dondur     return ret Daha sonra verilen bir sayisi tekrar linked liste'e donusturelim: 708 icin 8 --> 0 --> 7 seklinde bir linked list elde etmemiz gerekli. Sayiya sondan bas

 Problem surada . Cozum Ilk etapta yine naive implementasyon ile basyalabiliriz. Brute force ile dizedeki her bir noktada alinip, ondan sonra gelen bir noktada satldiginda elde edilecek kari hesaplayip, max olani dondurebiliriz. Ama bu bizi bir yere goturmez.  Yapmamiz gereken sey, maksimum farki bulmak. Ama bunu yaparken de kucuk olan sayinin buyuk olan sayidan sonra gelmesini saglamak.  Diyelim ki dizeyi bastan sona dogru traverse ediyoruz.  Her adimda, gecmisteki en kucuk rakami tutabiliriz. Burasi alis noktasi olacak.  Yine ayni adimda, eger bu noktada satmis olsaydik, (ve tabi daha onceki adimlardan bu adima kadar olan dize elemanlari icerisinde en dusuk olani bulmusuzdur) ne kadar kar edecektik bunu hesapliyoruz.  Eger simdiye kadar buldugumuz profitlerden yuksek ise, bunu global maks olarak atiyoruz.  def maxProfit(self, prices):     maks = float("-Infinity")     past_min = float("Infinity")     for p in prices:          # simdiye kadar gorulen en dusuk deger

Daha once O(n) ile cozdugumuz max subarray probleminin, leetcode'da bir de follow up'i var. Problemi divide and conquer ile cozebilir miyiz? Ilk bakista, verilen dizeyi sol ve sag olarak ikiye ayirip, ayri ayri max sub-array'larini bulmak kolay gozukuyor. Recursive bir fonksiyona bakiyor: class Solution:     def maxSubarraySum(self, nums, start, end):         # base case: sadece tek eleman varsa, max olarak onu dondur           if start == end:             return nums[start]         else:                # orta noktayi bularak dizeyi ikiye ayirip                # hangisinin max sub array'i buyukse onu donduruyoruz             mid = start + (end-start)//2             return max(self.maxSubarraySum(nums, start, mid),                                 self.maxSubarraySum(nums, mid+1, end))          def maxSubArray(self, nums):         return self.maxSubarraySum(nums, 0, len(nums)-1) Bu cozumde tabi ki bir eksik var. Ya max sub array, bizim boldugumuz yerden geciyorsa? Zaten 

 Problem surada . Cozum Yine naive implementasyon ile baslayabiliriz. Benim ilk aklima gelen bir tabulasyon olusturmak ve tum start-end komninasyonlarini burada tutmakti.  maks = float("-Infinity") cache = [[0]*len(nums) for t in range(len(nums))] # 1 uzunluktaki sub-arraylar for i in range(len(nums)):     cache[i][i] = nums[i] # 2 uzunluktasi sub-arrayler for i in range(1, len(nums)-1):     cache[i][i+1] = cache[i][i] + nums[i+1] # 3 uzunluktaki sub-arrayler for i in range(2, len(nums)-2):     cache[i][i+2] = cache[i][i+1] + nums[i+2] Kodu yazarken bile brute-force kullandik :D Burada olusan pattern'i gormus olduk. Simdi bunu daha dinamik sekilde yazarsak: class Solution:     def maxSubArray(self, nums):         maks = float("-Infinity")         cache = [[0]*len(nums) for t in range(len(nums))]                  for k in range(len(nums)):             for i in range(len(nums)-k):                 cache[i][i+k] = cache[i][i+k-1] + nums[i+k]                 maks = m

Problem surada . Cozum Soruda verilen 2 linked list'i merge etmemiz isteniyor. Su sekilde ilerleyebiliriz: 1. Geri dondurecegimiz deger, olusturulan merge edilmis linked list'in head (yani baslangic) node'u olacak. Ancak biz merge islemi yaparken hep listenin sonuna ekleme yapacagiz. Bu durumda, sonuc listesine head ve tail olmak uzere 2 referans tutmak ismizi kolaylastiracaktir.  1. Iki liste uzerinde iterasyon yapacagimiz icin, halihazirda okunan liste node'u tutacak 2 head referansi kullanacagiz. Bunlari iki tane serit okuyor gibi dusunebiliriz. Ya da kaset okuyucusu gibi. Her bir okuma yaptigimizda head'in degerini guncelleyecegiz. Ve liste bittigi zaman bu head degeri None olmus olacak. 2. Hangi liste uzerinde iterasyon yaparken, ikisinden birisi bittigi zaman donguye son verecegiz. Ve eger hala elemani bulunan bir liste var ise, onun tum elemanlarini sonuca ekleyebiliriz.  3. Son olarak da en basta tuttugumuz sonuc head node'unu donduruyoruz.  ret = None t

 Problem surada . Cozum Verilen grid'i bir graph olarak dusunebiliriz. Bir adayi tespit etmek icin, bir degeri 1 olan hucreden yola cikarak yavas yavas komsularini kontrol ederek disari dogru genisletebiliriz. Bu da aslinda breadth first search anlamina geliyor.  Cozum adimlari soyle olacak: 1. Gridinin 0,0 noktasindan baslayarak 2 for loop icerisinde tum node'larini itere edecegiz. 2. Ayni node'u 2 veya daha fazla kere ziyaret etmememiz gerekiyor, bunun icin ziyaret edilen node'lari tutacagimiz bir set olusturacagiz 3. Eger hucre degeri 1 ise, ada sayisini 1 artirip, buradan disari dogru genisletme islemi baslayacak (tabi ziyaret edilmemis node'lar uzerinden) 4. bir arama basladiktan sonra, bir noktada eklnen tum komsular 0 olunca (ada bitti), arama sonlanacak Implementasyon   Bir node'u ziyaret ederken komsularini bulmamiz gerekiyor. Bu noktada bazi edge case'ler var. Iste node en solda ise, onun solunda bir hucre yoktur meselea. Ya da node en sagda ise o