題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/counting-bits
給定一個非負整數(shù) num笼才。對于 0 ≤ i ≤ num 范圍中的每個數(shù)字 i 漱受，計算其二進制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。
示例 1:
輸入: 2
輸出: [0,1,1]
示例 2:
輸入: 5
輸出: [0,1,1,2,1,2]
進階:
- 給出時間復雜度為O(n*sizeof(integer))的解答非常容易患整。但你可以在線性時間O(n)內用一趟掃描做到嗎拜效？
- 要求算法的空間復雜度為O(n)。
- 你能進一步完善解法嗎各谚？要求在C++或任何其他語言中不使用任何內置函數(shù)（如 C++ 中的 __builtin_popcount）來執(zhí)行此操作紧憾。
暴力解法：
class Solution {
public int[] countBits(int num) {
int[] ans = new int[num+1];
for(int i=0;i<=num;i++){
ans[i] = getZeroCount(i);
}
return ans;
}
private int getZeroCount(int num){
int count = 0;
while(num != 0){
int tmp = num&1;
if(tmp == 1){
count++;
}
num = num>>1;
}
return count;
}
}
動態(tài)規(guī)劃解法：
class Solution {
public int[] countBits(int num) {
if(num < 1)
return new int[]{0};
int[] dp = new int[num+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=num;i++){
//最后一位是否是1
int last = i&1;
dp[i] = last + dp[i>>1];
}
return dp;
}
}
