题目

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 105
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
来源：力扣（LeetCode）

解题思路

  最最直白的方式就是用代码翻译题目，可以将每个数字转化为二进制然后再计算其中1的个数。

class Solution:def countBits(self, n: int) -> List[int]:ans=[]for i in range(n+1):ans.append(str(bin(i)).count('1'))return ans

  不过像这种看起来十分简单的题，并且是递增1的有序，一般就可能存在潜在的规律。我们不妨多写上几个样例来分析一下：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
6 --> 110
7 --> 111
8 --> 1000
9 --> 1001
10–> 1010
11–> 1011
12–> 1100
…
  不难发现每个偶数的后面都是0，每个奇数的后面都是1，如果相邻的偶数和奇数，偶数如果小于奇数，那么奇数的二进制一定是将偶数最后一位的0改成了1；另外单独观察偶数发现2，4，8是一类，6，12是一类，10是一类，前面两类它都有共同的前缀“1”和“11” 并且2，4，8是以2为等比的数列，6，12也是，不出意外20的前缀也应该是“101”；第一类的前缀只有一个1，那么1的二进制就是它们的前缀，而第二类则 3的二进制是它们的前缀，再一看5也是第三类的前缀且，那么我们大胆猜设以2为等比数列以奇数开头的数的二进制中1的个数同它前面的那一个数字一样，而偶数则是奇数的二进制1的个数加1。

class Solution:def countBits(self, n: int) -> List[int]:ans=[0]flag=1for i in range(1,n+1):if flag:flag=0ans.append(ans[i-1]+1)else:flag=1ans.append(ans[i//2])return ans