给你一个整数
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 <= 10e5
- 很容易就能实现时间复杂度为 O(n log n) 的解决方案,你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗?
- 你能不使用任何内置函数解决此问题吗?(如,C++ 中的 __builtin_popcount )
我们可以先看一些例子:
我们很容易想到,当n为偶数,就相当于在比这个数小两倍的数的基础上左移一位,也就是在低位多加1个0,例如n=3时为0011,而n=6时为0110,n=4时为0100,而n=2时为0010,也因此res[i] = res[i / 2]。
对于奇数,我们同样可以在最大的小于该数的那个偶数上(n-1)低位+1得到,例如n=7时为0111,最大的小于7的偶数也就是6是0110,7就相当于在0110的最低位上加了个1变成了0111,这也就说明对于奇数res[i] = res[i-1] + 1。
由此我们可以发现规律其实很简单,可以据此写出代码。
- class Solution {
- public int[] countBits(int n) {
- int [] res = new int [n+1];
- for(int i=1;i<=n;i++){
- if(i%2==0) res[i]=res[i/2];
- else res[i]=res[i/2]+1;
- }
- return res;
- }
- }