一魚多吃 用DP來數有幾個bit 1_Counting Bits Leetcode #338 精選75題

Alexander Sinn on Unsplash

題目敘述

題目會給定我們一個n值，要求我們列出從0 ~ n 之間，每個整數有幾個bit1，以陣列的形式返回答案。

例如n=3時

因為

0 = 0b 0

1 = 0b 1

2 = 0b 10

3 = 0b 11

輸出答案為[0, 1, 1, 2]

題目的原文敘述

測試範例

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

約束條件

Constraints:

• 0 <= n <= 10^5

 輸入n值介於 0 ~ 十萬之間。

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?

很容易有一個直覺的解法是暴力掃描過每個整數的每個bit，複雜度為O( n log n)。

請問您能想到一個O(n)的演算法嗎?

• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

請問您能不要使用內建的數bit function嗎?