[LeetCode] 0338. 비트 계산

정수가 주어지면 N, 반품 배열 답변 길이의 n+1 그렇게 각각 나 (0 <= 나는 <= n), 답변[i] 은 수 1'에스 이진 표현에서 나.

예시 1:

입력: n=2
산출: [0,1,1]
설명:
0 --> 0 1 --> 1 2 --> 10

예 2:

입력: n=5
산출: [0,1,1,2,1,2]
설명:
0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

제약:

• 0 <= n <= 10 5

후속 조치:

• 런타임을 사용하여 솔루션을 찾는 것은 매우 쉽습니다. O(n로그n). 선형 시간에 할 수 있습니까? 에) 그리고 아마도 한 번에 통과할 수 있을까요?
• 내장된 함수(예: __builtin_popcount C++에서)?