LeetCode 명상: 비트 계산

비트 계산에 대한 설명은 다음과 같습니다.

정수 n이 주어지면 길이 n 1 각 i(0 <= i <= n)에 대해 배열 ans 를 반환합니다. , ans[i] 는 번호입니다 1의를

i.

의 이진 표현으로 표현한 것입니다.

예:

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

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


</p>
<p>



<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

---

문제는 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

시간과 공간의 복잡성

설정된 비트 수를 세는 것은 $logn$로그 n 시간 복잡도(모든 비트가 설정된 최악의 경우 루프는 BinaryNumber의 비트 수 - 숫자의 이진 표현의 비트 수)를 실행합니다. $n$n ~이다 $logn$로그 n ).
그러나 우리도 그렇게 합니다. $n$n 시간이므로 전체적으로 시간 복잡도는 다음과 같습니다. $오(nlogn)$O(n log n) .

공간 복잡도는 $O(n)$O(n) 결과 배열을 위한 공간의 필요성이 증가함에 따라 $n$n 증가합니다.

---

다음으로는 Reverse Bits에 대해 살펴보겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 비트 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!