Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1‘s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
Hint:
Credits:
Special thanks to @ syedee for adding this problem and creating all test cases.
解法一：
class Solution { public: vector<int> countBits(int num) { if (num == 0) return {0}; vector<int> res{0, 1}; int k = 2, i = 2; while (i <= num) { for (i = pow(2, k - 1); i < pow(2, k); ++i) { if (i > num) break; int t = (pow(2, k) - pow(2, k - 1)) / 2; if (i < pow(2, k - 1) + t) res.push_back(res[i - t]); else res.push_back(res[i - t] + 1); } ++k; } return res; } };
解法二：
class Solution { public: vector<int> countBits(int num) { vector<int> res; for (int i = 0; i <= num; ++i) { res.push_back(bitset<32>(i).count()); } return res; } };
解法三：
class Solution { public: vector<int> countBits(int num) { vector<int> res{0}; for (int i = 1; i <= num; ++i) { if (i % 2 == 0) res.push_back(res[i / 2]); else res.push_back(res[i / 2] + 1); } return res; } };
原文：http://www.cnblogs.com/grandyang/p/5294255.html