lombak şehidi

 Problem surada . Cozum Bir onceki sorunun devami niteliginde ve bu sefer olusturulabilecek tum cumleleri geri dondurmemiz isteniyor. Yine ben aklima ilk gelen yontemle ise baslayacagim. Ne de olsa arkamizdan atli kosturmuyor, maksat cimnastik.  Ben yine backtracking ile baslamak istiyorum. Cunku bu soru icin uygun oldugunu dusunuyorum. String uzerinde kayan bir pencere ile dictionary kontrolu yaparak, bir cozum uretecegiz. Daha sonra bu cozumu baska bir yere kopyaladikta sonra, cozumdeki (veya cozume ulasamamis bir program dalindaki) son kelimeyi cikartacagiz. Ve o kelimeyi almak yerine, onceki kelimeyi bir karakter daha artiracagiz. Bu sayede tum kombinasyonlari denemis olacagiz.  class Solution:     def __init__(self):          # uzerinde calismakta oldugumuz cozumu temsil eden kelimeler          self.cur_solution = []          # bu da bulabildigimiz tum cozumler          self.solutions = []     def solve(self, string, start, dic):          # eger start, sona gelebilmis ise       

 Problem surada . Cozum Naive implementasyon ile baslayalim.  Two pointer approach kullanacagiz. Start ve end degiskenleri mevcut pencereyi temsil edecek. Eger mevcut pencere, dict icerisinde var ise, start'i end'e getirip, end'i bir artiracagiz ve devam edecegiz. Buraya kadar greedy bir algoritma cunku egere sozlukte varsa direk onu aliyor. Ama belki de onu direk almamasi gerekir. Ornek: verilen input: aaaaa, sozluk: aa, aaa  simdi bunun True dondurmesi gerekiyor cunku "aaa" + "aa" seklinde ayirabiliriz. Ama suana kadarki olusturdugumuz yontemle gidersek, surekli "aa" da devam edecegiz ve sonra tek bir "a" kalacak. Bu durumda string parse edilemez karari verecegiz.  Bu da aslinda backtracking anlamina geliyor. Yani son olarak sozlukten aldigimiz "aa" degeri ile cozume ulasamadi isek, bunu birakip kaldigimiz yerden yolumuza devam etmemiz gerekir. Bu durumda "aaa" cozumune de erisebilir ve dogru sonucu hesaplayabili

 Problem surada . Cozum Naive implementasyonla basliyoruz. Verilen stringleri bir sekilde anagram olup olmadiklarini anlamamiz gerekiyor. Anagram ne demek? Ayni sayida karakter olacak, karakterler de ayni olacak (bu arada soruda karakterler unique olacak diye bir ibare yok) sadece yerleri degisik olacak. Bu bize bir fikir veriyor aslinda. Yani biz verilen stringi, bir array gibi dusunup, alfabetik olarak karakterleri sort edersek, anagramlar ayni sonucu uretecektir. Ornek: def groupAnagrams(self, strs):     # her bir stringi karakter bazinda sort ettikten sonra     # olusan sonucu bu dictionary'de tutacagiz ki     # ayni ciktiyi veren anagramlari gruplayabilelim      cache = {}     for s in strs:          # stringin karakterlerini sort edip            # tekrar bir string olusturuyoruz          # sort -> O(n logn)          # string concat -> O(n)          processed = "".join(sorted(s))                    # bu cikti daha once elde edilmis ise          # bir anagram va

 Problem surada . Cozum Normalde naive implementasyon ile basliyoruz ancak burada cozum zaten direk O(n). Yani biz verilen arrayin sorted ve rotated oldugunu gozardi edip direk itere etsek zaten istenen indexi O(n) ile buluruz. O zaman naive implementasyona gerek yok.  Follow-up'ta sorulan noktaya geleleim ve istenen indexi O(log n) ile bulmaya calisalim. O(log n)'den de anlasilacagi gibi cozum binary search'te yatiyor. Ama bir farkla, arrayin rotated olmasini nasil handle edecegiz?  Once rotation noktasini bulup sonra binary search yapsak, islem tekrar O(n)'e gidebilir. O zaman binary search icerisinde bunu handle etmemiz gerekiyor. Her bir adimda arrayin bir notkasindan ikiye bolecegiz. Tam bu noktada rotation olup olmadigina bakabiliriz.  1. Binary search icerisinde rotation point olmadigina bakma fikri ise yaramadi. Cunku binary search'te mid pointi aldiktan sonra sol parcayi ya da sag parcayi alip devam etmemiz gerekiyor. Bu noktada rotation yok ise, rotation&#

 Problem surada . Cozum Surasi belli ki, verilen liste icerisinde cukurlari tespit etmemiz gerekiyor. Ve bu cukurda biriken su miktarini hesaplayip toplayacagiz.  Ilk etapta benim aklima listedeki sayilarin artip azalmasina bakarak cukurlari tespit etmek vardi ancak pek basarili olmadi. Naive bir implementasyon olarak, her bir stunda, kendisinden once ve sonra gelen, ve bu stundan daha yuksek olan duvarlari bulsak, ve bu cukurdaku su miktarini hesaplamak yerine sadece bu stunda birikebilecek su miktarini hesaplasak, ve bu sekilde tum stunlari toplayarak gitsek, sonuca ulasiriz.  O zaman soyle yapiyoruz: 1. Her stunu itere et  2. Her bir stun degerinden once gelen stunlardaki, bu stundan yuksek olan en yukske stunu bul 3. Stun degerinden sonra gelen ve bu stundan yuksek olan en yuksek stunu bul 4. ikinci ve ucuncu adimlarda cukurun iki tarafini bulmus olduk. Ancak su, bunlardan kisasi kadar birikebilecegi icin min islemi yap 5. Minimum duvari bulduktan sonra mevcut stun degerini bundan

 Problem surada . Cozum Problemde bizden bir sekilde verilen bir binary tree''yi string seklinde serialize etmemiz isteniyor. Ayni sekilde bu stringi daha sonra deserialize edip binary tree'yi tekrar olusturmamiz gerek. Naive bir baslangic olarak, pre-order traversal ile serialize edelim. Null tipleri icin de ozle bir karakter olarak "^" kullanacagim.  def serialize(self, root):     # eger TreeNode, None ise, bunu ozel bir karakterle temsil edebiliriz      if not root:           return "^"     arr = [str(root.val), self.serialize(root.left), self.serialize(root.right)]     return ",".join(arr) seklinde recursive sekilde verilen binary tree'yi serialize edebiliriz. Bir ornek: Zaten pre-order traversal yaptigimiz icin once root.val sonra left, sonra da  right branchlari alip stringe ceviriyoruz. Bunun sonucunda 1,2,^,^,3,4,^,^,5,^,^ seklinde bir string elde ediyoruz. Simdiki gorevimiz de bunu parse etmek.  Diyelim ki parse etmeye 1'den ba

 Problem surada . Cozum Ilk akla gelen yine tum tripletleri uretmek ve duplikasyonlari da bir sekilde elimine ederek, toplamlari sifir olan tripletleri dondurmek. Bu da eger duplikasyon olayini O(1) ile cozebilirsek toplamda O(n3) gibi bir maliyet getirir ki, cok ciddi bir maliyet.  Brute force olarak triplet uretmek, icsel olarak (implicit? :D) verilen array'in hicbir duzeni olmadigi bilgisini barindiriyor. Yani array elemanlari rastgele dizilmis ve biz de direk 3 dondu icerisinde hepsini donuyoruz. Ama requiremet'e bakarsak bize toplami sifir olan tripletler lazim.  Bu ipuclari bize gosteriyor ki, verilen arrayi sort edersek, bir optimizasyon cikartabiliriz. Ne de olsa sort ettikten sonra arrayin traverse yonune gore toplami gerektigi gibi artirabilir ya da azaltabiliriz.  Ornek olarak [-1,0,1,2,-1,-4,-2,-3,3,0,4] inputunu inceleyelim. Bunu sort ettigimiz zaman yukaridaki gibi bir sonuc elde ediyoruz. Tum array'i traverse edecek bir i index'ine yanci olarak bir soldan

 Problem surada . Cozum Verilen bir linked list'i kopyalamak trivial sayilabilir. Burada tek fark, her node, bir random alanina sahip ve hehangibir node'u isaret ediyor. Yani one-pass ile biz linked listi kopyalarken henuz bu node'u kopyalamamis olabiliriz. Bu gibi bir durumda bu nodu olsuturmaya calismak daha fazla karmasaya sebep olacaktir.  Bunun yerine oncelikle tum linked listi kopyalayalim. Ve de her orjinal node'a karsilik, klon node'u tutan bir mapping yapisi olusturalim. (Bir python dictionary). Kopyalama islemi bittikten sonra, linked listi tekrar one pass ile traverse edip, random alanini guncelleyelim. Bu kadar basit ama implementasyonda can sikici corner case'ler olabilir.  Implementasyon def copyRandomList(self, head):      # bos liste icin edge case kontrolu     if not head:          return None     # orjinal_node -> klone node      mapping = {}     # ilk once listeyi kopyalayalim      # ve mappingi olusturalim          # burada heading degeri