338. 比特位计数
2023-04-18 16:12:34 时间
一 题目:
给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1:
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:
输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
二 思路:
动态规划: 划分子问题
- 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
- 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已
另外这里判断奇偶可以用&运算,比如我们可以判断(i&1)是否等于1,等于1就是奇数,否则是偶数,至于为什么呢?因为&操作两个位均为1才为1,而数字1的前面N位均补充为0,跟它做与运算,前面肯定为0
三 代码:
class Solution {
public int[] countBits(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
// 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
// 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已
for (int i = 1; i <= n; i++) {
//如果是奇数
if ((i&1)==1){
dp[i]=dp[i-1]+1;
}else{
dp[i]=dp[i/2];
}
}
return dp;
}
}
相关文章
- 无影云电脑启动大规模商用 已服务众多行业客户
- 世界移动通信大会上海展即将举办,2020年全球芯片采购4498亿美元
- 阿里云:合作伙伴业务连续三年增长超100%,未来一年新增50亿生态资金
- 拼多多,「扎」进土地
- 带有过期时间的LRU实现
- 托管开源和云计算将如何推动业务增长
- 百度在上海成立云计算公司 注册资本达15亿元
- 区块链:虚实结合的“桥梁”
- 重学计算机组成原理-计算机总线详解
- 飞猪基于 Serverless 的云+端实践与思考
- 如何在后疫情时代选择合适的IT和云服务提供商
- 详解:虚拟化与容器化,你分清了吗?
- 元宇宙:区块链真正成熟的标志
- Devops 落地的核心和13条经验总结
- 虎口夺食:通信运营商做“云”有没有出路?
- 一篇漫画,看懂云计算!
- 6G对于所有产业来说,将开启一个新时代
- “懂行人”携手克而瑞:以科技赋能园区,推动产城智慧化
- Starlink将下载速度目标从1Gbps提高到10Gbps
- Oracle Fusion ERP云连续五年获评Gartner魔力象限报告领导者