首页 > 其他 > 详细

leetcode 338. Counting Bits

时间:2016-03-23 18:26:40      阅读:222      评论:0      收藏:0      [点我收藏+]

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
  • class Solution {
    
    public:
        vector<int> countBits(int num) {
            vector<int> count_v(num+1,0);
            for(int i = 1; i <= num;i++)
            {
                int x = i;
                int count=0;
                while(x)
                {
                    if((x & 1)==1) count++;
                    x >>= 1;
                }
                count_v[i] = count;
            }
            return count_v;
        }
    
    };

    注意:1.计算二进制中1的个数,难点在于时间复杂度。有三种基本求二进制1个数的方法:

  • (1)定理求解:取余数的方法,最慢。
  • (2)基本法(雾):值和1进行&操作,然后>>算术右移,仍然有两个循环。(即为本道题我的解法)
  • (3)快速法:n和n-1进行&操作,可以消去二进制最右的1,仍然有两个循环。(在191题中的解法)
  • 参考:http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

leetcode 338. Counting Bits

原文:http://www.cnblogs.com/dystopia/p/5312252.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!