正文

leetcode刷题13.比特位计数——java版(代码片段)

一条IT  一条IT  2022-12-13  189

关键词：

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐

这道题有两种位运算思路，都是利用数组前面已经算好的数来计算当前数的1的个数

——leetcode此题热评

前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

leetcode热度榜前100简单题中的数组部分马上刷完，接下来做链表相关

Question

338. 比特位计数

难度：简单

给定一个非负整数 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）来执行此操作。

Solution

题目要求只扫描一次，所以我们思考能否用已知求未知，也可以理解成把复杂问题分解成简单问题，也就是动态规划得思想

参考爬楼梯

对于一个二进制数来说，如果它的最低位为1(奇数）,则它与n/2（他前面得偶数）的 1得个数相差1。

如果它的最低位为 0(偶数)，则它与 n/2 的 1 个数相同，这样就可以用前面的推出后面的。

0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了。

Code

所有leetcode代码已同步至github

欢迎star

/**
 * @author yitiaoIT
 */
class Solution 
    public int[] countBits(int n) 
        int count1[] = new int[n+1];
        count1[0]=0;
        for (int i = 0; i <= n; i++) 
           if(i%2==0) 
               count1[i]=count1[i/2];
           
           else 
               count1[i]=count1[i-1]+1;
           
        
        return count1;

Result

复杂度分析

时间复杂度：O(N)

End

更多算法题欢迎关注专栏《leetcode》

java刷题--338比特位计数(代码片段)

java刷题--338比特位计数题目代码结果题目代码动态规划classSolutionpublicint[]countBits(intnum)int[]res=newint[num+1];res[0]=0;for(inti=1;i<=num;i++)res[i]=res[i&(i-1)]+1;//把最低位1去掉r 查看详情

java刷题--338比特位计数(代码片段)

leetcodejava刷题笔记—338.比特位计数

338.比特位计数给你一个整数n，对于0<=i<=n中的每个i，计算其二进制表示中1的个数，返回一个长度为n+1的数组ans作为答案。简单难度。这道题我们可以对每一个数循环进行191.位1的个数的元算即可。publicin... 查看详情

leetcode0338.比特位计数(代码片段)

...法求一个数二进制下有多少个1力扣题目链接：https://leetcode.cn/problems/counting-bits/给你一个整数n，对于 0<=i<=n中的每个i，计算其二进制表示中1的个数，返回一个长度为n+1的数组ans作为答案。查看详情

leetcode刷题11.多数元素——java版(代码片段)

...到0就重新换个数开始计数，总能找到最多的那个——leetcode此题热评前言哈喽，大家好，我是一条糊涂算法，难得糊涂昨天面试字节，切实感受到了刷算法带来的提升生命不息，刷题不止Question169 查看详情

leetcode刷题15.汉明距离——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐returnbin(x^y).count(‘1’)——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂Question461.汉明距离难度：简单两个整数之间的汉明距离指的... 查看详情

leetcode刷题35.加一——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐难道就我一个人看不懂题？——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂Question66.加一难度：简单给定一个由整数组成的非... 查看详情

⭐算法入门⭐《递推-一维》简单04——leetcode338.比特位计数(代码片段)

...0c;和我一起打卡！🌞《光天化日学C语言》🌞LeetCode太难？先看简单题！🧡《C语言入门100例》🧡数据结构难？不存在的！🌳《数据查看详情

leetcode刷题68.前n个数字二进制中1的个数——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐如果最后一位为0，则下一个数字的1个数会+1如果最后一位为1，下一个数字会导致最后一位变成0，进一位，相当于右移一位之后+1的数字中1的个数... 查看详情

leetcode刷题33.最小的k个数——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐先找到第k小的数，然后遍历一遍数组，把所有比k小的数加入结果集。然后用这个数填充结果集，使结果集大小等于k。——leetcode此题热评前言哈喽，大... 查看详情

leetcode刷题49.和为k的子数组——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐为什么这题不可以用双指针/滑动窗口：因为nums[i]可以小于0，也就是说右指针i向后移1位不能保证区间会增大，左指针j向后移1位也不能保证区间和会减小。... 查看详情

leetcode刷题58.移除元素——java版(代码片段)

【leetcode刷题】58.移除元素——Java版⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐一天不刷题，我就浑身难受——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂《糊涂算法》专... 查看详情

338.比特位计数简单dp(代码片段)

https://leetcode-cn.com/problems/counting-bits/很容易可以想到一个暴力的做法classSolutionpublic:vector<int>countBits(intn)vector<int>ans;for(inti=0;i<=n;i++)inttemp=i,cnt=0; 查看详情

leetcode刷题28.替换空格——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐returns.replace("","%20");——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂坚持真的好难，但胜利的喜悦更加诱人！Questi... 查看详情

leetcode刷题12.移动零——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐本题所使用的指针技巧，其实就是快速排序中序列按pivot元素分成两个分组并找到pivot元素位置的操作的基础——leetcode此题热评前言哈喽，大家好，我是一条... 查看详情

leetcode刷题65.判断子序列——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐面对简单题,我重拳出击,架起意大利炮——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂点击跳转到《糊涂算法》专栏学习java大厂面试... 查看详情

leetcode刷题29.合并二叉树——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐递归就完事了。。大一菜鸡艰难刷题中。。——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂简单题倒数第二道！Question617.合并二... 查看详情

leetcode刷题44.快乐数——java版(代码片段)

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐快乐就完事了——leetcode此题热评前言哈喽，大家好，我是一条。糊涂算法，难得糊涂《糊涂算法》专栏上线倒计时——7天Question202.快乐数难度：简单编... 查看详情