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

前端开发者丨JavaScript
https://www.rokub.com
别人家的面试题: 统计“ 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;
}
前端开发者丨JavaScript
» 本文来自:前端开发者 » 《js面试题_ 统计“ 1” 的个数_前端开发者》
» 本文链接地址:https://www.rokub.com/2182.html
» 您也可以订阅本站:https://www.rokub.com
赞(0)
64K

评论 抢沙发

评论前必须登录!