leetcode
leetcode 2901 ~ 2950
比特位计数

比特位计数

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 26 ms, 内存: 16.8 MB


/*
 * 思路:
 * 使用Java Stream API来实现相同的功能。
 * 利用IntStream.rangeClosed和map方法来创建和转换数组。
 */

import java.util.stream.IntStream;

public int[] countBits(int n) {
    return IntStream.rangeClosed(0, n)
            .map(i -> Integer.bitCount(i))
            .toArray();
}

解释

方法:

这个题解使用了动态规划的思想,依据已知的较小数字的比特位计数来确定更大数字的比特位计数。核心在于利用位运算的性质:对于任何整数i,i & (i - 1)的运算结果是将i的二进制表示中最低位的1变为0。因此,i中1的个数等于i & (i - 1)中1的个数加1。这样,通过从1遍历到n,我们可以逐个计算出每个数字的比特位1的数量。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到的动态规划关系`ans[i] = ans[i & (i - 1)] + 1`的推导依据是什么?为什么可以确保此计算方法的准确性?
这个动态规划关系基于一个重要的位运算性质:对于任何整数i,表达式`i & (i - 1)`的结果是将i的最低位的1变为0。如果我们知道一个数比如`i & (i - 1)`的1的个数,那么i的1的个数就是`i & (i - 1)`的1的个数加上那个被移除的最低位1。换句话说,每当我们在i的二进制表示中去掉最低位的1,我们就知道新数的比特位计数比原数少一个1。因此,通过已知的更小的数的计数,我们可以构建出更大的数的比特位计数,这确保了计算的准确性。
🦆
在题解的算法中,是否考虑了所有可能的输入情况,例如最小输入n=0时的输出是否正确?
是的,题解中的算法考虑了所有可能的输入情况,包括最小的输入情况n=0。在算法中,初始化的结果列表`ans`的长度为`n+1`,并且所有元素的初值设为0。当n=0时,列表长度为1,且唯一的元素ans[0]已经正确设置为0,这代表数字0的二进制中1的个数是0。因此,算法对于输入n=0也提供了正确的输出。
🦆
题解提到使用了位运算`i & (i - 1)`来去掉最低位的1,能否解释这个操作的具体工作原理以及它如何帮助减少计算量?
位运算`i & (i - 1)`的工作原理是:当我们计算`i & (i - 1)`时,从i的二进制表示中去除最低位的1。例如,如果i=14(二进制1110),则`i - 1`为13(二进制1101),而`i & (i - 1)`为12(二进制1100),即最低位的1被去除。这个操作有助于减少计算量,因为它允许我们利用已经计算过的结果(即`i & (i - 1)`的比特位计数)来计算当前i的比特位计数。这样,每个数的计数只需要常数时间O(1),从而使整个算法时间复杂度为O(n)。

相关问题