别人家的面试题:总计“1”的个数

别人家的面试题:总计“1”的个数

解题思路

那道题咋一看还挺不难的,无非是:

  • 福寿年高一个形式 countBit,对任意非负整数
    n,总括它的二进制数中“1”的个数
  • 循环 i 从 0 到 num,求 countBit(i),将值放在数组中回到。

JavaScript中,计算 countBit 能够取巧:

function countBit(n){ return n.toString(2).replace(/0/g,””).length; }

1
2
3
function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}

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

下一场,我们写一下完好无损的顺序:

版本1

function countBit(n){ return n.toString(2).replace(/0/g,”).length; }
function countBits(nums){ var ret = []; for(var i = 0; i <= nums;
i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
function countBit(n){
   return n.toString(2).replace(/0/g,”).length;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

地点那种写法十二分收益,好处是 countBit 利用 JavaScript
语言特征实现得卓殊不难,坏处是若是前几日要将它改写成别的语言的版本,就有大概懵B了,它不是很通用,而且它的性质还在于
Number.prototype.toString(2) 和 String.prototype.replace 的实现。

于是为了追求更好的写法,我们有供给考虑一下 countBit 的通用完毕法。

大家说,求2个平头的二进制表示中 “1” 的个数,最日常的当然是3个 O(logN)
的主意:

function countBit(n){ var ret = 0; while(n > 0){ ret += n & 1; n
>>= 1; } return ret; }

1
2
3
4
5
6
7
8
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}

据此大家有了版本2

那般达成也很简短不是吗?不过那样达成是或不是最优?提议此处思考10分钟再往下看。


别的版本

上边的版本已经符合了大家的急需,时间复杂度是 O(1),不用循环和递归。

其余,我们还足以有任何的本子,它们严俊来说有的依然“犯规”,但是我们还是可以学学一下这个思路:

版本4:用 Math.sqrt

JavaScript

function isPowerOfFour(num) { num = Math.sqrt(num); return num > 0 &&
num === (0|num) && (num & (num-1)) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    num = Math.sqrt(num);
    return num > 0 && num === (0|num) && (num & (num-1)) === 0;
};

本子5:用正则表明式

JavaScript

function isPowerOfFour(num) { return /^1(00)*$/g.test(num.toString(2));
};

1
2
3
function isPowerOfFour(num) {
    return /^1(00)*$/g.test(num.toString(2));
};

以上正是具有的内容,那道题有十二分多样思路,十分幽默,也相比考验基本功。即使你有友好的思路,可以留言加入座谈。

下一期我们研讨其它一道题,那道题比那两道题要难有的,但也更幽默:给定一个正整数
n,将它拆成至少七个正整数之和,对拆出的正整数求乘积,再次来到能够获得的乘积最大的结果

想一想你的解法是何许?你能够尽也许减弱算法的时光复杂度吗?期待您的答案~~

打赏帮衬小编写出越多好小说,感激!

打赏我

11:           0000 1011

我们试着一步一步化解这一个标题(注意演讲中数列有序冬季的分别):

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”已经为大家提示了答案,答案就在上头的万分定律里,小编把尤其等式再写1回:

countBit(n & (n – 1)) === countBit(n) – 1

1
countBit(n & (n – 1)) === countBit(n) – 1

相当于说,假设大家知晓了 countBit(n & (n - 1)),那么大家也就领会了
countBit(n)

而大家知道 countBit(0) 的值是 0,于是,大家能够很简单的递推:

版本4

function countBits(nums){ var ret = [0]; for(var i = 1; i <= nums;
i++){ ret.push(ret[i & i – 1] + 1); } return ret; }

1
2
3
4
5
6
7
function countBits(nums){
   var ret = [0];
   for(var i = 1; i <= nums; i++){
       ret.push(ret[i & i – 1] + 1);
   }
   return ret;
}

原来就好像此不难,你想到了吧 ╮(╯▽╰)╭

以上正是装有的内容,简单的标题思考起来很风趣吗?程序员就应当追求八面见光的算法,不是啊?

那是 leetcode
算法面试题连串的第3期,下一期大家探讨除此以外一道题,那道题也很风趣:判断三个非负整数是还是不是是
4 的平头次方
,别告诉笔者你用循环,想想更抢眼的措施吗~

打赏扶助本人写出更加多好小说,多谢!

打赏小编

绝不内置函数

那几个题材的首要性思路和上一道题类似,先考虑“4”的幂的二进制表示:

  • 40 = 1B
  • 41 = 100B
  • 42 = 10000B
  • 43 = 1000000B
  • ……

也正是每一种数比上多个数的二进制后面多五个零嘛。最重点的是,“4”的幂的二进制数只有1 个“1”。假使仔细阅读过上一篇,你就会驾驭,判断二个二进制数唯有 一个“1”,只要求:

JavaScript

(num & num – 1) === 0

1
(num & num – 1) === 0

而是,二进制数唯有 三个“1”只是“4”的幂的须求非充足标准,因为“2”的奇数拾遍幂也只有 3个“1”。所以,大家还供给增大的判断:

JavaScript

(num & num – 1) === 0 && (num & 0xAAAAAAAA) === 0

1
(num & num – 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0? 因为这么些保证 num 的二进制的可怜 “1”
现身在“奇数位”上,也就保障了这一个数确实是“4”的幂,而不只只是“2”的幂。

最终,大家收获完全的本子:

版本3

JavaScript

function isPowerOfFour(num) { return num > 0 && (num & (num-1)) === 0
&& (num & 0xAAAAAAAA) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    return num > 0 && (num & (num-1)) === 0
                   && (num & 0xAAAAAAAA) === 0;
};

地点的代码必要添加 num > 0,是因为 0 要清除在外,不然 (0 & -1) === 0
也是 true


对于11这些数,大家权且用1个字节来代表

前奏

打赏支持作者写出越来越多好小说,感激!

任选一种支付办法

图片 1
图片 2

3 赞 8 收藏 5
评论

解题思路

借使马虎“附加条件”,那题还挺简单的对啊?简直是随手拈来:

版本1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num
=== 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
        num /= 4;
    }
    return num === 1;
}

本子1 接近很简短、很有力的样子,它的日子复杂度是
log4N。有同学说,还足以做一些一线的改观:

版本1.1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num >>>= 2; }
return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
      num >>>= 2;
    }
    return num === 1;
}

地点的代码用位移替代除法,在任何语言中更快,鉴于 JS
平日情状下尤其坑的位运算操作,不肯定速度能变快。

好了,最主要的是,不管是 版本1 依然 版本1.1
如同都不满意大家前边提到的“附加条件”,即不使用循环和递归,也许说,大家必要摸索
O(1) 的解法。

依据常规,大家先讨论10分钟,然后往下看 ——


简单觉察,除了11最左侧那些位和5的最高位,别的位对应一样。也等于说i用二进制表示时1并发的次数等于i/第22中学1产出的次数加1(倘诺i用二进制表示时最左侧一个人为1,不然不加1)。那样大家在计算i时能够应用前边已总括出的i/2:ret[i]
= ret[i/2] + (i % 2 == 0 ? 0 : 1);

扩展:
一 、假设在回来找到的多少个数的同时,还供给您回来那八个数的职责列?
贰 、如若把题目中的要你追寻的七个数改为“多个数”,或私下个数列?(请看下面第四节)
三 、二分查找时: left <= right,right = middle – 1;left <
right,right = middle;

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图