Méditations LeetCode : compter les bits

La description de Counting Bits dit :

Étant donné un entier n, renvoie un tableau et de longueur n 1 tel que pour chaque i (0 <= i <= n) , ans[i] est le numéro de 1's dans la représentation binaire de i.

Par exemple :

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

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




</p>
<p>Ou :<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

---

Le problème veut que nous obtenions le nombre de 1 de la représentation binaire de chaque nombre de 0 à n.

La première solution que j'ai trouvée a été de créer un tableau de longueur n 1, de le remplir avec des valeurs de 0 à n en binaire...

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

...et mappez chacun au nombre de 1 bits dont il dispose :

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

---

Notez que dans le problème précédent, nous avons utilisé une technique pour compter le nombre de 1 bits (ou calculer son poids de Hamming) — il s'agit simplement de diminuer une valeur inférieure du nombre jusqu'à ce qu'il atteigne 0 :

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

---

On peut enchaîner les méthodes, et globalement, la solution ressemble à ça :

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;
  });
}

Ou, nous pouvons l'écrire plus explicitement, en poussant chaque décompte vers le tableau de résultats :

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

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

Complexité temporelle et spatiale

Le comptage des bits définis a $logn$log n complexité temporelle (dans le pire des cas, lorsque tous les bits sont définis, la boucle exécutera le nombre de bits dans BinaryNumber — le nombre de bits de la représentation binaire du nombre $n$n est $logn$log n ).
Mais nous le faisons aussi $n$n fois, donc globalement, la complexité temporelle sera $O(nlogn)$O(n log n) .

La complexité de l'espace est $O(n)$O(n) à mesure que le besoin d'espace pour notre tableau de résultats augmente à mesure que $n$n augmente.

---

Ensuite, nous examinerons Reverse Bits. En attendant, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!