338. 比特位計數（leetcode）

題目描述

給你一個整數 n ，對于 0 <= i <= n 中的每個 i ，計算其二進制表示中 1 的個數 ，返回一個長度為 n + 1 的數組 ans 作為答案。

示例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$

題解1（C++版本）

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n + 1, 0);for(int i = 1; i <= n; i++){for(int j = 0; j <= 20; j++){if(i & (1<<j)) ans[i]++;}}return ans;}
};

題解2（C++版本）

class Solution {
public:vector<int> countBits(int n) {vector<int> dp(n + 1, 0); // 對于一個二進制數來說，如果它的最低位為1,則它與 n/2 的 1 的個數相差1。 如果它的最低位為 0，則它與 n/2 的 1 的個數相同for(int i = 1; i <= n; i++){if(i & 1) dp[i] = dp[i/2] + 1;else dp[i] = dp[i/2];}return dp;}
};