Bit maskesiyle her alt küme
Görev tanımı
Problem
Birbirinden farklı öğelerden oluşan bir liste verildiğinde, onun her alt kümesini döndür. Alt kümeleri sayarak sırala: bir alt kümeyi, items[i] dahilse i. biti 1 olan bir ikili sayı olarak oku ve alt kümeleri bu sayı 0'dan en büyüğe kadar listele. Her alt kümenin içinde öğeleri orijinal sıralarında tut. Listede en fazla 15 öğe var; boş listenin de bir alt kümesi var.
Örnekler
Input: items = ["a", "b"]
Output: [[], ['a'], ['b'], ['a', 'b']]
Neden: 0, 1, 2 ve 3 sayıları ikili olarak 00, 01, 10 ve 11
Input: items = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Neden: items[2], 2. bit yandığında 4 sayısından itibaren katılır
Input: items = []
Output: [[]]
Neden: edge case: boş küme tek alt kümedir
İpuçları
0 / 3
Her öğe bir alt kümenin ya içinde ya dışındadır, yani n öğe 2 üzeri n alt küme verir. Başka ne tam olarak bu kadar çeşit halinde gelir?
0'dan 2 üzeri n eksi 1'e kadarki tam sayılar, n bitin olası her desenidir ve her desen bir alt kümeyi tarif edebilir.
Bir mask sayısını 0'dan 2 üzeri n eksi 1'e kadar say. Her maske için biti 1 olan her i'nin items[i]'sini topla; bunu bir kaydırma ve bir AND ile test edebilirsin.
- Hedef zaman
- O(n · 2ⁿ)
- Hedef alan
- O(n · 2ⁿ)
Kısıtlar
- items are distinct
- 0 ≤ items.length ≤ 15
Çözüm
n öğenin bir alt kümesi öğe başına bir evet ya da hayır seçimidir; bu da tam olarak n bitlik bir sayı demektir, bu yüzden 0'dan 2 üzeri n eksi 1'e kadar saymak her alt kümeyi bir kez dolaşır. Her sayı için i. bit mask >> i & 1 ile test edilir, biti açık olan öğeler de alt kümeyi oluşturur. i. bit her zaman items[i] anlamına geldiği için üyeler orijinal sıralarında kalır. Zaman O(n · 2^n), çıktı için alan da aynı.
def all_subsets(items):
n, subsets = len(items), []
for mask in range(1 << n): # every n-bit pattern is one subset
subsets.append([items[i] for i in range(n) if mask >> i & 1])
return subsets
print(all_subsets(["a", "b"])) # -> [[], ['a'], ['b'], ['a', 'b']]
print(all_subsets([1, 2, 3])) # -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
print(all_subsets([])) # -> [[]]Kodda değil de fikirde mi takıldın? Küme olarak bit maskesi bunu anlatıyor.