【力扣】剑指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判断整数的奇偶。

最后

以上就是踏实花卷为你收集整理的【力扣】剑指offer II 003.前 n 个数字二进制中 1 的个数的全部内容，希望文章能够帮你解决【力扣】剑指offer II 003.前 n 个数字二进制中 1 的个数所遇到的程序开发问题。

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