Leetcode-338. 比特位计数

链接

力扣

题目

给你一个整数 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 <= 10e5

进阶

• 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
• 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

思路

我们可以先看一些例子：

• n=0  0000  0个1
• n=1  0001  1个1
• n=2  0010  1个1
• n=3  0011  2个1
• n=4  0100  1个1
• n=5  0101  2个1
• n=6  0110  2个1
• n=7  0111  3个1

我们很容易想到，当n为偶数，就相当于在比这个数小两倍的数的基础上左移一位，也就是在低位多加1个0，例如n=3时为0011，而n=6时为0110，n=4时为0100，而n=2时为0010，也因此res[i] = res[i / 2]。

对于奇数，我们同样可以在最大的小于该数的那个偶数上(n-1)低位+1得到，例如n=7时为0111，最大的小于7的偶数也就是6是0110,7就相当于在0110的最低位上加了个1变成了0111，这也就说明对于奇数res[i] = res[i-1] + 1。

由此我们可以发现规律其实很简单，可以据此写出代码。

Java Code

class Solution {
    public int[] countBits(int n) {
        int [] res = new int [n+1];
        for(int i=1;i<=n;i++){
            if(i%2==0) res[i]=res[i/2];
            else res[i]=res[i/2]+1;
        }
        return res;
    }
}