系列文章目录
前言
每天进步一点点！！
一、背景
理解一下题目的意思，就是返回一个数组，这个数组中的每个元素都是（0-n）化为二进制数中1的个数。
二、我的思路（异或，逐位判断）
利用前面做的题目的思路，采用移位的办法，获取某元素每一个比特位的值，即0或1。
怎么判断一个比特位是0还是1呢？
我采用的办法是用1去跟那个比特位异或操作，操作下来的结果小于原数，说明那个比特位是1（因为1^1=0，故而会比原来的数更小）
对于每个元素都如此，则可以加个外循环即可！！
class Solution {
public:
vector<int> countBits(int n) {
if(n==0)
return {0};
vector<int> ans(n+1,0);
int bitMax=31;//记录最大数项的最多bit位是多少（从0开始索引）
while(!(n>>bitMax))
{
bitMax-=1;
}
//cout<<bitMax<<endl;
for(int i=0; i<=n ;i++)
{
for (int bit=0;bit<=bitMax;bit++)
{
//i的每一位分别与1进行异或，
//如果i的那位是1，异或下来的结果a<i;反之，那位是0，那么a>i
int a= i^(1<<bit);
if (a<i)
{
ans[i]+=1;
}
}
}
return ans;
}
};
三、官方的思路
1.动态规划，最高有效位
class Solution {
public:
vector<int> countBits(int n) {
//动态规划，最高有效位
//动态规划的境界就是当前所求，与前面的某些值有关系，
//不一定相邻，只需要在其前面即可
//原理，如果y代表x的二进制最高有效位，
//那么ans[x]=1+ans[x-y],因为y是最高有效位，那么它必然是1，所以是1+……
vector<int> ans(n+1,0);
int y;//维护一个最高位y,不过这个y是十进制数
for(int i=1;i<=n;i++)
{
//如何求得y呢?即i&(i-1)) ==0
if( (i&(i-1)) ==0 )
{
y=i;
}
ans[i]=ans[i-y]+1;//这样就到达了利用前面以求得数的目的了
}
return ans;
}
};
2.动态规划，右移大法
class Solution {
public:
vector<int> countBits(int n) {
//动态规划，网友牛逼
vector<int> ans(n+1,0);
for(int i=1;i<=n;i++)
{
//如果是偶数，表明能够右移一次或以上，右移后1的数量不变
//什么时候能一直右移呢，就是2的几次方的时候
//再就是考虑奇数的情况，奇数右移，明显会损失1，从而加上1即可
if(i%2==0)
{
ans[i]=ans[i/2];
}
else
{
ans[i]=ans[i/2]+1;
}
}
return ans;
}
};
3.动态规划，最低有效位
class Solution {
public:
vector<int> countBits(int n) {
//动态规划，最低设置位
vector<int> ans(n+1,0);
for(int i=1;i<=n;i++)
{
//令x=i&(i-1)，意思是把x的二进制位右起第一个1置为0，所以x<i
//而x的二进制相比i,只少了一个二进制位的1，具体这个1在什么位置不用管
ans[i]=ans[i&(i-1) ] +1;
}
return ans;
}
};
总结
动态规划的境界就是当前所求，与前面的某些值有关系，不一定相邻，只需要在其前面即可！！