平阳门户网站建设/线下引流推广方法

力扣338题：比特位计数

题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

输入输出样例

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

解法一，常规思路，十进制转换成二进制再计算1的个数

class Solution{
public:
//十进制转换二进制的算法，是除2取余，逆序排序vector<int>countBits(int n){vector<int>res;for(int i=0;i<=n;i++){//将十进制数转换成二进制int binaryNum=decimalToBinary(i);//统计二进制数中1的个数res.push_back(countBitsNum(binaryNum));}return res;}int countBitsNum(int nums){int count=0;while(nums){int remainder=nums%10;int merchant=nums/10;if(remainder){count++;}nums/=10;}return count;}//将十进制数转化为二进制int decimalToBinary(int nums){int remainder=nums%2;int merchant=nums/2;if(merchant!=0){int res=decimalToBinary(merchant)*10+remainder;return res;}return remainder;}
};

解法二，动态规划+数字的奇偶性

class Solution2
{
public:vector<int>countBits(int n){vector<int>res(n+1);//初始化数组res[0]=0;//二进制中奇数一定比之前的偶数多一个1//二进制中偶数中的1的个数一定和除以2之后的个数一样多for(int i=1;i<=n;i++){if(i%2==1){res[i]=res[i-1]+1;}else{res[i]=res[i/2];}}return res;}
};

解法三，Brain Kernighan算法

//使用Brian Kernighan算法：对于任意整数x,令x=x&(x-1),该运算将x的二进制表示的最后一个1变成0,因此
//对x重复进行该操作，直到x变成0,则操作次数即为x的一比特数
//时间复杂度O(nLOGn)vector<int>countBits(int n){vector<int>res(n+1);//初始化数组for(int i=1;i<=n;i++){res[i]=countOnes(i);}return res;}int countOnes(int x){int one=0;while(x>0){x&=(x-1);one++;}return one;}

解法四，动态规划+最高有效位

//动态规划最高有效位vector<int>countBits2(int n){vector<int>res(n+1);int highBit=0;//初始化数组for(int i=1;i<=n;i++){//其代表最高有效位发生变化，即4==100 3=011//记录此时的最高有效位if((i&(i-1))==0){highBit=i;}res[i]=res[i-highBit]+1;}return res;}