338 Counting Bits

2019-11-07 23:34:01

字体：大中小

来源：转载

供稿：网友

一、题目简述

给定非负整数num $num$ ，求在区间[0,num] $[0,num]$ 内所有整数的二进制串中1的位数，并把结果以数组形式表示。示例：如num=5 $num=5$ ，则应返回[0,1,1,2,1,2] $[0,1,1,2,1,2]$ 。要求：时间复杂度与控件复杂度均应为O(n) $O(n)$ 。

二、编程思路

由题目中所给出的要求可知，不能使用普通思路，即对[0...num] $[0...num]$ 中所有的数字单独求其二进制串中1的位数，而应寻找其前后之间的规律，即递归思路，降低算法复杂度。

十进制数	二进制数	1的位数
0	0	0
1	1	1
2	10	1
3	11	2
4	100	1
5	101	2
6	110	2
7	111	3
8	1000	1
9	1001	2
…	…	…

仔细观察上表可以发现，整数n $n$ 的二进制串中1的位数f(n) $f(n)$ 与将其二进制串最高位去掉后数字m $m$ 的f(m) $f(m)$ 之间存在如下递归关系： f(n)=1+f(m) $f(n)=1+f(m)$ 其中，m=(n<<1)&1...1（1的个数为n二进制串的长度） $m=(n<<1)/&1...1（1的个数为n二进制串的长度）$ 。

三、代码实现

class Solution {public: vector<int> countBits(int num) { vector<int> bits; int bits_width = 3;//当前数字二进制串的长度 for (int i = 0; i <= num; i++){ //递归基定义 if (i == 0){ bits.push_back(0); continue; } if (i == 1){ bits.push_back(1); continue; } //递归步的定义 int bit_n; bit_n = 1 + bits[(i << 1)&bits_width]; bits.push_back(bit_n); //对bits_width进行更新 if (i >= bits_width) bits_width = (bits_width << 1) | 1; } return bits; }};