先以2,3为例,它们的二进制分别是10、11,可以看到,忽略其二进制中最高位的1之后,这组数中二进制位为1的数量分别和数字0,1中二进制位为1的数量相同,再以4,5,6,7为例,他们的二进制分别是100、101、110、111,忽略其二进制中最高位的1之后,这组数中二进制位为1的数量分别和数字0,1,2,3中二进制位为1的数量相同,至此可以得出规律:
res[i+j]=res[j]+1;其中
i
为2
的幂次数(2,4,8
等等),j
的取值范围是[0,i);
class Solution { public int[] countBits(int n) { if(n==0) return new int[]{0}; if(n==1) return new int[]{0,1}; int[] res = new int[n+1]; res[0]=0;res[1]=1; for(int i=2;i<=n;){ for(int j=0;j<i;j++){ if(i+j<=n){ res[i+j]=res[j]+1; }else{ break; } } i=2*i; } return res; } }
标签:二进制位,二进制,比特,int,res,计数,LeetCode338,new From: https://www.cnblogs.com/rockdow/p/17647724.html