Counting Bits

Q: Qual é a complexidade de tempo de Counting Bits?

A melhor solução é executada em tempo O(n): cada uma das n+1 entradas vem de uma entrada anterior com uma adição. Contar os bits de cada número individualmente leva O(n log n). Ambas usam O(1) de memória além do array de saída.

Q: Existe outra recorrência O(n) para contar bits?

Sim. i & (i-1) limpa o bit 1 menos significativo de i , então bits[i] = bits[i & (i-1)] + 1 para todo i maior ou igual a 1. Para 12 ( 1100 ), 12 & 11 é 8 ( 1000 ), que tem um bit 1, então 12 tem dois.

Q: Posso usar uma função popcount integrada?

Chamar uma função dessas para cada número, como Integer.bitCount em Java ou __builtin_popcount em C e C++, fornece uma resposta correta. Os entrevistadores geralmente pedem a versão sem isso, porque o objetivo do problema é reutilizar as respostas que você já calculou.

FácilManipulação de bits Programação dinâmica

+10

Dado um número inteiro não negativo n, retorne um array com n+1 elementos, em que o elemento i é o número de 1s na forma binária de i, para cada i de 0 a n.

Função

countBits(n: integer) → integer-array

ninteger: o último número a contar, 0 ou mais
Retornainteger-array: um array de n+1 contagens, em que a entrada i é o número de bits 1 em i

Restrições

0 ≤ n ≤ 2 × 10⁴

Exemplos

Entrada: n = 2
Saída: [0, 1, 1]
Explicação: Em binário, 0 é 0, 1 é 1 e 2 é 10: nenhum 1, depois um, depois um.

Entrada: n = 5
Saída: [0, 1, 1, 2, 1, 2]
Explicação: 3 é 11 e 5 é 101, dois 1s cada; 4 é 100, com um. Com 0, 1 e 2 do primeiro exemplo, as contagens são 0, 1, 1, 2, 1, 2.

Para ir além

Você consegue preencher todo o array em tempo O(n), sem usar uma função integrada que conte bits e sem contar cada número do zero?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Contar cada número do zero repete trabalho: 13 é 1101, os bits de 6 (110) com mais um dígito no final. Preencha as respostas em ordem crescente, e cada entrada reutiliza uma menor com uma adição.

Conte os bits de cada número

Intuição

Conte diretamente os bits 1 de cada número: adicione x & 1 a um contador, desloque x para a direita em um bit e pare em 0. Para 13 (1101), os bits são 1, 0, 1, 1, então a contagem é 3.

Um número até n tem cerca de log2 n dígitos binários, então a execução é O(n log n): cerca de 20.000 × 15 = 300.000 passos para n = 2 × 10^4.

Algoritmo

Inicie uma lista de resultados vazia.
Para cada i de 0 a n, defina count como 0 e x como i.
Enquanto x for maior que 0, adicione x & 1 a count e desloque x para a direita em uma posição.
Adicione count ao resultado.
Retorne o resultado.

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

Construa sobre metade do número

Intuição

Deslocar i uma posição para a direita remove seu último dígito binário, e i & 1 é esse dígito. Portanto, i tem os bits 1 de i >> 1 mais seu último dígito: bits[i] = bits[i >> 1] + (i & 1).

Para todo i maior ou igual a 1, i >> 1 é menor que i; assim, preencher o array da esquerda para a direita, começando em bits[0] = 0, significa que a entrada que você lê sempre está pronta. Para n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Cada entrada requer um deslocamento, um AND e uma adição: tempo O(n) e nenhuma memória além da saída.

Algoritmo

Crie um array bits com n+1 zeros. bits[0] permanece 0.
Para i de 1 a n, defina bits[i] como bits[i >> 1] + (i & 1).
Retorne 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

Armadilhas e casos extremos

Retornar n entradas em vez de n+1. Para n = 0, a resposta é [0].
Precedência de operadores. Em Python, C, Java e JavaScript, + tem precedência maior que &, então bits[i >> 1] + i & 1 significa (bits[i >> 1] + i) & 1. Mantenha os parênteses ao redor de (i & 1).
Consultar bits[i-1] em vez de bits[i >> 1]. Os números vizinhos não seguem uma regra simples: 7 é 111, com três 1s, e 8 é 1000, com um.
Em Lua e R, os arrays começam em 1, então a contagem de i fica no índice i+1, e a consulta de i >> 1 fica em floor(i/2) + 1. Lua 5.1 não tem operador de deslocamento, então divida por 2 usando math.floor(i / 2).

Perguntas frequentes3

Qual é a complexidade de tempo de Counting Bits?

A melhor solução é executada em tempo O(n): cada uma das n+1 entradas vem de uma entrada anterior com uma adição. Contar os bits de cada número individualmente leva O(n log n). Ambas usam O(1) de memória além do array de saída.

Existe outra recorrência O(n) para contar bits?

Sim. i & (i-1) limpa o bit 1 menos significativo de i, então bits[i] = bits[i & (i-1)] + 1 para todo i maior ou igual a 1. Para 12 (1100), 12 & 11 é 8 (1000), que tem um bit 1, então 12 tem dois.

Posso usar uma função popcount integrada?

Chamar uma função dessas para cada número, como Integer.bitCount em Java ou __builtin_popcount em C e C++, fornece uma resposta correta. Os entrevistadores geralmente pedem a versão sem isso, porque o objetivo do problema é reutilizar as respostas que você já calculou.

def countBits(n):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

n = 2

Saída Esperada

[0, 1, 1]