比特位计数

[编程题]比特位计数

热度指数：119 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例1

输入

输出

[0,1,1]

算法知识视频讲解

yyhaos

时间O(N)，腾讯TEG后端20秋招一面原题

vector<int> countBits(int num) {
    vector<int> ans(num+1,0);
    int th=1;
    for(int i=1;i<=num;i++){
        if(i<th){
            ans[i]=1+ans[i-th/2];
        }
        if(i==th){
            ans[i]=1;
            th*=2;
        }
    }
    return ans;
}

编辑于 2021-01-03 20:24:52 回复(1)

C/C++

2022115886

#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n;
    cin>>n;
    int dp[n+4];
    dp[0]=0;
    for(int i=0;i<=n;i++){
        if(i%2==0)
        dp[i]=dp[i/2];
        else
        dp[i]=dp[i-1]+1;
    }
    for(int i=0;i<=n;i++)
    cout<<dp[i]<<" ";
    return 0;
}

发表于 2023-07-04 12:34:01 回复(0)