每日一题338
文章目录
338. 比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
输入: 2
输出: [0,1,1]
思路1 直接计算
- 利用 x & (x-1), 每次可以消除最后一个二进制1的值,直到为0的特性
- 时间复杂度是 o(k * num)
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num + 1);
for (int i = 0; i < res.size(); i++) {
res[i] = count(i);
}
return res;
}
int count(int x) {
int one = 0;
while (x > 0) {
x = x & (x-1);
one++;
}
return one;
}
};思路2 dp
- 利用 x & (x-1), 可以通过该公式是否为0, 判断x是不是2的整数次幂
- 通过之前的二进制1的个数得出当前二进制1的个数
class Solution {
public:
vector<int> countBits(int num) {
vector<int> bits(num + 1);
bits[0] = 0;
int high = 0;
for (int i = 1; i <= num; i++) {
if ((i & (i-1)) == 0) {
high = i;
}
bits[i] = bits[i-high] + 1;
}
return bits;
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论