一：解题思路
方法一：之前做过一道求一个正整数二进制中1的个数的题目，利用这个题目为基础，然后遍历从1-n 这n+1 个数字。Time:O(n*k),Space:O(1)
方法二：利用动态规划的思想来做，递推公式为：d[i]=d[i&(i-1)]+1。Time:O(n),Space:O(1)
二：完整代码示例 (C++版和Java版)
方法一C++:
class Solution { private: int theNumberOfOne(int n) { int count = 0; while (n != 0) { count++; n &= (n-1); } return count; } public: vector<int> countBits(int num) { vector<int> d(num+1,0); for (int i = 0; i <= num; i++) { d[i] = theNumberOfOne(i); } return d; } };
方法一Java:
class Solution { private int theNumberOfOne(int num) { int count=0; if(num!=0) { count++; num&=(num-1); } return count; } public int[] countBits(int num) { int[] d=new int[num+1]; for(int i=0;i<=num;i++) { d[i]=theNumberOfOne(i); } return d; } }
方法二C++:
class Solution { public: vector<int> countBits(int num) { vector<int> d(num+1,0); for (int i = 1; i <= num; i++) { d[i] = d[i& (i - 1)] + 1; } return d; } };
方法二Java:
class Solution { public int[] countBits(int num) { int[] d=new int[num+1]; for(int i=1;i<=num;i++) { d[i]=d[i & (i-1)]+1; } return d; } }
p158 连续自然数二进制中 1 的个数(leetcode 338)
原文：https://www.cnblogs.com/repinkply/p/13404877.html