Counting Bits

Q: Counting Bits'in zaman karmaşıklığı nedir?

En iyi çözüm O(n) zamanda çalışır: n+1 girdinin her biri, daha önceki bir girdiden tek bir toplama işlemiyle elde edilir. Her sayının bitlerini ayrı ayrı saymak O(n log n) zaman alır. Her iki çözüm de çıktı dizisinin dışında O(1) bellek kullanır.

Q: Counting Bits için başka bir O(n) bağıntı var mı?

Evet. i & (i-1) , i değerinin en düşük 1 bitini temizler; bu nedenle 1 veya daha büyük her i için bits[i] = bits[i & (i-1)] + 1 olur. 12 için ( 1100 ), 12 & 11 sonucu 8’dir ( 1000 ); bunun bir tane 1 biti vardır, dolayısıyla 12’nin iki tane 1 biti vardır.

Q: Dahili bir popcount işlevi kullanabilir miyim?

Java'daki Integer.bitCount veya C ve C++'taki __builtin_popcount gibi yöntemleri her sayı için çağırmak doğru bir yanıt verir. Görüşmeyi yapanlar genellikle bunu kullanmadan yapılan sürümü ister; çünkü problemin amacı, önceden hesapladığınız yanıtları yeniden kullanmaktır.

KolayBit işlemleri Dinamik programlama

+10

0 veya daha büyük bir tam sayı olan n verildiğinde, 0 ile n arasındaki her i için i'nin ikili gösterimindeki 1'lerin sayısının i. eleman olduğu, n+1 elemanlı bir dizi döndürün.

Fonksiyon

countBits(n: integer) → integer-array

ninteger: sayılacak son sayı, 0 veya daha fazla
Döndürürinteger-array: n+1 elemandan oluşan bir sayım dizisi; burada i. öğe, i sayısındaki 1 bitlerinin sayısıdır

Kısıtlar

0 ≤ n ≤ 2 × 10⁴

Örnekler

Girdi: n = 2
Çıktı: [0, 1, 1]
Açıklama: İkili sistemde 0, 0; 1, 1 ve 2, 10 şeklindedir: önce hiç 1 yok, sonra bir tane, sonra da bir tane.

Girdi: n = 5
Çıktı: [0, 1, 1, 2, 1, 2]
Açıklama: 3, 11 eder ve 5, 101 eder; her ikisinde de iki tane 1 vardır; 4 ise 100 eder ve bir tane 1 vardır. İlk örnekteki 0, 1 ve 2 ile birlikte sayılar 0, 1, 1, 2, 1, 2 olur.

Ek soru

Tüm diziyi, bitleri sayan yerleşik bir fonksiyon kullanmadan ve her sayıyı baştan saymadan O(n) zamanda doldurabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her sayıyı baştan saymak işi tekrarlar: 13, 1101 şeklindedir; 6'nın (110) bitlerinin sonuna bir basamak daha eklenmiş hâlidir. Yanıtları artan sırayla doldur ve her giriş, bir toplama işlemiyle daha küçük bir girişi yeniden kullanır.

Her sayının bitlerini say

Sezgi

Her sayının 1 bitlerini doğrudan sayın: x & 1 değerini bir sayaçta toplayın, x değerini bir bit sağa kaydırın ve 0'a ulaşınca durun. 13 için (1101) bitler 1, 0, 1, 1 olarak çıkar; dolayısıyla sayı 3'tür.

n'e kadar olan bir sayının yaklaşık log2 n ikili basamağı vardır, bu nedenle çalışma O(n log n) olur: n = 2 × 10^4 için yaklaşık 20.000 × 15 = 300.000 adım.

Algoritma

Boş bir sonuç listesi oluştur.
0'dan n'e kadar her i için count'u 0 ve x'i i olarak ayarla.
x 0'dan büyük olduğu sürece x & 1'i count'a ekle ve x'i bir bit sağa kaydır.
count'u sonuca ekle.
Sonucu döndür.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Sayının yarısı üzerine kurun

Sezgi

i değerini bir bit sağa kaydırmak son ikili basamağını siler ve i & 1 bu basamaktır. Dolayısıyla i, i >> 1 değerindeki 1'lere son basamağını ekler: bits[i] = bits[i >> 1] + (i & 1).

1 veya daha büyük her i için i >> 1, i değerinden küçüktür; bu nedenle diziyi soldan sağa, bits[0] = 0 ile başlayarak doldurmak, okuduğunuz girdinin her zaman hazır olduğu anlamına gelir. n = 5 için: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Her girdi bir kaydırma, bir AND ve bir toplama gerektirir: O(n) zaman ve çıktı dışında ek bellek gerekmez.

Algoritma

n+1 sıfırdan oluşan bir bits dizisi oluştur. bits[0] 0 olarak kalır.
1'den n'e kadar i için bits[i] değerini bits[i >> 1] + (i & 1) olarak ayarla.
bits değerini döndür.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Tuzaklar ve uç durumlar

n+1 yerine n kayıt döndürmek. n = 0 için yanıt [0] olur.
Operatör önceliği. Python, C, Java ve JavaScript'te +, & operatöründen daha yüksek önceliğe sahiptir; bu nedenle bits[i >> 1] + i & 1, (bits[i >> 1] + i) & 1 anlamına gelir. (i & 1) çevresindeki parantezleri koruyun.
bits[i >> 1] yerine bits[i-1] değerine bakmak. Komşular arasında basit bir kural yoktur: 7, üç tane 1 içeren 111; 8 ise bir tane 1 içeren 1000 şeklindedir.
Lua ve R'de diziler 1'den başlar; bu nedenle i için sayı i+1 indeksinde, i >> 1 için değer ise floor(i/2) + 1 indeksindedir. Lua 5.1'de kaydırma operatörü yoktur; bu nedenle math.floor(i / 2) kullanarak sayıyı yarıya indirin.

Sıkça sorulan sorular3

Counting Bits'in zaman karmaşıklığı nedir?

En iyi çözüm O(n) zamanda çalışır: n+1 girdinin her biri, daha önceki bir girdiden tek bir toplama işlemiyle elde edilir. Her sayının bitlerini ayrı ayrı saymak O(n log n) zaman alır. Her iki çözüm de çıktı dizisinin dışında O(1) bellek kullanır.

Counting Bits için başka bir O(n) bağıntı var mı?

Evet. i & (i-1), i değerinin en düşük 1 bitini temizler; bu nedenle 1 veya daha büyük her i için bits[i] = bits[i & (i-1)] + 1 olur. 12 için (1100), 12 & 11 sonucu 8’dir (1000); bunun bir tane 1 biti vardır, dolayısıyla 12’nin iki tane 1 biti vardır.

Dahili bir popcount işlevi kullanabilir miyim?

Java'daki Integer.bitCount veya C ve C++'taki __builtin_popcount gibi yöntemleri her sayı için çağırmak doğru bir yanıt verir. Görüşmeyi yapanlar genellikle bunu kullanmadan yapılan sürümü ister; çünkü problemin amacı, önceden hesapladığınız yanıtları yeniden kullanmaktır.

def countBits(n):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

n = 2

Beklenen Çıktı

[0, 1, 1]