LeetCode 338. 比特位计数

文章目录

• 前言
• 题目
• 题解
• NO1：Brian Kernighan 算法
• NO2：Brian Kernighan 算法（进阶）
• NO3：奇偶数判别（位运算）
• NO4、字符串替换（空间最优）
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：338. 比特位计数，难度：简单。

题目描述(摘自leetcode)：

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

示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
 
提示：
0 <= n <= 105
 
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

---

题解

NO1：Brian Kernighan 算法

思路：利用n & (n-1)来不断消解1，最终操作的次数即为一个数的比特数！

代码：时间复杂度O(nlogn)：遍历一遍需要n次，每个整数计算一个比特数最多不会超过logn次。空间复杂度O(1)：除了原本要返回的数组，其他仅为常数个。

class Solution {
    //Brian Kernighan 算法
    public int[] countBits(int n) {
        int[] nums = new int[n+1];
        for (int i = 1; i <= n; i++) {
            nums[i] = countOnes(i);
        }
        return nums;
    }

    /**
     * Brian Kernighan 算法的原理是：对于任意整数 xx，令 x=x & (x-1)x=x & (x−1)，
     * 该运算将 xx 的二进制表示的最后一个 11 变成 00。
     * 因此，对 xx 重复该操作，直到 xx 变成 00，则操作次数即为 xx 的「一比特数」。
     */
    public static int countOnes(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

---

NO2：Brian Kernighan 算法（进阶）

思路：这里依旧使用的是Brian Kernighan 算法，只不过这里的话计算比特数的时间复杂度为O(1)，每个之后的比特数都会基于之前已经计算好的指定比特数+1.

代码：时间复杂度O(n)，空间复杂度O(1)

public int[] countBits(int n) {
    int[] nums = new int[n+1];
    for (int i = 1; i <= n; i++) {
        //每次基于之前计算好的比特数结果+1
        nums[i] = nums[i & (i-1)] + 1;
    }
    return nums;
}

---

NO3：奇偶数判别（位运算）

思路：奇偶数规律如下

奇数：前面的偶数+1
举例：1=>1  3(11)=>2  5(111)=>3
     0=>0  2(10)=>1  4(110)=>2 

偶数：与当前数/2的个数一样多
     2(10)=>1  4(100)=>1  6(110)=>2 8(1000)=>1
     1=>1      2(10)=>1   3(11)=>2  4(100)=>1

代码：时间复杂度O(n)，空间复杂度O(1)

//奇偶数判断
public int[] countBits(int n) {
    int[] nums = new int[n+1];
    for (int i = 1; i <= n; i++) {
        //位运算来判断奇偶数，若是==0则是偶数
        if((i & 1) == 0){
            nums[i] = nums[i/2];
        }else{
            nums[i] = nums[i-1] + 1;
        }
    }
    return nums;
}

---

NO4、字符串替换（空间最优）

思路：将数字转为二进制形式的字符串，将字符串中的0替换为空字符串，最后统计出来1的个数。

代码：时间复杂度O(nlogn)，空间复杂度O(1)

//字符串填充替换
public int[] countBits(int n) {
    int[] nums = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        //将数字转为二进制形式的字符串，接着将0全部替换为空字符串，最终统计1的个数
        nums[i] = Integer.toString(i,2).replace("0","").length();
    }
    return nums;
}

---

参考文章

[1]. leetcode题解

[2]. 清晰的思路—奇偶数求解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.12