Her sayının 1 olan bitleri
Görev tanımı
Problem
Negatif olmayan bir n tam sayısı verildiğinde, 0'dan n'ye kadar (n dahil) her i için i indeksindeki elemanı i'nin ikili biçimindeki 1'lerin sayısı olan bir liste döndür. Bütün listeyi her sayının basamakları üzerinde döngü kurmadan tek geçişte doldurmaya çalış.
Örnekler
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Neden: ikili olarak 0, 1, 10, 11, 100, 101
Input: n = 2
Output: [0, 1, 1]
Input: n = 0
Output: [0]
Neden: edge case: liste sıfırın kendi elemanını da tutar
İpuçları
0 / 3
Her sayının 1'lerini sıfırdan saymak işi tekrarlar. Zaten ele aldığın daha küçük bir sayı mevcut sayıya neredeyse tıpatıp benziyor.
Bir sayıyı bir basamak sağa kaydırmak en düşük basamağını atar, diğer bütün basamakları korur. O daha küçük sayı zaten listende.
Listeyi 1'den yukarı doğru doldur. i'nin sayısı, i'nin bir sağa kaydırılmışı için kayıtlı sayı artı i'nin en düşük basamağı 1 ise bir.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- n ≥ 0
Çözüm
i'nin en düşük ikili basamağını atmak i'yi bir sağa kaydırmak demektir; bu, sayısı zaten bilinen daha küçük bir sayıdır, yani i'nin sayısı bu kayıtlı sayı artı atılan basamaktır. Listeyi artan sırada doldurmak her aramanın geriye, tamamlanmış bir elemana bakmasını garanti eder. Her eleman bir kaydırma, bir AND ve bir toplamaya mal olur. Zaman O(n), çıktı listesi O(n) alan.
def set_bits_up_to(n):
counts = [0] * (n + 1)
for i in range(1, n + 1):
counts[i] = counts[i >> 1] + (i & 1) # reuse the answer without the low digit
return counts
print(set_bits_up_to(5)) # -> [0, 1, 1, 2, 1, 2]
print(set_bits_up_to(2)) # -> [0, 1, 1]
print(set_bits_up_to(0)) # -> [0]Kodda değil de fikirde mi takıldın? 1 olan bitleri saymak bunu anlatıyor.