leetcod如何实现比特位计数

问题描述

比特位计数是一个非常经典的问题，要求给定一个非负整数num，对于范围[0, num]内的每个数字i，计算其二进制表示中1的个数，并将结果以数组的形式返回。

解决方案

解决该问题有多种方法，下面分别介绍两种经典的实现方式。

方法一：逐个统计

该方法通过逐个统计每个数字i的二进制表示中1的个数，然后将结果存入数组中。

public int[] countBits(int num) {
    int[] result = new int[num+1];
    for (int i = 0; i <= num; i++) {
        result[i] = countOnes(i);
    }
    return result;
}

private int countOnes(int num) {
    int count = 0;
    while (num != 0) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

该方法的时间复杂度为O(nk)，其中k为整数的二进制表示位数，空间复杂度为O(n)，因为需要存储每个数字的结果。

方法二：利用动态规划

该方法利用动态规划的思想，通过已经计算过的数字的结果来快速计算当前数字的结果。

public int[] countBits(int num) {
    int[] result = new int[num+1];
    for (int i = 1; i <= num; i++) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

该方法的时间复杂度为O(n)，空间复杂度为O(n)，因为只需要存储每个数字的结果。

总结

比特位计数是一个经典的问题，可以通过逐个统计和利用动态规划两种方式来解决。逐个统计的方法适用于任意整数，但时间复杂度较高；而利用动态规划的方法可以在O(n)的时间复杂度内解决，但需要一些额外的空间来存储结果。在实际应用中，可以根据具体需求选择合适的方法来解决该问题。