剑指offer003-前n个数字二进制中1的个数

题目

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 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*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
• 要求算法的空间复杂度为 O(n) 。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。

很明显的动态规划的题目，先分析规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

n	二进制		1的数量
0		0		0
1		1		1
-------------------
2		10		1
3		11		2
-------------------
4		100		1	-> n=0 (+1)
5		101		2	-> n=1 (+1)
6		110		2	-> n=2 (+1)
7		111		3	-> n=3 (+1)
-------------------
8		1000	1	-> n=0 (+1)
9		1001	2	-> n=1 (+1)
10		1010	2	-> n=2 (+1)
11		1011	3	-> n=3 (+1)
12		1100	2
13		1101	3
14		1110	3
15		1111	4
------------------
16		10000	1

动态规划一般是找A[i]和A[i-1]之间的关系，很容易找出规律，比如4-7，把二进制的最高位和后面两位拆分，发现实际上就是0-3的1的数量+1。

比如8-15，实际上就是0-7的1的个数+1

因此，当我们初始化数组，a[0] = 0, a[1] = 1时

我们发现a[n]实际上应该等于a[n-小于n的最小2的幂] + 1

即a[5] = a[5-4] + 1，a[15] = a[15-8] + 1

本质上说，当二进制的位数上升之后，最高位肯定是1，剩下的位数我们可以在动态数组中找到

即4位的二进制，最高位肯定时1，剩下的三位中1的个数可由三位二进制得到，形成递推关系式

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int[] countBits(int n) {
        if(n == 0){
            return new int[1];
        }
        int[] res = new int[n + 1];
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            res[i] = res[largest_power(i)] + 1;
        }
        return res;
    }

    int largest_power(int N) {
        int N1 = N;
        N = N | (N >> 1);
        N = N | (N >> 2);
        N = N | (N >> 4);
        N = N | (N >> 8);
        N = N | (N >> 16);
        int maxPower = (N + 1) >> 1;
        return N1 & ~maxPower;
    }
}

1
2
3

解答成功:
执行耗时:2 ms,击败了39.71% 的Java用户
内存消耗:42.3 MB,击败了75.21% 的Java用户

• ← Previous Post
• Next Post →