算法题每日一练---第42天：比特位计数

一、问题描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组ans 作为答案。

题目链接：比特位计数

二、题目要求

样例

输入：n=5输出： [0,1,1,2,1,2]
解释：0-->01-->12-->103-->114-->1005-->101

考察

动态规划中等题型，规律归纳有点难
建议用时15~30min

三、问题分析

对于这道题目，一开始，遇到这一题根本没想到用递归，因为脑子笨规律找不到。直接for循环一个个转换成2进制，对有1的数字进行计数，最后输出结果。

提交也成功通过了，只是有点耗费时空复杂度。

做出了就行，但我看了关于动态规划的题解，我沉默了，真TM的好！

接下来接着用我们的三步走，老套路了，开干：

第一步 含义搞懂：

题目要求求出二进制中1的个数，那么dp[i]就代表i转换成二进制之后，存储的数字。

第二步 变量初始：

这一题只需要初始一个变量，那就是dp[0]=0

第三步 规律归纳：

0-->01-->12-->13-->24-->15-->26-->27-->38-->19-->210-->2

我把前十个数字分成奇数、偶数分别列出来，看看有什么区别：

如果i是偶数，dp[i]=dp[i/2]; 因为是2进制，偶数除以一个2，也没有多出来一个1。
如果i是奇数，dp[i]=dp[i/2]+1;奇数就是比偶数多出来一个1

三步走，打完收工！

四、编码实现

classSolution {
public:
vector<int>countBits(intn) {
longlonginti,k;//初始化变量vector<int>dp(n+1);//定义数组dp[0]=0;//第二步 变量初始for(i=1;i<=n;i++)
        {
if(i%2==0)//第三步 规律归纳dp[i]=dp[i/2];
elsedp[i]=dp[i/2]+1;
        }
returndp;//输出结果    }
};

五、测试结果

好家伙，执行用时直接少了2/3