LeetCode 瞑想: ビットを数える

ビットのカウントの説明には次のように書かれています:

整数 n を指定すると、長さ n 1 の配列を返します。各 i (0 、 ans[i] は の数字ですof 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 までの各数値の 2 進表現の 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 ビットの数を数える (またはその ハミング重み を計算する) テクニックを使用したことに注意してください。これは、数値が 1 に達するまで、数値から 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

時間と空間の複雑さ

設定されたビットをカウントすると、 $logn$ログ 時間計算量 (すべてのビットが設定されている最悪の場合、ループは binaryNumber のビット数 (数値の 2 進表現のビット数) を実行します) $n$n は $logn$ログ ).
ただし、私たちもやってます $n$n したがって、全体的な時間計算量は次のようになります。 $O(nlogn)$O(n log n) .

空間の複雑さは $O(n)$O(n) 結果配列のためのスペースの必要性が増加するため、 $n$n 増加します。

---

次に、リバース ビットについて見ていきます。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: ビットを数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。