Counting Bits

Q: Jaka jest złożoność czasowa algorytmu Counting Bits?

Najlepsze rozwiązanie działa w czasie O(n): każdy z n+1 elementów pochodzi od jednego wcześniejszego elementu z jednym dodawaniem. Zliczanie bitów każdej liczby po jednym zajmuje O(n log n), ponieważ liczba nie większa niż n ma około log2 n cyfr binarnych. Oba rozwiązania wymagają O(1) pamięci poza tablicą wynikową.

Q: Dlaczego bits[i] = bits[i >> 1] + (i & 1) działa?

i >> 1 to i bez jego ostatniej cyfry binarnej, a i & 1 to usunięta cyfra. Jedynki w i to jedynki krótszej liczby plus ostatnia cyfra. Dla 11, czyli 1011 , krótszą liczbą jest 5 ( 101 , dwie jedynki), a ostatnia cyfra to 1, więc 11 ma trzy jedynki.

Q: Czy istnieje inna rekurencja O(n) dla zliczania bitów?

Tak. i & (i-1) zeruje najmłodszy bit 1 w i , więc dla każdego i większego lub równego 1 zachodzi bits[i] = bits[i & (i-1)] + 1 . Dla 12 ( 1100 ) 12 & 11 daje 8 ( 1000 ), które ma jedną jedynkę, więc 12 ma dwie. Ta metoda jest równie szybka jak reguła przesunięcia i używa tego samego wypełniania od lewej do prawej.

Q: Czy mogę użyć wbudowanej funkcji popcount?

Większość języków ma taką funkcję, na przykład Integer.bitCount w Javie lub __builtin_popcount w C i C++, a wywołanie jej dla każdej liczby daje poprawną odpowiedź. Osoby prowadzące rozmowy kwalifikacyjne zwykle proszą o wersję bez niej, ponieważ istotą problemu jest ponowne wykorzystywanie już obliczonych wyników. Zależność rekurencyjna działa również w językach, które nie mają takiej funkcji.

ŁatweOperacje na bitach Programowanie dynamiczne

+10

Otrzymujesz liczbę całkowitą n, która jest równa 0 lub większa. Dla każdej liczby i od 0 do n policz, ile jedynek pojawia się w zapisie binarnym liczby i. Zwróć wyniki jako tablicę zawierającą n+1 elementów, gdzie element i to liczba jedynek dla liczby i.

Funkcja

countBits(n: integer) → integer-array

ninteger: ostatnia liczba do odliczenia, 0 lub więcej
Zwracainteger-array: tablica n+1 liczników, gdzie element i to liczba bitów 1 w i

Ograniczenia

0 ≤ n ≤ 2 × 10⁴

Przykłady

Wejście: n = 2
Wyjście: [0, 1, 1]
Wyjaśnienie: W systemie binarnym 0 to 0, 1 to 1, a 2 to 10. To oznacza brak jedynek, potem jedną, a następnie jedną.

Wejście: n = 5
Wyjście: [0, 1, 1, 2, 1, 2]
Wyjaśnienie: 3 to 11, a 5 to 101 — oba mają po dwie jedynki, podczas gdy 4 to 100 z jedną jedynką. Uwzględniając 0, 1 i 2 z pierwszego przykładu, liczby jedynek dla liczb od 0 do 5 wynoszą: 0, 1, 1, 2, 1, 2.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz wypełnić całą tablicę w czasie O(n), bez wbudowanej funkcji zliczającej bity i bez zliczania każdej liczby od początku?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Liczenie jedynek w każdej liczbie osobno działa, ale powtarza część pracy. 13 to 1101, a 6 to 110: bity liczby 13 to bity liczby 6 z jedną dodatkową cyfrą na końcu. Jeśli uzupełnisz odpowiedzi w kolejności rosnącej, potrzebna liczba dla i będzie już w tablicy, a każda pozycja wymaga jednego dodawania.

Policz bity każdej liczby

Intuicja

Weź każdą liczbę od 0 do n i bezpośrednio policz jej bity 1. Najmłodszy bit liczby x to x & 1. Dodaj go do licznika, a następnie przesuń x w prawo za pomocą x >> 1, aby następny bit stał się najmłodszym. Zatrzymaj się, gdy x osiągnie 0.

Dla 13, czyli 1101, bity od prawej strony to 1, 0, 1, 1, więc ich liczba wynosi 3. Każda liczba wymaga jednego kroku na każdą cyfrę binarną, a liczba nie większa niż n ma około log2 n cyfr.

Całe działanie ma więc złożoność O(n log n). Dla n = 2 × 10^4 to około 20,000 × 15 = 300,000 kroków, co mieści się w limicie czasu. Nadal jednak wykonujemy niepotrzebną pracę: zliczanie bitów liczby 13 powtarza wszystkie kroki wykonane już dla 6. Złożoność pamięciowa wynosi O(1), nie licząc tablicy wynikowej.

