leetcode TOP100 比特位计数
2024-08-29 20:20:36
338. 比特位计数
题目描述:
`给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
思路描述:
TIPs:别用暴力,超时…
1.先观察数字,首先奇数的二进制位最后一位一定为1,例子如3,5,7,所对应的二进制分别为11,101,0111,
2.而偶数的二进制位最后一位一定不为1,例子就不举了。
3.那么我们就可以推出我们的公式了:
当n是奇数时,b[n]=b[n/2]+1
当n为偶数时,b[n]=b[n/2];**
剩下代码:
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1);
res[0]=0;
for(int i=1;i<=num;i++)
{
if(i&1)
res[i]=res[i/2]+1;
else
res[i]=res[i/2];
}
return res;
}
};
最新文章
- Types of CQRS
- HDU Math Problems
- Activiti 查看流程图
- php表单中如何获取单选按钮与复选按钮的值
- 手机号码js正则验证
- 频谱分析仪 RBW&;VBW
- Android 用Animation-list实现逐帧动画
- Unity5 新功能解析--GI(全局光)
- spring Scurity终于测试OK了,复杂的功能还待深入研究!发布出来一起探讨吧!
- JavaScript初学者应知的24条最佳实践(译)
- eclipse中project facet问题
- Python后台开发Django(启动)
- 从壹开始前后端分离【 .NET Core2.0 +Vue2.0 】框架之十 || AOP面向切面编程浅解析:简单日志记录 + 服务切面缓存
- Topologies on product spaces of $\mathbb{R}$ and their relationships
- spring中基于JDK和CGLIB代理在项目的应用
- Asp.net Core Mvc EF- Migrations使用
- 构建你自己的论坛,基于windows服务器的xampp+discuz论坛
- form表单中的id 与name的区别
- FPGA实战操作(1) -- SDRAM(Verilog实现)
- PAT 天梯赛练习集 L2-016. 愿天下有情人都是失散多年的兄妹