338 Counting Bits Bit位计数
2024-08-30 00:11:13
给定一个非负整数 num。 对于范围 0 ≤ i ≤ num 中的每个数字 i ,计算其二进制数中的1的数目并将它们作为数组返回。
示例:
比如给定 num = 5 ,应该返回 [0,1,1,2,1,2].
进阶:
给出时间复杂度为O(n * sizeof(integer)) 的解答非常容易。 但是你可以在线性时间O(n)内用一次遍历做到吗?
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗? 在c ++或任何其他语言中不使用任何内置函数(如c++里的 __builtin_popcount)来执行此操作。
详见:https://leetcode.com/problems/counting-bits/description/
C++:
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1,0);
for(int i=1;i<=num;++i)
{
res[i]=res[i&(i-1)]+1;
}
return res;
}
};
参考:https://www.cnblogs.com/grandyang/p/5294255.html
最新文章
- TYPESDK手游聚合SDK服务端设计思路与架构之四:流程优化之信息安全与订单校验
- html导入css样式的方法
- Excel中设置下拉列表的来源怎么选择其他工作表的内容
- 《算法设计手册》面试题解答 第五章:图的遍历 附:DFS应用之找挂接点
- silverlight 文本框只能输入数字
- NOIP2007 字符串展开
- DATEDIFF()(转)
- xcode5.1上真机调试报告No architectures to compile for...的解决办法
- AOP-----动态代理(转)
- c# zip file and folder programmatically
- 逆向wireshark学习SSL协议算法(转)
- 前端MVC Vue2学习总结(五)——表单输入绑定、组件
- HTTPS、证书与使用Charles抓包
- 对EF的封装
- 4327: JSOI2012 玄武密码
- Ubuntu安装最新版nodejs
- 初始Java
- reids的主从复制配置
- 2018/09/13《涂抹MySQL》【MySQL复制特性】学习笔记(六)
- React、Redux 和 Bootstrap