[Leetcode] 第338题 比特位计数
2024-08-24 20:24:39
一、题目描述
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出:[0,1,1,2,1,2]
二、题目分析
1)发现规律:2的幂1的数目一定是1个,用last_2记录最近出现的2的幂
2)dp[i]=1+dp[i-last_2],比如dp[7]=1+dp[3]
三、代码实现
class Solution {
public:
vector<int> countBits(int num) {
vector<int>res(num + );
res[] = ;
if (num < )return res;
res[] = ;
int last_2 = ;
for (int i = ; i <= num; ++i) {
if (i%last_2 == && i / last_2 == ) {
res[i] = ;
last_2 = i;
}
else
res[i] = + res[i - last_2];
}
return res;
}
};
最新文章
- Scrapy框架实现爬虫
- 学习Maven之Properties Maven Plugin
- 强势回归,Linux blk用实力证明自己并不弱!
- 检测网页地址有效性java代码
- javascript——继承
- react-native迁移版本遇到的问题
- [Leetcode][001] Two Sum (Java)
- Oracle排序分析函数
- Python巡检Oracle表空间并邮件告警
- HTML <;area>;<;map>;标签及在实际开发中的应用
- AttributeError: module &#39;__main__&#39; has no attribute &#39;main&#39;解决方法
- 全局解释器锁 GIL
- icpc2018-焦作-E Resistors in Parallel-数论+大数
- CSS font-family字体大合集
- [解决]IP地址非法,请接入联通热点后重新获取
- C++ c++与C语言的区别(三目运算符,const修饰符)
- Mac 安装Jupyter notebook
- (转)如何修正DIV float之后导致的外部容器不能撑开的问题
- vs文件属性(生成操作)各选项功能
- P2341 [HAOI2006]受欢迎的牛 强连通