设为首页 加入收藏

TOP

LeetCode:Counting Bits
2016-04-30 15:25:03 】 浏览:217
Tags:LeetCode:Counting Bits

Counting Bits


Total Accepted:18290Total Submissions:32984Difficulty:Medium

Given a non negative integer numbernum. For every numbersiin the range0 ≤ i ≤ numcalculate the number of 1's

in their binary representation and return them as an array.

Example:
Fornum = 5you should return[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.

    Hint:

    1. You should make use of what you have produced already.
    2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
    3. Or does the odd/even status of the number help you in calculating the number of 1s

      Credits:
      Special thanks to@ syedeefor adding this problem and creating all test cases.

      Subscribeto see which companies asked this question

      Hide Tags Dynamic Programming Bit Manipulation
      Hide Similar Problems (E) Number of 1 Bits

      直接贴讨论区的解答:

      Question: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.

      Thinking:

      1) We do not need check the input parameter, because the question has already mentioned that the number is non negative.

      2) How we do this The first idea come up with is find the pattern or rules for the result. Therefore, we can get following pattern

      Index :0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

      num :0 1 1 21 2 2 31 2 2 3 2 3 3 4

      Do you find the pattern

      Obviously, this is overlap sub problem, and we can come up the DP solution. For now, we need find the function to implement DP.

      dp[0] = 0;

      dp[1] = dp[0] + 1;

      dp[2] = dp[0] + 1;

      dp[3] = dp[1] + 1;

      dp[4] = dp[0] + 1;

      dp[5] = dp[1] + 1;

      dp[6] = dp[2] + 1;

      dp[7] = dp[3] + 1;

      dp[8] = dp[0] + 1; ...

      This is the function we get, now we need find the other pattern for the function to get the general function. After we analyze the above function, we can get dp[0] = 0;

      dp[1] = dp[1-1] + 1;

      dp[2] = dp[2-2] + 1;

      dp[3] = dp[3-2] + 1;

      dp[4] = dp[4-4] + 1;

      dp[5] = dp[5-4] + 1;

      dp[6] = dp[6-4] + 1;

      dp[7] = dp[7-4] + 1;

      dp[8] = dp[8-8] + 1; ..

      Obviously, we can find the pattern for above example, so now we get the general function

      dp[index] = dp[index - offset] + 1;


      code:

      class Solution {
      public:
          vector
                   
                     countBits(int num) {
              
              vector
                    
                      dp(num+1); dp[0] = 0; int offset = 1; for(int i=1;i
                      
                     
                    
                   
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇数据结构与算法――有向无环图的.. 下一篇2015级C++第10、11周实践项目 继..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目