Counting Bits

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

En iyi çözüm O(n) zamanda çalışır: n+1 girdinin her biri, bir önceki girdiden tek bir toplama işlemiyle elde edilir. Her sayının bitlerini tek tek saymak O(n log n) zaman alır; çünkü n değerine kadar olan bir sayının yaklaşık log2 n ikili basamağı vardır. Her iki yöntem de çıktı dizisi dışında O(1) bellek kullanır.

Q: Neden bits[i] = bits[i >> 1] + (i & 1) işe yarıyor?

i >> 1 , son ikilik basamağı çıkarılmış i değeridir ve i & 1 , çıkarılan bu basamaktır. i değerindeki 1'lerin sayısı, daha kısa sayıdaki 1'lerin sayısı ile son basamağın toplamıdır. 1011 olan 11 için daha kısa sayı 5'tir ( 101 , iki tane 1) ve son basamak 1'dir; dolayısıyla 11'de üç tane 1 vardır.

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

Evet. i & (i-1) , i değerindeki 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 ); bu değerde bir tane 1 bulunduğundan, 12'de iki tane vardır. Kaydırma kuralı kadar hızlıdır ve aynı soldan sağa doldurma yöntemini kullanır.

Q: Yerleşik bir popcount işlevi kullanabilir miyim?

Java'daki Integer.bitCount veya C ve C++'taki __builtin_popcount gibi bir işlev çoğu dilde bulunur ve bunu her sayı için çağırmak doğru yanıtı verir. Görüşmeciler genellikle bu işlev olmadan yapılan sürümü ister, çünkü problemin amacı daha önce hesapladığınız yanıtları yeniden kullanmaktır. Özyineleme, böyle bir işlevin bulunmadığı dillerde de işe yarar.

KolayBit işlemleri Dinamik programlama

+10

0 veya daha büyük bir tam sayı olan n verilir. 0'dan n'e kadar olan her i sayısı için, i ikili sistemde yazıldığında kaç tane 1 bulunduğunu sayın. Sayıları, n+1 öğeden oluşan bir dizi olarak döndürün; burada i. öğe, i sayısı için bulunan adettir.

Fonksiyon

countBits(n: integer) → integer-array

ninteger: sayılacak son sayı, 0 veya daha fazla
Döndürürinteger-array: n+1 adet sayım içeren bir dizi; 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: İkilik sistemde 0, 0; 1, 1 ve 2, 10 şeklindedir. Yani önce hiç 1 yok, sonra bir tane, ardından bir tane.

Girdi: n = 5
Çıktı: [0, 1, 1, 2, 1, 2]
Açıklama: 3, 11 eder ve 5, 101 eder; ikisinde de ikişer 1 vardır. 4 ise tek bir 1 içeren 100 eder. İlk örnekteki 0, 1 ve 2 ile birlikte, 0'dan 5'e kadar olan sayıların 1 sayıları 0, 1, 1, 2, 1, 2'dir.

Gönderirken +15 gizli test

Ek soru

Yerleşik bir bit sayma işlevi kullanmadan ve her sayıyı baştan saymadan dizinin tamamını 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ının 1'lerini ayrı ayrı saymak işe yarar, ancak aynı işi tekrarlar. 13, 1101 ve 6, 110 şeklindedir: 13'ün bitleri, sonuna bir basamak daha eklenmiş 6'nın bitleridir. Yanıtları artan sırada doldurursanız, i için gereken sayı zaten dizidedir ve her girdi bir toplama işlemine mal olur.

Her sayının bitlerini say

Sezgi

0'dan n'e kadar her sayıyı ele al ve 1 bitlerini doğrudan say. x'in en düşük biti x & 1'dir. Bunu bir sayaca ekle, ardından sonraki bitin en düşük bit olması için x >> 1 ile x'i sağa kaydır. x 0'a ulaşınca dur.

13 için, yani 1101 için, bitler sağdan 1, 0, 1, 1 olarak gelir; dolayısıyla sayı 3'tür. Her sayı, ikili basamak başına bir adım gerektirir ve n'e kadar olan bir sayının yaklaşık log2 n basamağı vardır.

