mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
26 lines
876 B
Markdown
26 lines
876 B
Markdown
# [338. Counting Bits](https://leetcode.com/problems/counting-bits/)
|
||
|
||
# 思路
|
||
这道题给我们一个整数n，然我们统计从0到n每个数的二进制中的1的个数，存入一个一维数组中返回。
|
||
|
||
设结果数组为`res`，那么问题的关键就在于`res[i]`怎样从`res[0,...,i-1]`快速计算得出。有很多思路，例如
|
||
* `res[i] = res[i / 2] + (i & 1)`: i 为偶数时`res[i] = res[i / 2]`否则`res[i] = res[i / 2] + 1`；
|
||
* `res[i] = res[i & (i-1)] + 1`: 因为`i & (i-1)`表示去掉二进制中末尾1后的值。
|
||
|
||
这样只用一遍遍历即可得出结果。
|
||
|
||
# C++
|
||
``` 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 >> 1] + (i & 1);
|
||
// res[i] = res[i & (i-1)] + 1;
|
||
|
||
return res;
|
||
}
|
||
};
|
||
```
|