338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2]

代码语言：javascript复制

class Solution {
    public int[] countBits(int n) {
        /**
        动态规划 1basecase  2穷举 3状态转移

        奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
          举例： 
         2 = 10      3 = 11
        偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已
           举例：
          2 = 10       4 = 100       8 = 1000

         */

         int[] ans=new int[n 1];
         ans[0]=0;
         for(int i=1;i<=n;i  ){//状态转移
             if(i%2==1){
                 ans[i]=ans[i-1] 1;
             }else{
                 ans[i]=ans[i/2];
             }
         }
         return ans;
    }
}

二进制 数组

0 人点赞