lombak şehidi

 Problem surada . Cozum Cok enteresan bir problem ile karsi karsiyayiz. Elimizde 2 inversion tipi var: global ve local.  Local inversion: yan yana olup da, kendisinden sonra gelenden buyuk olan bir eleman var ise bu local inversion oluyor.  Global inversion: yanyana olmasina gerek olmadan, kendisinden sonra gelen elemanlar icinde, kendisinden buyuk bir eleman var ise, bu global inversion oluyor.  Ben cok dusunmeden direk hesaplamaya giristim. Siz yapmayin diye burada tekrar yapalim ama sonra dusunme asamasina geri donecegiz.  O zaman oncelikle local inversionlari hesaplayalim: def isIdealPermutation(self, nums: List[int]) -> bool:      # local inversion sayisi kolay,     # her bir pair'i kontrol ediyoruz     loc = 0      for i in range(len(nums)-1):          if nums[i+1] < nums[i]:               loc += 1     glob = 0     # global icin ise 2 loop gerekli cunku her bir eleman icin     # kendisinden sonra gelen ve kendisinden kucuk kac eleman     # oldugunu bulmamiz gerek     fo

 Problem surada . Cozum Bu problemi O(n) space ile cozmek trivial o yuzden direk olarak follow-up ile baslayalim ve O(1) space ve O(n) time ile nasil cozeriz bunu dusunelim. Eger ileri ve geri olarak lined list uzerinde gezinebilse idik, ortasindan baslyarak yanlara dogru gider ve esitlik bozuluyorsa palindrome olmadigina karar verebilirdik. Peki geriye dogru gidemiyor ise, linkedlistin ilk yarisini ters cervirsek ve karsilastirmayi birincisi sifirdan ikincisi de linkedlistin tam ortasindan baslayacak sekilde iki pointer ile yapsak? Su sekilde: 1, 2, 2, 1 seklinde giden linked listi inceleyeim. Ilk yarisini ters cevirir isek, sonuca 2,1,2,1 seklinde bir hale gelir. Bu sekilde iken, i ve j olmak uzere iki pointer ile karsilastirma yapmak mumkun. Birincisi sifirdan ikincisi de ll'nin ortasindan baslayacak ve her adimda ikisini de 1 artiracagiz. Esitlik bozulursa False dondurecegiz.  O zaman ilk etapta linkedlistin uzunlugunu bulmamiz gerekiyor ki, ortsina kadar olan node'lari ter

 Problem surada . Cozum Naive implementasyon ile baslar isek, verilen arrayi sol taraf 1 elemanli olacak sekilde ayirmaya baslayabiliriz. Her adimda, sol arrayi bir eleman daha fazla genisletmeye calisiriz. Buradaki kriter su, sol arraydaki en buyuk eleman dahi, sag taraftaki elemanlarint tamamindan daha kucuk olacak. Bu kriteri sagladigimiz anda sol taraf eleman sayisini dondurecegiz.  def partitionDisjoint(self, A: List[int]) -> int:     # verilen left ve right arraylari icin bunun valid bir partition olup olmadigini      # kontrol eden fonksiyonumuz      # max hesaplayip, sagdaki tum elemanlarla karsilastirdigimizdan     # toplamda O(n) bir maliyete sahip     def is_valid_partition(left, right):          max_left = max(left)  # O(n)          for n in right:               if n > max_left:                    return False          return True     # sol taraf tek elemanli olacak sekilde baslayabiliriz     for i in range(1, len(A)):          left = A[:i]     # array kopyalama yapti