leetcode-338-Counting-Bits

发表于   |  

描述

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

分析

在191题中，已经有求得某个数（写成2进制）1出现的次数的方法，如果用这种方法的话，复杂度是：$O(n*sizeof(integer))$（乘以的常数不考虑），而题目中提示复杂度可以达到$O(n)$，其实还是要用到动态规划的思想，公式是这样的：$[2^{i-1}, 2^i-1]$中的值等于$[0, 2^{i-1}-1]$的值加1。比如[0,1]对应的值是0,1，接下来算[2,3]对应的值，等于1,2，[0,1,2,3]对应的是0,1,1,2，所以[4,5,6,7]对应的是1,2,2,3。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> result(num+1, 0);
        int i = 1;
        int base = 1;
        
        while(i <= num) {
            for(int j=0; j<base && i<=num; j++) {
                result[i++] = result[j] + 1;
            }
            base <<= 1;
        }
        return result;
    }
};

相关问题

(E) Number of 1 Bits

题目来源