lombak şehidi

11. Majority Element Problem surada . Cozum Ilk aklima gelen naive yontem, her bir elemanin arrayda kac kere gectigini tutan bir dictionary kullanmak. Daha sonra da, n/2'den fazla degeri olan key'i geri dondurmek. Ise yariyor ama iyilestirilebilir.  def majorityElement(self, nums: List[int]) -> int:     # biraz daha sekil olsun diye defaultdict yerine direk Counter kullanilabilir.     counts = collections.Counter(nums)     # ve de en fazla count degerine sahip elemani dondurebilirz.     # cunku problemde majority degerinin var olacagi garanti ediliyor     return max(counts.keys(), key=counts.get) Baktigimizda, O(n) ile her bir elemani sayiyoruz. Toplamda O(n) time compl. ve de O(n) space compl. sahip bir cozum.  Olaya baska bir acidan bakar isek, madem majority element, arraydaki toplam eleman sayisinin yarisindan fazla, bu array sort edilmis olsa idi kesinlikle en ortadaki eleman majority elemandan olurdu. Oyle ya, yarsindan fazlasini kapliyor arrayin.  def majorityElement(

1. Decode XORed Array Problem surada . Cozum XOR operatoru, iki binary sayi arasindaki bit farklarini ortaya cikartiyor. Yani XOR sonucu 1 gelmisse, iki taraftaki bit farkli, 0 gelmisse ayni demektir. Bu durumda XOR sonucuna bakarak, ve de encode edilmemis arrayin ilk elemani elimizde olduguna gore, ikinci elemanini reverse XOR ile bulabiliriz.  Soyle: encoded[i] = arr[i] ^ arr[i+1]  olduguna gore, encode edilmemis arrayin ilk elemanina first dersek, encoded[1] = first ^ arr[i+1] Bu denklemde sol tarafi biliyoruz, ve de first degerini biliyoruz. O zaman geriye kalan basit bir cebir islemine benzer sekilde arr[i+1] bilinmeyenini esitligin bir tarafinda birakmak. arr[i+1] = ??? HINT 1: XOR islemi siralamadan bagimsizdir. Toplama islemi gibi. Ne de olsa iki sayi arasindaki bit farklarina bakiyoruz, ilk once hangisinin geldiginin bir onemi yok.  HINT 2:      a = b ^ c ise;      b = a ^ c ve de c = b ^ a  seklinde degiskenler yer degistirilebilir. Bu su demek, XOR operatorunun tersi yine XO

Bitwise islemlere gecmeden once, int tipi ile alakli bir hatirlatma yapalim. Python3'ten itibaren, int tipinin tutabilecegi max deger, bilgisayar hafizasi kadardir. Yani tipin kendisinde bir kisitlama yok. Bu da demek oluyor ki, yeterince hafiza varsa sistemde, int tipini overflow etmek imkansizdir. Bunu nasil basariyor peki?  Arbitrary Precision Python 2.0'da tam sayilar icin iki farkli tip vardi: int ve long. Buradaki int, C data typi olup, sabit "precision"a sahiptir. Yani kodun calistigi platforma gore 2 veya 4 byte ile temsil edilir ve buna bagli olarak tutabilecegi maksimum deger bellidir ( detaylara suradan bakabilirsiniz ). Dogal olarak bu tip overflow edilebilir. Hatta sys.maxint ile kodun calistigi platformda, int tipinin alabilecegi max degere ulasabilirz. Ama Python2 bile, bunu guzel bir sekilde handle etmektedir. Eget int tipi overflow oluyor ise, otomatik olarak long'a "promote" edilir.  Python3'te int tipi ve long tipi birlestirilerek