LeetCode-Meditationen: Bits zählen

Die Beschreibung für Counting Bits lautet:

Gegeben eine ganze Zahl n, gib ein Array ans der Länge n 1 zurück so dass für jedes i (0 <= i <= n) , ans[i] ist die Nummer von 1's in der binären Darstellung von i.

Zum Beispiel:

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

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




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

---

Das Problem möchte, dass wir die Anzahl der Einsen der binären Darstellung jeder Zahl von 0 bis n erhalten.

Die erste Lösung, die ich mir ausgedacht habe, bestand darin, ein Array der Länge n 1 zu erstellen und es mit binären Werten von 0 bis n zu füllen...

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

...und ordne jedes einzelne der Anzahl von 1-Bits zu, die es hat:

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

---

Beachten Sie, dass wir im vorherigen Problem eine Technik verwendet haben, um die Anzahl der 1-Bits zu zählen (oder ihr Hamming-Gewicht zu berechnen) – dabei wird einfach ein kleinerer Wert von der Zahl verringert, bis sie erreicht ist 0:

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

---

Wir können die Methoden verketten und insgesamt sieht die Lösung so aus:

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

Oder wir können es expliziter schreiben und jede Zählung in das Ergebnisarray übertragen:

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

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

Zeit- und Raumkomplexität

Das Zählen der gesetzten Bits hat $logn$log n Zeitkomplexität (im schlimmsten Fall, wenn alle Bits gesetzt sind, führt die Schleife die Anzahl der Bits in „binaryNumber“ aus – die Anzahl der Bits der binären Darstellung von Zahl $n$n Ist $logn$log n ).
Wir machen es aber auch $n$n Zeiten, also insgesamt wird die Zeitkomplexität sein $O(nlogn)$O(n log n) .

Die räumliche Komplexität ist $O(n)$O(n) da der Platzbedarf für unser Ergebnisarray zunimmt $n$n erhöht.

---

Als nächstes werfen wir einen Blick auf Reverse Bits. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Bits zählen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!