Biraz Kadim Algoritmik Sihir veya LeetCode'dan İlgi Çekici Bir Görev Dizisini Çözmek

Bir süre önce leetcode.com web sitesinde bir dizi eğlenceli göreve rastladım. Görevlerin kendisi çok zor değil ama çözümleri oldukça ilgi çekici. Üstelik bu tür sorunlar büyük şirketlerle yapılan görüşmelerde sıklıkla karşımıza çıkıyor ve bunların çözüm yöntemlerini anlamak oldukça faydalı olabiliyor.

İlk Görev 136. Tek Sayı (Kolay)

Biri hariç her öğenin iki kez göründüğü, boş olmayan bir tamsayı dizisi verildiğinde, öğeyi çifti olmadan bulmanız gerekir. Sorunu O(n) zaman karmaşıklığında ve sürekli ekstra bellekle çözün.

Örnek 1:

Giriş: sayılar = [1, 3, 3, 2, 6, 2, 1]

Çıkış: 6

Örnek 2:

Giriş: sayılar = [12, 1, 1, 7, 1, 12, 1]

Çıkış: 7

Örnek 3:

Giriş: sayılar = [6]

Çıkış: 6

Yalnızca işlenenleri farklı olduğunda 1 sonucunu veren XOR işlevi özelliğinden yararlanacağız. Dizinin tüm öğeleri arasında dolaşarak ve bunlar üzerinde bit düzeyinde XOR uygulayarak, tüm özdeş bit değerlerini sıfırlayacağız. Sonuç olarak geriye istenilen sonuç kalacaktır.

İşte kısa bir Python3 çözüm kodu:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Yalnızca bir tam sayının kapladığı kadar ek bellek kullanırız ve çözümü verilen diziden tek geçişte buluruz, bu da bize O(n) karmaşıklığını verir. Bu kısa ve zarif bir çözümdür.

İkinci Sorun 137. Tek Sayı II (Orta Zorluk)

Biri hariç her öğenin üç kez göründüğü ve yalnızca bir öğenin bir kez göründüğü boş olmayan bir tamsayı dizisi verildiğinde, bu benzersiz öğeyi bulmamız gerekir. Sorunu O(n) zaman karmaşıklığında ve sürekli ekstra bellekle çözün.

Örnek 1:

Giriş: sayılar = [3, 1, 3, 3]

Çıkış: 1

Örnek 2:

Giriş: sayılar = [12, 1, 1, 5, 1, 12, 12]

Çıkış: 5

Örnek 3:

Giriş: sayılar = [6]

Çıkış: 6

Ne yazık ki bu durumda önceki numarayı kullanamıyoruz çünkü gerekli konumdaki eşleştirilmiş bitleri sıfıra çeviremiyoruz. Verilen diziyi önceki görevdeki formata dönüştürmek ve daha sonra benzer şekilde çözmek cazip gelebilir.

Bu şekilde mantık yürüterek, diziyi geçerken N sayısıyla iki kez (veya üç kez) karşılaştığımızı bilseydik, elde ettiğimiz toplama N ile ek bir XOR ekleyebileceğimizi fark etmek kolaydır. Bu, bu sayıdaki son XOR'u çift yapar, böylece onu nihai toplamdan çıkarırız ve geriye kalan bizim cevabımız olur.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

Ne yazık ki, bu çözüm bellek açısından maksimum (len(nums)-1)/3 gerektirecektir ve bu da sürekli tüketim olarak kabul edilemez, bu nedenle başka bir çözüm aramamız gerekecek.

Yaklaşımımızı değiştirmeyi deneyelim.

Daha önce XOR'u (ekleme modulo 2'yi temsil eden) kullandık. Eğer toplama modulo 3'ü uygulamış olsaydık önceki örnekteki hileyi kolaylıkla uygulayabilirdik.

İlk karşılaştığımızda cevaba bir sayı koyabilirsek, ikinci seferde onu akümülatöre koyabilir ve üçüncü seferde hem cevabı hem de akümülatörü sıfırlayabilirsek, bu, sorunu tek geçişte çözmemize yardımcı olacaktır. görev gereksinimlerini karşılayan, tam olarak iki tam sayıya eşit ek bellek tüketimine sahip liste.

O halde biraz daha bitsel sihir uygulayalım:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

Bu şekilde tüm üçlü sayılar sıfırlanır ve elimizde yalnızca bir kez gerçekleşen sayı kalır.

Üçüncü Görev 260. Tek Numara III (Orta Zorluk)

Yalnızca bir kez görünen iki öğe dışında her öğenin iki kez göründüğü, boş olmayan bir tamsayı dizisi verildiğinde, bu benzersiz öğeleri bulmamız gerekir. Amaç, sorunu O(n) zaman karmaşıklığında ve sürekli ekstra bellekle çözmektir ve benzersiz öğelerin sırası önemli değildir.

Örnek 1:

Giriş: sayılar = [1, 2, 1, 3, 2, 5]

Çıkış: [3, 5]

Örnek 2:

Giriş: sayılar = [1, -2]

Çıkış: [-2, 1]

Açıkçası, ilk görevi çözerken yaptığımız gibi, XOR işlemini kullanarak tüm eşleştirilmiş sayıları kolayca ortadan kaldırabiliriz. O zaman görevin karmaşıklığı, benzersiz sayılardan herhangi birinin tanımlanmasında yatmaktadır; bundan sonra ikincisi, XOR toplamımızla XOR'lanarak kolayca hesaplanabilir.

Bunu başarmak için bu benzersiz sayılar arasında herhangi bir farklı bit bulmamız yeterli. Daha sonra diziyi tekrar yineleyerek XOR toplamı gerçekleştiriyoruz ve sonuçları bu bitin ayarlandığı sayılar ve 0 olduğu sayılar için iki gruba bölüyoruz. Sonuç olarak istenen benzersiz öğeleri elde ediyoruz.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

Dizide iki kez yineleme yapılması gerekmesine rağmen karmaşıklık O(n) olarak kalır ve bellek tüketimi yalnızca 2 tam sayıdır.

Not: Python'daki int'nin diğer dillerdeki int ile tam olarak aynı olmamasına rağmen, boyutunu sabit olarak kabul edeceğiz.