Algorytm

Utwórz pustą listę wyników.
Dla każdego i od 0 do n ustaw count na 0, a x na i.
Gdy x jest większe od 0, dodaj x & 1 do count i przesuń x w prawo o jeden bit.
Dodaj count do wyników.
Zwróć wyniki.

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

Buduj na połowie liczby

Intuicja

Przesunięcie i w prawo o jeden usuwa jego ostatnią cyfrę binarną. Zatem i ma dokładnie tyle jedynek, co i >> 1, plus jedną, gdy jego ostatnia cyfra to 1. Tą ostatnią cyfrą jest i & 1, co daje regułę bits[i] = bits[i >> 1] + (i & 1).

Dla każdego i równego co najmniej 1, i >> 1 jest mniejsze od i. Jeśli wypełniasz tablicę od lewej do prawej, zaczynając od bits[0] = 0, wpis, którego szukasz, jest już zawsze wypełniony. To programowanie dynamiczne: każda odpowiedź jest budowana na podstawie mniejszej.

Dla n = 5: 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. Każdy wpis wymaga jednego przesunięcia, jednej operacji AND i jednego dodawania, więc czas działania wynosi O(n), a poza wynikiem nie potrzeba dodatkowej pamięci.

Algorytm

Utwórz tablicę bits z n+1 zerami. bits[0] pozostaje równe 0.
Dla i od 1 do n ustaw bits[i] na bits[i >> 1] + (i & 1).
Zwróć bits.

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

Pułapki i przypadki brzegowe

Reguła mieści się w jednym wierszu, więc błędy kryją się wokół niej.

Tablica ma n+1 elementów, a nie n. Dla n = 0 odpowiedzią jest [0]: jeden element, dla liczby 0.
Priorytet operatorów. W Pythonie, C, Javie i JavaScript operator + ma wyższy priorytet niż &, więc bits[i >> 1] + i & 1 jest odczytywane jako (bits[i >> 1] + i) & 1. Zachowaj nawiasy wokół (i & 1).
Odczytywanie bits[i-1] zamiast bits[i >> 1]. Sąsiednie liczby nie podlegają prostej regule: 7 to 111 z trzema jedynkami, a 8 to 1000 z jedną.
W Lua i R tablice zaczynają się od 1, więc liczba dla i znajduje się pod indeksem i+1, a odczyt dla i >> 1 pod indeksem floor(i/2) + 1. Lua w środowisku uruchomieniowym nie ma operatora przesunięcia, więc dziel przez 2, używając math.floor(i / 2).
Konwersja każdej liczby na ciąg binarny i zliczenie znaków 1 daje poprawną odpowiedź, ale tworzy nowy ciąg dla każdej liczby.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu Counting Bits?

Najlepsze rozwiązanie działa w czasie O(n): każdy z n+1 elementów pochodzi od jednego wcześniejszego elementu z jednym dodawaniem. Zliczanie bitów każdej liczby po jednym zajmuje O(n log n), ponieważ liczba nie większa niż n ma około log2 n cyfr binarnych. Oba rozwiązania wymagają O(1) pamięci poza tablicą wynikową.

Dlaczego bits[i] = bits[i >> 1] + (i & 1) działa?

i >> 1 to i bez jego ostatniej cyfry binarnej, a i & 1 to usunięta cyfra. Jedynki w i to jedynki krótszej liczby plus ostatnia cyfra. Dla 11, czyli 1011, krótszą liczbą jest 5 (101, dwie jedynki), a ostatnia cyfra to 1, więc 11 ma trzy jedynki.

Czy istnieje inna rekurencja O(n) dla zliczania bitów?

Tak. i & (i-1) zeruje najmłodszy bit 1 w i, więc dla każdego i większego lub równego 1 zachodzi bits[i] = bits[i & (i-1)] + 1. Dla 12 (1100) 12 & 11 daje 8 (1000), które ma jedną jedynkę, więc 12 ma dwie. Ta metoda jest równie szybka jak reguła przesunięcia i używa tego samego wypełniania od lewej do prawej.

Czy mogę użyć wbudowanej funkcji popcount?

Większość języków ma taką funkcję, na przykład Integer.bitCount w Javie lub __builtin_popcount w C i C++, a wywołanie jej dla każdej liczby daje poprawną odpowiedź. Osoby prowadzące rozmowy kwalifikacyjne zwykle proszą o wersję bez niej, ponieważ istotą problemu jest ponowne wykorzystywanie już obliczonych wyników. Zależność rekurencyjna działa również w językach, które nie mają takiej funkcji.

Python

def countBits(n):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

n = 2

Oczekiwane

[0, 1, 1]