題目描述

思路1:

1. 寫一個返回2進制中1數量的函數countOne
2. 遍歷0到num,對每一個數使用countOne,并將結果保存到res中返回

var countBits = function (num) {let res = new Array(num + 1).fill(0);for (let i = 0; i <= num; i++) {res[i] = countOne(i.toString(2));}return res;
};const countOne = num => {let res = 0;for (let i = 0; i < num.length; i++) {if (num[i] == 1) {res++;}}return res;
}

思路2:

1. 上面求1的個數的速率可以提升,可以考慮采用位運算來求

var countBits = function (num) {let res = new Array(num + 1).fill(0);for (let i = 0; i <= num; i++) {res[i] = countOne(i);}return res;
};const countOne = num => {let res = 0;while (num > 0) {res++;num = num & (num - 1);}return res;
}

思路3:

找到后面數與前面數的聯系,利用緩存進一步加速

1. 對于十進制10來說,其對應的二進制為"1010",其1的位數dp[10]為十進制2中1的位數 + 1,其對應公式如下:

dp[10] = dp[2] + 1;

2. 10與2之間其實只差一個十進制8(“1000”)
3. 同理十進制13(“1101”)其1的個數可以由公式 dp[13] = dp[5] + 1 求出

十進制5的二進制對應"101"

4. 因此可以得到遞推關系式, dp[i] = dp[i - highBit] + 1;

其中 highBit是不超過i的2的最大整數次冪
算法如下:

var countBits = function (num) {let dp = new Array(num + 1).fill(0);let highBit = 0;for (let i = 1; i <= num; i++) {if ((i & (i - 1)) == 0) {highBit = i;}dp[i] = dp[i - highBit] + 1;}return dp;
};