Counting Bits

Q: Jaka jest złożoność czasowa algorytmu zliczania bitów?

Najlepsze rozwiązanie działa w czasie O(n): każdy z n+1 wpisów powstaje z jednego wcześniejszego wpisu przez dodanie jedynki. Zliczanie bitów każdej liczby osobno zajmuje O(n log n). Oba rozwiązania wykorzystują O(1) pamięci poza tablicą wynikową.

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

Tak. i & (i-1) zeruje najniższy bit 1 w i , więc bits[i] = bits[i & (i-1)] + 1 dla każdego i większego lub równego 1. Dla 12 ( 1100 ) 12 & 11 wynosi 8 ( 1000 ), które zawiera jedną jedynkę, więc 12 zawiera dwie.

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

Wywołanie jej dla każdej liczby, na przykład Integer.bitCount w Javie lub __builtin_popcount w C i C++, daje poprawną odpowiedź. Osoby prowadzące rozmowę kwalifikacyjną zwykle proszą o wersję bez niej, ponieważ istotą problemu jest ponowne wykorzystanie już obliczonych odpowiedzi.

ŁatweOperacje na bitach Programowanie dynamiczne

+10

Dla danej liczby całkowitej n, która jest równa 0 lub większa, zwróć tablicę zawierającą n+1 elementów, w której element i jest liczbą jedynek w binarnym zapisie liczby i, dla każdej wartości i od 0 do n.

Funkcja

countBits(n: integer) → integer-array

ninteger: ostatnia liczba do zliczenia, 0 lub więcej
Zwracainteger-array: tablica n+1 liczników, gdzie element i jest liczbą bitów o wartości 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: brak jedynek, potem jedna, a następnie jedna.

Wejście: n = 5
Wyjście: [0, 1, 1, 2, 1, 2]
Wyjaśnienie: 3 to 11, a 5 to 101 — po dwie jedynki; 4 to 100 — jedna. Dla 0, 1 i 2 z pierwszego przykładu liczby jedynek wynoszą 0, 1, 1, 2, 1, 2.

Pytanie dodatkowe

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

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Liczenie każdej liczby od zera powtarza pracę: 13 to 1101, bity liczby 6 (110) z jedną dodatkową cyfrą na końcu. Wpisuj odpowiedzi w kolejności rosnącej, a każdy kolejny wpis wykorzystuje mniejszą wartość i jedno dodawanie.

Policz bity każdej liczby

Intuicja

Policz bezpośrednio jedynki w zapisie binarnym każdej liczby: dodaj x & 1 do licznika, przesuń x w prawo o jeden bit i zakończ na 0. Dla 13 (1101) bity to kolejno 1, 0, 1, 1, więc ich liczba wynosi 3.

Liczba nie większa niż n ma około log2 n cyfr binarnych, więc działanie ma złożoność O(n log n): około 20 000 × 15 = 300 000 kroków dla n = 2 × 10^4.

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 wyniku.
Zwróć wynik.

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

Zbuduj na połowie liczby

Intuicja

Przesunięcie i w prawo o jeden usuwa jego ostatnią cyfrę binarną, a i & 1 to ta cyfra. Zatem i ma jedynki z i >> 1 plus swoją ostatnią cyfrę: bits[i] = bits[i >> 1] + (i & 1).

Dla każdego i większego lub równego 1 wartość i >> 1 jest mniejsza niż i, więc wypełnianie tablicy od lewej do prawej, zaczynając od bits[0] = 0, oznacza, że odczytywany wpis jest zawsze gotowy. Dla n = 5: 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, jednego AND i jednego dodawania: czas O(n) i brak dodatkowej pamięci poza wynikiem.

Algorytm

Utwórz tablicę bits złożoną z n+1 zer. 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

Zwrócenie n elementów zamiast n+1. Dla n = 0 odpowiedzią jest [0].
Kolejność operatorów. W Pythonie, C, Javie i JavaScript operator + ma wyższy priorytet niż &, więc bits[i >> 1] + i & 1 oznacza (bits[i >> 1] + i) & 1. Zachowaj nawiasy wokół (i & 1).
Odczytywanie bits[i-1] zamiast bits[i >> 1]. Sąsiednie liczby nie mają prostej wspólnej reguły: 7 to 111 z trzema jedynkami, a 8 to 1000 z jedną.
W Lua i R tablice zaczynają się od indeksu 1, więc liczba jedynek dla i znajduje się pod indeksem i+1, a odczyt dla i >> 1 pod indeksem floor(i/2) + 1. Lua 5.1 nie ma operatora przesunięcia, więc dziel przez 2, używając math.floor(i / 2).

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu zliczania bitów?

Najlepsze rozwiązanie działa w czasie O(n): każdy z n+1 wpisów powstaje z jednego wcześniejszego wpisu przez dodanie jedynki. Zliczanie bitów każdej liczby osobno zajmuje O(n log n). Oba rozwiązania wykorzystują O(1) pamięci poza tablicą wynikową.

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

Tak. i & (i-1) zeruje najniższy bit 1 w i, więc bits[i] = bits[i & (i-1)] + 1 dla każdego i większego lub równego 1. Dla 12 (1100) 12 & 11 wynosi 8 (1000), które zawiera jedną jedynkę, więc 12 zawiera dwie.

Czy mogę użyć wbudowanej funkcji popcount?

Wywołanie jej dla każdej liczby, na przykład Integer.bitCount w Javie lub __builtin_popcount w C i C++, daje poprawną odpowiedź. Osoby prowadzące rozmowę kwalifikacyjną zwykle proszą o wersję bez niej, ponieważ istotą problemu jest ponowne wykorzystanie już obliczonych odpowiedzi.

def countBits(n):
    # Napisz kod tutaj

Test #1

Test #2

Argument

n = 2

Oczekiwany wynik

[0, 1, 1]