【力扣】剑指offer II 003.前 n 个数字二进制中 1 的个数

题目：https://leetcode-cn.com/problems/w3tCBm/

方法一：动态规划-最高有效位

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        int highBits = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBits = i;
            }
            bits[i] = bits[i - highBits] + 1;
        }
        return bits;
    }
}

时间复杂度：O(n)；空间复杂度：O(1).

思路：用highBit表示不超过i的二进制的最高位，则当前的1比特数=去掉最高位的1之后的1比特数 + 1；

方法二：动态规划-最低有效位

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

时间复杂度：O(logn)；空间复杂度：O(1)；

思路：当前数的1比特数 = 除最后一位的1比特数 + 最后一位的1比特数。除最后1一位的1比特数考虑使用右移1位；最后一位的1比特数考察当前数是奇数还是偶数，使用(x & 1)判断。

【注意】：

1. java数组的默认值：整数数组默认值为0，布尔数组默认值为false，String数组或对象数组默认值为null；
2. x & (x - 1) 作用：将x的最后一个1改为0。如果x &(x - 1) == 0表示x为2的整数次方；
3. 右移相当于整除2，左移相当于乘2（对于溢出情况另做判断）。
4. x & 1判断整数的奇偶。