js面试题_ 统计“ 1” 的个数_前端开发者

前端开发者丨JavaScript

别人家的面试题： 统计“ 1” 的个数小胡子哥 @Barret李靖 给我推荐了一个写算法刷题的地方 leetcode.com， 没有 ACM 那么难， 但题目很有趣。

而且据说这些题目都来源于一些公司的面试题。

好吧， 解解别人公司的面试题其实很好玩， 既能整理思路锻炼能力， 又不用担心漏题╮(╯▽╰)╭。

长话短说， 让我们来看一道题： 统计“ 1” 的个数给定一个非负整数 num， 对于任意 i， 0≤ i≤ num， 计算 i 的值对应的二进制数中“ 1” 的个数， 将这些结果返回为一个数组。

例如： 当 num = 5 时， 返回值为[0, 1, 1, 2, 1, 2]。

/** * @param {number} num * @return {number[]} */

var countBits = function (num) { //在此处实现代码 }; 1 2 3 4 5 6 7 /** * @param {number} num * @return {number[]} */ var countBits = function ( num ) { //在此处实现代码 } ;解题思路这道题咋一看还挺简单的，无非是：实现一个方法 countBit ，对任意非负整数 n，计算它的二进制数中“1”的个数，对任意非负整数 n，计算它的二进制数中“1”的个数 循环 i 从 0 到 num，求 countBit(i) ，将值放在数组中返回。

JavaScript中， 计算countBit可以取巧：

functioncountBit(n) {

returnn.toString(2).replace(/0/g, “”).length;

}

123

functioncountBit(n) {

returnn.toString(2).replace(/ 0 /

g, “”).length;

}

上面的代码里， 我们直接对n用toString(2) 转成二进制表示的字符串， 然后去掉其中的0， 剩下的就是“ 1” 的个数。

然后， 我们写一下完整的程序： 版本1functioncountBit(n) {

returnn.toString(2).replace(/0/g, ”).length;

}

functioncountBits(nums) {

varret= [];

for (vari=0; i<=nums; i++) {

ret.push(countBit(i));

}

returnret;

}

1234567891011

functioncountBit(n) {

returnn.toString(2).replace(/ 0 /

g, ”).length;

}

functioncountBits(nums) {

varret= [];

for (vari=0; i<=nums; i++) {

ret.push(countBit(i));

}

returnret;

}

上面这种写法十分讨巧， 好处是countBit利用JavaScript语言特性实现得十分简洁， 坏处是如果将来要将它改写成其他语言的版本， 就有可能懵B了， 它不是很通用， 而且它的性能还取决于Number.prototype.toString(2) 和String.prototype.replace的实现。

所以为了追求更好的写法， 我们有必要考虑一下countBit的通用实现法。

我们说， 求一个整数的二进制表示中“ 1” 的个数， 最普通的当然是一个O(logN) 的方法：

functioncountBit(n) {

varret=0;

while (n>0) {

ret+=n&1;

n>>=1;

}

returnret;

}

12345678

functioncountBit(n) {

varret=0;

while (n>0) {

ret+=n&1;

n>>=1;

}

returnret;

}

所以我们有了版本2这么实现也很简洁不是吗？ 但是这么实现是否最优？ 建议此处思考10秒钟再往下看。

更快的countBit上一个版本的countBit的时间复杂度已经是O(logN) 了， 难道还可以更快吗？ 当然是可以的， 我们不需要去判断每一位是不是“ 1”， 也能知道n的二进制中有几个“ 1”。

有一个诀窍， 是基于以下一个定律： 对于任意n， n≥ 1， 有如下等式成立： countBit(n& (n-1)) ===countBit(n) -11countBit(n& (n-1)) ===countBit(n) -1这个很容易理解， 大家只要想一下， 对于任意n， n– 1的二进制数表示正好是n的二进制数的最末一个“ 1” 退位， 因此n&n– 1正好将n的最末一位“ 1” 消去， 例如： 6的二进制数是110， 5=6– 1的二进制数是101， 6&5的二进制数是110&101==100的二进制数是110， 的二进制数是101， 的二进制数是88的二进制数是1011000， 87=88– 1的二进制数是1010111， 88&87的二进制数是1011000&1010111==1010000于是， 我们有了一个更快的算法： 版本3functioncountBit(n) {

varret=0;

while (n>0) {

ret++;

n&=n-1;

}

returnret;

}

functioncountBits(nums) {

varret= [];

for (vari=0; i<=nums; i++) {

ret.push(countBit(i));

}

returnret;

}

12345678910111213141516

functioncountBit(n) {

varret=0;

while (n>0) {

ret++;

n&=n-1;

}

returnret;

}

functioncountBits(nums) {

varret= [];

for (vari=0; i<=nums; i++) {

ret.push(countBit(i));

}

returnret;

}

上面的countBit(88) 只循环3次， 而“ 版本2” 的countBit(88) 却需要循环7次。

优化到了这个程度， 是不是一切都结束了呢？ 从算法上来说似乎已经是极致了？ 真的吗？ 再给大家30秒时间思考一下， 然后再往下看。

countBits的时间复杂度考虑countBits， 上面的算法：“ 版本1” 的时间复杂度是O(N*M)， M取决于Number.prototype.toString和String.prototype.replace的复杂度。“ 版本2” 的时间复杂度是O(N*logN)“ 版本3” 的时间复杂度是O(N*M)， M是N的二进制数中的“ 1” 的个数， 介于1~logN之间。

上面三个版本的countBits的时间复杂度都大于O(N)。

那么有没有时间复杂度O(N) 的算法呢？ 实际上，“ 版本3” 已经为我们提示了答案， 答案就在上面的那个定律里， 我把那个等式再写一遍： countBit(n& (n-1)) ===countBit(n) -11countBit(n& (n-1)) ===countBit(n) -1也就是说， 如果我们知道了countBit(n& (n-1))， 那么我们也就知道了countBit(n)！ 而我们知道countBit(0) 的值是0， 于是， 我们可以很简单的递推： 版本4functioncountBits(nums) {

varret= [0];

for (vari=1; i<=nums; i++) {

ret.push(ret[i&i-1] +1);

}

returnret;

}

1234567

functioncountBits(nums) {

varret= [0];

for (vari=1; i<=nums; i++) {

ret.push(ret[i&i-1] +1);

}

returnret;

}