Bu, toplam çalışmayı O(n log n) yapar. n = 2 × 10^4 için yaklaşık 20.000 × 15 = 300.000 adım eder; bu da makul sürede çalışır. Yine de yapılan işin bir kısmı boşa gider: 13'ü saymak, 6 için zaten yaptığın her adımı tekrarlar. Çıktı dizisi dışında alan kullanımı O(1)'dir.

Algoritma

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

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ına ekle

Sezgi

i değerini bir bit sağa kaydırmak, son ikili basamağını siler. Bu nedenle i, i >> 1 değerindeki 1 bitlerinin aynısına sahiptir ve son basamağı 1 olduğunda bir 1 biti daha eklenir. Bu son basamak i & 1 değeridir ve şu kuralı verir: 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. Diziyi soldan sağa, bits[0] = 0 ile başlayarak doldurursan, eriştiğin değer her zaman önceden doldurulmuş olur. Bu dinamik programlamadır: her yanıt, daha küçük bir yanıttan oluşturulur.

n = 5 için: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. Her dizi öğesi bir kaydırma, bir AND ve bir toplama gerektirir; dolayısıyla zaman karmaşıklığı O(n)'dir ve çıktı dışında belleğe gerek yoktur.

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'i 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

Kural tek satıra sığıyor, bu yüzden hatalar etrafında gizleniyor.

Dizide n değil, n+1 öğe vardır. n = 0 için yanıt [0] olur: 0 sayısı için bir öğe.
İşlem önceliği. Python, C, Java ve JavaScript'te +, & işleminden daha yüksek önceliğe sahiptir; bu yüzden bits[i >> 1] + i & 1, (bits[i >> 1] + i) & 1 şeklinde okunur. (i & 1) çevresindeki parantezleri koruyun.
bits[i >> 1] yerine bits[i-1] değerine bakmak. Komşu sayılar 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şladığı için i sayısının adedi i+1 indeksinde, i >> 1 değerine bakma işlemi ise floor(i/2) + 1 indeksindedir. Çalıştırıcının Lua'sında kaydırma işleci yoktur; bu nedenle math.floor(i / 2) kullanarak ikiye bölün.
Her sayıyı ikili dizgeye dönüştürüp 1 karakterlerini saymak doğru yanıtı verir, ancak her sayı için yeni bir dizge oluşturur.

Sıkça sorulan sorular4

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

En iyi çözüm O(n) zamanda çalışır: n+1 girdinin her biri, bir önceki girdiden tek bir toplama işlemiyle elde edilir. Her sayının bitlerini tek tek saymak O(n log n) zaman alır; çünkü n değerine kadar olan bir sayının yaklaşık log2 n ikili basamağı vardır. Her iki yöntem de çıktı dizisi dışında O(1) bellek kullanır.

Neden bits[i] = bits[i >> 1] + (i & 1) işe yarıyor?

i >> 1, son ikilik basamağı çıkarılmış i değeridir ve i & 1, çıkarılan bu basamaktır. i değerindeki 1'lerin sayısı, daha kısa sayıdaki 1'lerin sayısı ile son basamağın toplamıdır. 1011 olan 11 için daha kısa sayı 5'tir (101, iki tane 1) ve son basamak 1'dir; dolayısıyla 11'de üç tane 1 vardır.

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

Evet. i & (i-1), i değerindeki 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); bu değerde bir tane 1 bulunduğundan, 12'de iki tane vardır. Kaydırma kuralı kadar hızlıdır ve aynı soldan sağa doldurma yöntemini kullanır.

Yerleşik bir popcount işlevi kullanabilir miyim?

Java'daki Integer.bitCount veya C ve C++'taki __builtin_popcount gibi bir işlev çoğu dilde bulunur ve bunu her sayı için çağırmak doğru yanıtı verir. Görüşmeciler genellikle bu işlev olmadan yapılan sürümü ister, çünkü problemin amacı daha önce hesapladığınız yanıtları yeniden kullanmaktır. Özyineleme, böyle bir işlevin bulunmadığı dillerde de işe yarar.

Python

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

Test durumları

Durum 1

Durum 2

Girdi

n = 2

Beklenen

[0, 1, 1]