LeetCode 冥想：計算比特

計數位的描述如下：

給定一個整數n，回傳一個陣列 ans 長度 n 1 這樣對於每個 i (0 , ans[i] 是數字 1 的 在 的二進位表示中 i.

例如：

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

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

或：

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

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

---

該問題要求我們取得從 0 到 n 的每個數字的二進位表示形式中 1 的數量。

我想到的第一個解決方案是創建一個長度為 n 1 的數組，用二進制的 0 到 n 的值填充它......

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

...並將每一位對應到它所擁有的 1 位數：

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

---

請注意，在上一個問題中，我們使用了一種技術來計算1 位的數量（或計算其漢明權重）——它只是從數字中減去一個較小的值，直到達到0：

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

---

我們可以連結這些方法，總的來說，解決方案如下所示：

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

或者，我們可以更明確地寫它，將每個計數推送到結果數組：

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

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

時間與空間複雜度

對設定的位元進行計數有 $logg$登入 時間複雜度（在最壞的情況下，當所有位元都已設定時，循環將運行 binaryNumber 中的位數 — 數字的二進位表示形式的位數 $n$nn > 是 $lo\text{g} 登入n$登入
). 然而我們也這樣做 $n$nn$>O\text{(}n nn o$g n

)

O(n log $\mathrm{O(n log n)}.空間複雜度為$O(n)$n)O(n🎜>$O(n) 隨著結果數組對空間的需求增加

---

nn nn > 增加。 接下來，我們將看看反向位。在那之前，祝您編碼愉快。

以上是LeetCode 冥想：計算比特的詳細內容。更多資訊請關注PHP中文網其他相關文章！