338. 比特位计数

描述

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

链接

338. 比特位计数 - 力扣（LeetCode） (leetcode-cn.com)

解法：位运算 判断 奇偶数， +  动态规划

对于所有的数字，只有两类：

奇数：二进制表示中，奇数一定比前面的那个偶数多一个 1，因为多的就是 最低位（二进制下）的1.

          举例： 

         0 = 0       1 = 1

         2 = 10      3 = 11

偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

           举例：

          2 = 10       4 = 100       8 = 1000

          3 = 11       6 = 110       12 = 1100

 1 class Solution {
 2     public int[] countBits(int n) {
 3         int[] res = new int[n+1];
 4         res[0] = 0;
 5         for(int i = 1; i<= n; i++) {
 6             if( (i & 1) == 1) {  // 奇数
 7                 res[i] = res[i-1] + 1;
 8             }
 9             else {   // 偶数
10                 res[i] = res[i/2];
11             }
12         }
13         return res;
14     }
15 }

参考

 清晰的思路 - 比特位计数 - 力扣（LeetCode） (leetcode-cn.com)