【leetcode】经典算法题-Counting Bits

题目描述:

给定一个数字n,统计0~n之间的数字二进制的1的个数,并用数组输出

例子:

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

要求:

  • 算法复杂复o(n)
  • 空间复杂度o(n)

原文描述:

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.

思路分析:

  • 根据题目的要求,时间和空间复杂度,明显是要动态规划的方法
  • 得出推到公式:f(n) = 不大于f(n)的最大的2的次方+f(k),k一定是在前面出现的,用数组记录,直接查询
  • 举例f(5) = f(4)+ f(1),注意2de次方都是一个1,而且是最高位,f(5) = 1+f(1),f(6) = 1+f(2)直到f(8) = 1

代码:

public class Solution {    public int[] countBits(int num) {        int[] res = new int[num+1];        int pow2 = 1,before =1;        for(int i=1;i<=num;i++){            if (i == pow2){                before = res[i] = 1;                pow2 <<= 1;            }            else{                res[i] = res[before] + 1;                before += 1;            }        }        return res;    }}

我的微信二维码如下,欢迎交流讨论

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下: