338.Counting Bits

tags: Easy DP Bit Manipulation

338. Counting Bits

題目描述

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

範例

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

• 0 <= n <= 10⁵

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

解答

C#

public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1]; 
        if (n == 0) return ans;
        
        ans[1] = 1;
        for (int threshold = 2; threshold <= n; threshold <<= 1) {
            ans[threshold] = 1;
            for (int i = threshold + 1; i <= n && i < (threshold << 1); i++) {
                ans[i] = 1 + ans[i - threshold];
            }
        }

        return ans;
    }
}

public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1]; 
        if (n == 0) return ans;

        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }

        return ans;
    }
}

Reference

JimSep 1, 2023

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        bound = 1
        k = 0
        for i in range(1, n + 1):
            ans[i] = ans[k] + 1
            k += 1
            if k == bound:
                k = 0
                bound *= 2
        return ans

Yen-Chi ChenFri, Sep 1, 2023

C++

class Solution {
public:
    vector<int> countBits(int n) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        
        vector<int> ans;
        for (int num = 0; num <= n; num ++) {
            ans.push_back(parallelBitCount(num));
        }
        return ans;
    }

    int parallelBitCount(uint32_t n) {
        n = ( n & 0x55555555 ) + ( ( n >> 1 ) & 0x55555555 );
        n = ( n & 0x33333333 ) + ( ( n >> 2 ) & 0x33333333 );
        return ((( n + (n >> 4) ) & 0x0f0f0f0f ) * 0x01010101) >> 24;
    }
};

Jerry WuFir, Sep 1, 2023

回到題目列表