題目描述
給定一個非負(fù)整數(shù) num。對于 0 ≤ i ≤ num 范圍中的每個數(shù)字 i ，計算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回冯吓。
輸入: 2
輸出: [0,1,1]
輸入: 5
輸出: [0,1,1,2,1,2]
問題分析
1.暴力計算
2.奇偶分類
對于所有的數(shù)字功舀，只有兩類：
奇數(shù)：二進(jìn)制表示中，奇數(shù)一定比前面那個偶數(shù)多一個 1鲁豪，因為多的就是最低位的 1。
舉例：
0 = 0 1 = 1
2 = 10 3 = 11
偶數(shù)：二進(jìn)制表示中律秃，偶數(shù)中 1 的個數(shù)一定和除以 2 之后的那個數(shù)一樣多爬橡。因為最低位是 0，除以 2 就是右移一位棒动，也就是把那個 0 抹掉而已糙申，所以 1 的個數(shù)是不變的。
舉例：
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
解題思路1
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans(num + 1);
ans[0] = 0;
for (int i = 1; i <= num; i++)
{
//奇數(shù)
if (i % 2 == 1)
{
ans[i] = ans[i - 1] + 1;
}
else
{
ans[i] = ans[i / 2];
}
}
return ans;
}
};
