[LeetCode]338. Counting Bits

思路

对于每一位数，计算其中1的个数，计算过程优化，可以使时间较短

代码

class Solution { public: vector<int> countBits(int num) { vector<int> res; for (int i = 0; i < num + 1; ++i) { int count = 0, n = i; while (n){ ++count; n &= n - 1; } res.push_back(count); } return res; } };

思路 update

对于上述代码中的循环计算，对于5来说，只需要计算 5 & 4 的结果，之前的结果都保存在前一位数中

代码 update

class Solution { public: vector<int> countBits(int num) { vector<int> res(num + 1, 0); for (int i = 1; i < num + 1; ++i) { res[i] = res[i & (i - 1)] + 1; } return res; } };