外人家的面试题：总括“1”的个数

2016/05/27 · JavaScript · 5 评论 · Javascript, 算法

本文小编： 伯乐在线 - 十年踪迹 。未经作者许可，制止转发！
款待插手伯乐在线 专栏撰稿人。

小胡子哥 @Barret李靖 给自家推荐了一个写算法刷题的地点 leetcode.com，没有 ACM 那么难，但难点很风趣。何况传说那些难题都源于一些厂商的面试题。好啊，解解旁人集团的面试题其实很有趣，不仅能整理思路锻练技艺，又不要操心漏题 ╮(╯▽╰)╭。

长途电话短说，让我们来看一道题：

别人家的面试题：一个整数是不是是“4”的N次幂

2016/05/30 · 基础工夫 · 2 评论 · 算法

本文我： 伯乐在线 - 十年踪迹 。未经小编许可，防止转发！
迎接参预伯乐在线 专栏撰稿人。

这是 leetcode.com 的第二篇。与上一篇无异于，大家钻探共同绝对简便易行的难题，因为上学总重申规行矩步。何况，就终于轻易的主题材料，追求算法的极端的话，在那之中也可能有大学问的。

统计“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) {     //在此处实现代码 };

“4”的整数十四回幂

给定三个三十一位有号子整数（32 bit signed integer），写贰个函数，检查那个大背头是或不是是“4”的N次幂，这里的N是非负整数。

例如：

• 给定 num = 16，返回 true，因为 16 = 4²
• 给定 num = 5，返回 flase

叠合条件： 你可以预知不用循环和递归吗？

解题思路

这道题咋一看还挺轻巧的，无非是：

• 贯彻一个主意 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 的通用实现法。

作者们说，求三个平头的二进制表示中 “1” 的个数，最普通的自然是三个 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分钟再往下看。

---

解题思路

万一忽略“附加条件”，那题还挺轻便的对啊？大致是随手拈来：

版本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 像样极粗略、很强盛的规范，它的时间复杂度是 log₄N。有同学说，还是能做一些细小的转移：

版本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分钟，然后往下看 ——

---

更快的 countBit

上三个本子的 countBit 的年华复杂度已是 O(logN) 了，难道还是能更加快吧？当然是足以的，我们无需去看清每一人是否“1”，也能精通n 的二进制中有多少个“1”。

有二个妙方，是基于以下二个定律：

• 对此自由 n， n ≥ 1，有如下等式创造：

countBit(n & (n - 1)) === countBit(n) - 1

1	countBit(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
• 88 的二进制数是 101一千，87 = 88 – 1 的二进制数是 1010111，88 & 87 的二进制数是 1011000 & 1010111 == 1010000

于是乎，我们有了三个更加快的算法：

版本3

function countBit(n){ var ret = 0; while(n > 0){ ret++; n &= n - 1; } return ret; } 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 12 13 14 15 16

function countBit(n){     var ret = 0;     while(n > 0){         ret++;         n &= n - 1;     }     return ret; }   function countBits(nums){    var ret = [];    for(var i = 0; i <= nums; i++){        ret.push(countBit(i));    }    return ret; }

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

优化到了这一个水平，是否整个都终止了吗？从算法上来讲就如早便是极致了？真的吗？再给大家30 秒时间考虑一下，然后再往下看。

---

不用循环和递归

实际上那道题真心有无数种思路，计算指数之类的对数学系学霸们一心不是主题素材嘛：

版本2

JavaScript

const log4 = Math.log(4); function isPowerOfFour(num){ var n = Math.log(num) / log4; return n === (0|n); }

1 2 3 4 5

const log4 = Math.log(4); function isPowerOfFour(num){     var n = Math.log(num) / log4;     return n === (0|n); }

啊，通过对数公式 log_m(n) = log(n) / log(m) 求出指数，然后推断指数是否贰个整数，这样就可以绝不循环和递归化解难点。并且，还要小心细节，能够将 log4 当作常量收取出来，那样并不是每一遍都再一次总结，果然是学霸范儿。

可是呢，利用 Math.log 方法也终于某种意义上的违犯禁令吧，有未有永不数学函数，用原生方法来减轻吧？

当然有了！况且还不仅仅一种，我们能够连续想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) - 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 算法面试题种类的首开始的一段时期，下期大家斟酌除此以外一道题，那道题也很有趣：推断三个非负整数是不是是 4 的平头次方，别告诉自身你用循环，想想更抢眼的格局呢~

打赏支持小编写出越来越多好小说，感激！

打赏作者

不要内置函数

以此难点的显要思路和上一道题类似，先思考“4”的幂的二进制表示：

• 4⁰ = 1B
• 4¹ = 100B
• 4² = 10000B
• 4³ = 1000000B
• ……

也正是各样数比上一个数的二进制后边多七个零嘛。最根本的是，“4”的幂的二进制数只有1 个“1”。即使条分缕析翻阅过上一篇，你就能知道，剖断一个二进制数唯有 1 个“1”，只须求：

JavaScript

(num & num - 1) === 0

1	(num & num - 1) === 0

唯独，二进制数独有 1 个“1”只是“4”的幂的须要非丰硕基准，因为“2”的奇多次幂也独有 1 个“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

---

打赏支持本人写出更加多好作品，多谢！

任选一种支付情势

3 赞 8 收藏 5 评论

别的版本

地方的版本已经适合了小编们的供给，时间复杂度是 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，将它拆成起码七个正整数之和，对拆出的正整数求乘积，再次来到可以赚取的乘积最大的结果。

想一想你的解法是什么？你可以尽可能降低算法的时光复杂度吗？期望您的答案~~

打赏辅助本身写出越多好小说，多谢！

打赏我

有关小编：十年踪迹

月影，奇舞蹈艺术团大校，热爱前端开拓，JavaScript 工程师一枚，能写代码也能打杂卖萌说段子。 个人主页 · 笔者的篇章 · 14 ·     

打赏支持作者写出越来越多好小说，多谢！

任选一种支付办法

1 赞 7 收藏 2 评论

至于小编：十年踪迹

月影，奇舞蹈艺术团少将，热爱前端开辟，JavaScript 技士一枚，能写代码也能打杂卖萌说段子。 个人主页 · 作者的稿子 · 14 ·     

本文由9992019银河国际发布于网络前端,转载请注明出处：禁绝转发

关键词：