leetcode 338. Counting Bits 位计算 + 统计二进制1的数量

迈不过友情╰ 2022-06-07 01:13 184阅读 0赞

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.

题意很简单，直接位运算即可。

代码如下：

import java.util.Arrays;
    
    /*
     * 第一种方法感觉想不出来，但是看起来很对
     * */
    class Solution
    {
        public int[] countBits(int num) 
        {
            if(num<0)
                return new int[0];
            int[] res=new int[num+1];
            Arrays.fill(res, 0);
            for(int i=1;i<=num;i++)
                res[i]=res[i&(i-1)]+1;
            return res;
        }
    
        /*
         * 这个是使用分解计算
         * */
        public int[] countBits22(int num) 
        {
            if(num<0)
                return new int[0];
            int[] res=new int[num+1];
            res[0]=0;
            for(int i=1;i<=num;i++)
                res[i]=getBit(i);    
            return res;
        }
    
        public int getBit(int num)
        {
            int count=0;
            while(num>0)
            {
                num=num&(num-1);
                count++;
            }
            return count;
        }
    }

下面是C++的做法，就是一个简单的位运算

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        vector<int> countBits(int num) 
        {
            vector<int> res(num + 1, 0);
            for (int i = 0; i <= num; i++)
            {
                int tmp = i;
                while (tmp != 0)
                {
                    tmp = tmp&(tmp - 1);
                    res[i]++;
                }
            }
            return res;
        }
    };