本文主要是介绍LeetCode刷题之HOT100之比特位计数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天把仙剑三看完了,茂茂割肉让人无法释怀,眼泪止不住的流。长卿和紫萱的分离似乎也意味着重逢,这就是他们的宿命吧。怅然若失的感觉席卷全身,哎,做题吧。
1、题目描述
2、逻辑分析
题目要求将整数从0到此元素(都包括),计算每一个数二进制表示1的个数,返回数组。我想到了那个斐波拉契数,类似阶层,又有所不同,我去看看题解。官方题解给出了四种解法,其中分别是Brian Kernighan 算法与动态规划算法。下面先从第一种方法Brian Kernighan 算法开始。
Brian Kernighan 算法:从0到n,每个整数都分别计算它们的二进制中表示1的个数,再返回数组即可,而使用Brian Kernighan 算法的优点是可以在一定程度上进一步提升计算速度。Brian Kernighan算法的原理是:对于任意整数 x,令 x = x & (x−1),该运算将 x 的二进制表示的最后一个 1 变成 0。因此,对 x 重复该操作,直到 x 变成 0,则操作次数即为 x 的「二进制带有1的比特数」。
3、代码演示
public int[] countBits(int n) {// 创建一个大小为n+1的数组来存储结果int [] bits = new int[n +1];// 遍历从0到n的每个数字 for(int i = 0 ; i <= n; i++){// 计算当前数字i的二进制表示中1的个数,并将结果存储在数组中bits[i] = countOne(i);}return bits;}public int countOne(int x){int ones = 0;while(x >0){x &= (x - 1);ones++;}return ones;}
我叫GPT给我写注释,他说我的countOne函数写的不对,问题在于 x &= (x - 1); 这一行。这行代码确实会消除 x 的二进制表示中的最低位的1,但它并不适合用于计数。因为无论你执行多少次这个操作,只要 x 不为0,ones 就会一直增加,即使 x 的某些位原本就是0。应该这样写:
public int countOne(int x){ int ones = 0; while(x > 0){ if ((x & 1) == 1) { // 检查x的最低位是否为1 ones++; // 如果是,增加计数 } x >>= 1; // 右移一位,丢弃最低位的1 } return ones; // 返回正确的计数结果
}
时间复杂度:O(nlogn),空间复杂度:O(1)。
接下来一起看看动态规划的解法,我先去看看挑哪一个来写哈!官方的写的太深奥了,我发现了一个天才般的解法:
也就是说,可以根据奇数、偶数中二进制1的个数来解题。下面直接上代码,就像三行情诗一样美哈哈:
public int[] countBits(int n) { int [] countOne = new int[n + 1];for(int i = 1; i <= n; i++){// 当前数字i的二进制表示中1的个数等于其除以2的商(即i/2)的二进制表示中1的个数 // 加上i的最低位(即i % 2)的值(0或1)// 这是基于一个观察:一个数字的二进制表示中1的个数与其除以2的商的二进制表示中1的个数相关countOne[i] = countOne[i /2] + i % 2;}return countOne;}
时间复杂度:O(n),空间复杂度:O(1)。
ok啦,今天差不多就到这儿了,明天好好学习!BYE
这篇关于LeetCode刷题之HOT100之比特位计数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!