LeetCode Java刷题笔记—338. 比特位计数

338. 比特位计数

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

简单难度。这道题我们可以对每一个数循环进行191. 位1的个数的元算即可。

public int[] countBits( int n ){int[] res = new int[ n + 1 ];for( int i = 0; i <= n; i++ ){res[ i ] = count( i );}return res;
}/*** 对每一位的二进制1数进行统计*/
private int count( int i ){int sum = 0;while( i != 0 ){sum++;sum &= ( sum - 1 );}return sum;
}

但是这样做会超出时间限制，我们需要在线性时间复杂度 O(n) 内用一趟扫描解决此问题。

我们知道i >> 1运算是将i的二进制数向右右移一位，因此会把最低位去掉，高位补0，结果会比i更小。当 i 的最低位是0，那么i和i >> 1中1的个数相同；当i的最低位是1，那么i的个数是 i >> 1的1的个数加1。我们可以知道，0的1二进制表示中 1 的个数为0，1的二进制表示中 1 的个数为1。

利用此规律，我们可以利用数组前面已经算好的数来计算当前数的1的个数，这里用到了动态规划。

/*** 利用数组前面已经算好的数来计算当前数的1的个数*/
public int[] countBits( int n ){int[] res = new int[ n + 1 ];for( int i = 0; i <= n; i++ ){//当前数的结果是它的i >> 1的结果，可能需要加1，通过i & 1获取低位的值相加即可res[ i ] = res[ i >> 1 ] + ( i & 1 );}return res;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！