X

LEETCODE 338. Counting Bits 解题思路分析

题目大意:

比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

  • 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗?
  • 要求算法的空间复杂度为O(n)。
  • 你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=338

解题思路分析:

这是一道动态规划的题目。首先我们应该掌握一个知识点,即如何求出一个数字的二进制表现下1的个数。这需要先将十进制转为二进制,转化的方式是求当前十进制数字与2的余数,该余数即是二进制数的最低位,然后将该十进制数除以2,继续求它与2的余数,这一次求出的余数是二进制数的次低位,重复上述过程,直到十进制数变为0为止。我们统计出所有值为1的位数即可。

掌握了上述方法,本题实际上已经有了答案。我们从0循环至num,分别计算出当前数字的二进制表现下1的个数即可。不过这种解法效率相对较低,换一个思路去思考,其实我们只需要知道当前数字num二进制表现下最低位是否为1即可,接下来,根据上文讲到的方法,我们需要将当前数字除以2(num/2)之后再继续使用它与2进行求余操作。对于num/2,它一定小于num,另外由于我们是从0循环至当前数字num的,也就是说,num/2这个数字我们之前一定已经计算过它的结果,因此我们这里不必再去做重复计算,直接利用之前的计算结果即可。

res[num] = num%2 + res[num/2] ; // 最低位是否为1 加上 自身一半的数字中1的个数

以上即是动态规划的推导公式,而本题的返回结果正是动态规划使用到的dp数组。如果你想将代码写的更酷炫一些,num/2这里「除以2」操作可以使用「>>1」(右移一位)来替代,即:

res[num] = num%2 + res[num>>1] ; 

实现代码:

public int[] countBits(int num) {
    int[] res=new int[num+1]; // 返回结果兼DP数组
    // 从1开始循环每个数字。(数字0中1的个数是0)
    for(int i=1;i<=num;i++){
        // 最低位是否为1 加上 自身一半的数字中1的个数
        res[i]= i%2+res[i/2];
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.80% of Java online submissions for Counting Bits.

Memory Usage: 43.5 MB, less than 5.88% of Java online submissions for Counting Bits.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-338-counting-bits-解题思路分析/
Categories: leetcode
kwantong: