Meditasi LeetCode: Mengira Bit

Penerangan untuk Mengira Bit berkata:

Diberi integer n, kembalikan susunan ans panjang n 1 supaya untuk setiap i (0 <= i <= n) , ans[i] ialah nombor daripada 1's dalam perwakilan binari i.

Contohnya:

Input: n = 2
Output: [0, 1, 1]

Explanation:
0 --> 0
1 --> 1
2 --> 10




</p>
<p>Atau:<br>
</p>

<pre class="brush:php;toolbar:false">Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

---

Masalahnya mahu kita mendapatkan nombor 1s bagi perwakilan binari setiap nombor daripada 0 hingga n.

Penyelesaian pertama yang saya hasilkan ialah mencipta tatasusunan panjang n 1, isikan dengan nilai dari 0 hingga n dalam binari...

const arr = Array.from({ length: n + 1 }, (_, i) => i.toString(2));

...dan petakan setiap satu kepada bilangan 1 bit yang ada:

arr.map(j => {
  let result = 0;
  let binaryNumber = parseInt(j, 2);
  while (binaryNumber > 0) {
    binaryNumber &= binaryNumber - 1;
    result++;
  }
  return result;
});

---

Perhatikan bahawa dalam masalah sebelumnya, kami menggunakan teknik untuk mengira bilangan 1 bit (atau mengira Berat Hamming) — ia hanya mengurangkan satu nilai yang lebih rendah daripada nombor sehingga ia mencapai 0:

let numberOf1Bits = 0;
while (binaryNumber > 0) {
  binaryNumber &= binaryNumber - 1;
  numberOf1Bits++;
}

---

Kami boleh merantai kaedah, dan secara keseluruhan, penyelesaiannya kelihatan seperti ini:

function countBits(n: number): number[] {
  return Array.from({ length: n + 1 }, (_, i) => i.toString(2)).map(j => {
    let result = 0;
    let binaryNumber = parseInt(j, 2);
    while (binaryNumber > 0) {
      binaryNumber &= binaryNumber - 1;
      result++;
    }
    return result;
  });
}

Atau, kita boleh menulisnya dengan lebih jelas, menolak setiap kiraan ke tatasusunan hasil:

Input: n = 2
Output: [0, 1, 1]

Explanation:
0 --> 0
1 --> 1
2 --> 10

Kerumitan masa dan ruang

Mengira bit set mempunyai $logn$log n kerumitan masa (dalam kes paling teruk apabila semua bit ditetapkan, gelung akan menjalankan bilangan bit dalam binaryNumber — bilangan bit perwakilan binari nombor $n$n ialah $logn$log n ).
Walau bagaimanapun, kami juga melakukannya $n$n kali, jadi secara keseluruhan, kerumitan masa akan menjadi $O(nlogn)$O(n log n) .

Kerumitan ruang adalah $O(n)$O(n) kerana keperluan untuk ruang untuk tatasusunan hasil kami meningkat apabila $n$n bertambah.

---

Seterusnya, kita akan melihat Bit Songsang. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Mengira Bit. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!