LeetCode-338. Counting Bits

LeetCode-338. Counting Bits

​​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 1:

Input: 2Output: [0,1,1]

Example 2:

Input: 5Output: [0,1,1,2,1,2]

Follow up:

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

题解：

根据1，2，4，8，……，2^n来分段处理，后一段的个数可以由前一段的个数+1得到。

class Solution {public: vector countBits(int num) { vector dp; dp.push_back(0); int bit = 0; int now = 1; for (int i = 1; i <= num; i++){ if (i == now){ dp.push_back(1); now = pow(2, ++bit); } else if (i < now){ dp.push_back(dp[i - now/2] + 1); } } return dp; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。