剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

1. 暴力解法

   非常常规。

   主题思想：通过位运算来判断（与1 做& 运算），为1加1，然后将数右移，直到该数字右移至大小为0时停止，进行下一个数的判断；

   class Solution {
   public int[] countBits(int n) {
   int []
   t = new int[n+1];
   t[0]=0;
   for(int i=0;i<n+1;i++){
   int count=0;
   int temp=i;
   while(temp!=0){
   if((temp&1) ==1){
   count++;
   }
   temp=temp>>1;
   }
   t[i]=count;
   }
   return t;
   }
   }
   

2. 递推公式

   通过这个关系式 t[i] = i%2+t[i/2] 减少大量的重复计算。

   举例说明 5 二进制 101 5%2=1 t[5/2]=t[2]=1 总和=2；

   class Solution {
   public int[] countBits(int n) {
   int []
   t = new int[n+1];
   t[0]=0;
   for(int i=0;i<n+1;i++){
   t[i]=i%2+t[i/2];
   }
   return t;
   }
   }
   

3. 通过判断奇偶数/ 动态规划

   class Solution {
   public int[] countBits(int n) {
   int []
   t = new int[n+1];
   t[0]=0;
   for(int i=0;i<n+1;i++){
   if(i%2==0){
   t[i]=t[i/2];
   }else {
   t[i]=1+t[i/2];
   }
   }
   return t;
   }
   }
   

最后

以上就是自然硬币为你收集整理的剑指 Offer II 003. 前 n 个数字二进制中 1 的个数的全部内容，希望文章能够帮你解决剑指 Offer II 003. 前 n 个数字二进制中 1 的个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。