Counting Bits

Q: Apa kompleksitas waktu Counting Bits?

Solusi terbaik berjalan dalam waktu O(n): setiap dari n+1 entri berasal dari satu entri sebelumnya dengan satu penjumlahan. Menghitung bit setiap angka satu per satu membutuhkan waktu O(n log n). Keduanya menggunakan memori O(1) di luar array output.

Q: Apakah ada relasi rekurensi O(n) lainnya untuk Menghitung Bit?

Ya. i & (i-1) menghapus bit 1 terendah dari i , jadi bits[i] = bits[i & (i-1)] + 1 untuk setiap i yang bernilai 1 atau lebih. Untuk 12 ( 1100 ), 12 & 11 bernilai 8 ( 1000 ), yang memiliki satu bit 1, jadi 12 memiliki dua bit 1.

Q: Bisakah saya menggunakan fungsi popcount bawaan?

Memanggil salah satunya untuk setiap angka, seperti Integer.bitCount di Java atau __builtin_popcount di C dan C++, menghasilkan jawaban yang benar. Pewawancara biasanya meminta versi tanpa itu, karena inti masalahnya adalah menggunakan kembali jawaban yang sudah kamu hitung.

MudahManipulasi bit Dynamic programming

+10

Diberikan bilangan bulat n yang bernilai 0 atau lebih, kembalikan array berisi n+1 entri, dengan entri i merupakan jumlah angka 1 dalam bentuk biner i, untuk setiap i dari 0 hingga n.

Fungsi

countBits(n: integer) → integer-array

ninteger: angka terakhir yang dihitung, 0 atau lebih
Mengembalikaninteger-array: sebuah array berisi n+1 hitungan, dengan entri i merupakan jumlah bit 1 dalam i

Batasan

0 ≤ n ≤ 2 × 10⁴

Contoh

Input: n = 2
Output: [0, 1, 1]
Penjelasan: Dalam biner, 0 adalah 0, 1 adalah 1 dan 2 adalah 10: tidak ada angka 1, lalu satu, lalu satu.

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Penjelasan: 3 adalah 11 dan 5 adalah 101, masing-masing memiliki dua angka 1; 4 adalah 100, dengan satu angka 1. Jika ditambah 0, 1, dan 2 dari contoh pertama, jumlahnya adalah 0, 1, 1, 2, 1, 2.

Pertanyaan lanjutan

Bisakah kamu mengisi seluruh array dalam waktu O(n), tanpa fungsi bawaan yang menghitung bit dan tanpa menghitung setiap angka dari awal?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Menghitung setiap angka dari awal mengulang pekerjaan: 13 adalah 1101, bit-bit dari 6 (110) dengan satu digit tambahan di akhir. Isi jawabannya secara berurutan dari yang terkecil, dan setiap entri menggunakan kembali nilai yang lebih kecil dengan satu penambahan.

Hitung bit setiap angka

Intuisi

Hitung bit 1 setiap angka secara langsung: tambahkan x & 1 ke sebuah penghitung, geser x ke kanan sebanyak satu posisi, lalu berhenti saat nilainya 0. Untuk 13 (1101), bit-bitnya menghasilkan 1, 0, 1, 1, jadi jumlahnya 3.

Angka hingga n memiliki sekitar log2 n digit biner, jadi prosesnya berjalan dalam O(n log n): sekitar 20.000 × 15 = 300.000 langkah untuk n = 2 × 10^4.

Algoritma

Mulai dengan list hasil yang kosong.
Untuk setiap i dari 0 hingga n, atur count menjadi 0 dan x menjadi i.
Selama x lebih besar dari 0, tambahkan x & 1 ke count dan geser x ke kanan sebanyak satu bit.
Tambahkan count ke hasil.
Kembalikan hasilnya.

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

Bangun berdasarkan setengah dari jumlah tersebut

Intuisi

Menggeser i ke kanan satu posisi menghapus digit biner terakhirnya, dan i & 1 adalah digit tersebut. Jadi, i memiliki digit 1 dari i >> 1 ditambah digit terakhirnya: bits[i] = bits[i >> 1] + (i & 1).

Untuk setiap i yang bernilai 1 atau lebih, i >> 1 lebih kecil daripada i, jadi mengisi array dari kiri ke kanan, dimulai dari bits[0] = 0, berarti entri yang kamu baca selalu siap. Untuk n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Setiap entri memerlukan satu operasi shift, satu operasi AND, dan satu penjumlahan: waktu O(n) dan tanpa memori tambahan selain output.

Algoritma

Buat array bits berisi n+1 angka nol. bits[0] tetap 0.
Untuk i dari 1 hingga n, atur bits[i] menjadi bits[i >> 1] + (i & 1).
Kembalikan 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

Jebakan dan kasus tepi

Mengembalikan n entri, bukan n+1. Untuk n = 0, jawabannya adalah [0].
Prioritas operator. Dalam Python, C, Java, dan JavaScript, + memiliki prioritas lebih tinggi daripada &, jadi bits[i >> 1] + i & 1 berarti (bits[i >> 1] + i) & 1. Pertahankan tanda kurung di sekitar (i & 1).
Mencari bits[i-1], bukan bits[i >> 1]. Bilangan yang bersebelahan tidak memiliki aturan sederhana yang sama: 7 adalah 111 dengan tiga angka 1, sedangkan 8 adalah 1000 dengan satu angka 1.
Dalam Lua dan R, array dimulai dari 1, jadi hitungan untuk i berada pada indeks i+1 dan pencarian untuk i >> 1 berada pada indeks floor(i/2) + 1. Lua 5.1 tidak memiliki operator geser, jadi bagi dengan 2 menggunakan math.floor(i / 2).

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Counting Bits?

Solusi terbaik berjalan dalam waktu O(n): setiap dari n+1 entri berasal dari satu entri sebelumnya dengan satu penjumlahan. Menghitung bit setiap angka satu per satu membutuhkan waktu O(n log n). Keduanya menggunakan memori O(1) di luar array output.

Apakah ada relasi rekurensi O(n) lainnya untuk Menghitung Bit?

Ya. i & (i-1) menghapus bit 1 terendah dari i, jadi bits[i] = bits[i & (i-1)] + 1 untuk setiap i yang bernilai 1 atau lebih. Untuk 12 (1100), 12 & 11 bernilai 8 (1000), yang memiliki satu bit 1, jadi 12 memiliki dua bit 1.

Bisakah saya menggunakan fungsi popcount bawaan?

Memanggil salah satunya untuk setiap angka, seperti Integer.bitCount di Java atau __builtin_popcount di C dan C++, menghasilkan jawaban yang benar. Pewawancara biasanya meminta versi tanpa itu, karena inti masalahnya adalah menggunakan kembali jawaban yang sudah kamu hitung.

def countBits(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 2

Output yang diharapkan

[0, 1, 1]