LeetCode 338 Counting Bits
题意
给出一个num，输出0到num整数二进制形式中包含1的个数
要求
时间复杂度比简单方法的O(n*sizeof(integer))好 空间复杂度O（n）
题解
0：000 1：001 2：010 3：011 4：100 5：101 递推公式： res[1]=res[0]+1; res[2]=res[0]+1; res[3]=res[1]+1; res[4]=res[0]+1; res[5]=res[1]+1; 原理：每次去掉i的二进制形式中最高位的1，取去掉后的数中1的个数，加1就是原数1的个数。
class Solution { public: vector<int> countBits(int num) { vector<int>res; res.resize(num+1); res[0] = 0; int count = 0,mod; for(int i = 1;i <= num;++ i) { if(count == 0) { count = i; mod = i; } count --; res[i] = res[i % mod] +1; } return res; } };