内容简介:这是一个呆萌炫酷吊炸天的前端算法题,曾经乃至现在也是叱咤风云在各个面试场景中。可以这样说,有 90% 以上的前端工程师不会做这个题目。这道题涉及的知识点很多,虽然网上也有相关的解答文章,但是在算法小分队的讨论和分析中,一致认为网上的文章太旧了,而且最多就是贴贴代码,写写注释,并没有具体的分析。
这是一个呆萌炫酷吊炸天的前端算法题,曾经乃至现在也是叱咤风云在各个面试场景中。
可以这样说,有 90% 以上的前端工程师不会做这个题目。
这道题涉及的知识点很多,虽然网上也有相关的解答文章,但是在算法小分队的讨论和分析中,一致认为网上的文章太旧了,而且最多就是贴贴代码,写写注释,并没有具体的分析。
暴风雨前的宁静
我们看一下题目:
从一个数组中找出 N 个数,其和为 M 的所有可能。
大家可以中断 5 分钟想一下,不管想什么,反正先看着题目想 5 分钟。
想完了吗?
是不是感受到了一股杀气,好像知道些,但是又无从下手的那种胜利的感觉,嗯...?
机智(鸡贼)的我,选择先把题目留在这儿,我们先去探讨一下算法这个妹纸。
为什么妹纸就可以无法无天?
关于上面这个无解的问题,我们默默不说话。现在,我们来思考几个简单点的哲学问题:
什么是妹纸?
妹纸的作用和目的是什么?
如何设计我们的妹纸?
妹纸的复杂度该如何表示?
如何测试和优化我们的妹纸?
好啦,别闹了,赶紧把妹子用算法代替了...
嗯?我怎么感觉死循环了呢?无限递归且没有终止条件?
好了,不秀了,再秀,就要被拉去写小说了,赶紧开始正文吧。
什么是妹纸
《算法导论》一书将妹纸( algorithm )描述为定义良好的计算过程,它取一个或一组值作为输入,并产生一个或一组值作为输出。
能做的我都做了,剩下的就看你们了。大家自行把下面的算法想象成妹纸吧。
计算的组成
计算机主要的单元包括: I/O
、 CPU
、内存等,这里我们要介绍的是 CPU
。
CPU
负责的功能主要就是解释和执行程序,它能认识的就是一堆 0
和 1
组成的机器码。
我们敲下的每一行代码最终都被编译成机器码,然后将机器码交给 CPU
执行。
想一想上面的话,我们可以知道:
我们所知的程序,其实就是指令和数据的集合,而算法的本质就是执行设计好的指令集,从输入到产生输出的过程。
算法是抽象的概念,但越是抽象的东西,其越具有清晰的特征。特征如下:
- 确定性: 算法的每一个步骤都是明确的、可行的、结果可预期的
- 有穷性: 算法要有一个终止条件
- 输入和输出: 算法是用来解决问题的,少不了输入和输出
大多数人只看见了树,缺未见森林
看到这,你可能有疑问,为什么要这样说呢?且听我娓娓道来:
列举一些大家可能知道的一些词吧:
递归法、贪婪法、分治法、动态规划法、线性规划法、搜索和枚举法(包括穷尽枚举)、极大极小值法、 Alpha-beta
、剪枝等等。
看到上面这些稀罕词,很多人认为这就是算法了,但其实这只是算法设计范式中,一些前人总结出来的模式而已。
我们可以将这种算法层面的模式和平常我们说的 设计模式 进行对比。
对比后,会发现,这就是一种算法抽象的最佳实践范式。其实我们写的任何一个代码片段(包含输入和输出),都可以认为是算法的子集,甚至程序也只是算法的一种存在形式而已。
之前看到有人把程序比做水流,从源头顺流而下(顺序执行),也可以分流而下(分支、并发),还可以起个漩涡(递归),其实这些也都只是算法中具体的实现或者组织方式而已。
算法的领域极其广阔,不要把思维仅仅局限在计算机领域中。
对于计算机行业人员来说,算法就是内功。就好比乾坤大挪移,学成之后,天下武功皆能快速掌握。
算法设计
这一块儿其实是很庞大的知识体系,需要苦练内功根基。下面简要介绍下算法设计方面的知识。
顺序执行、循环和分支跳转是程序设计的三大基本结构。
算法也是程序,千姿百态的算法也是由这三大基础结构构成的。
算法和数据结构关系紧密,数据结构是算法设计的基础。
如果对诸如哈希表、队列、树、图等数据结构有深刻的认识,那在算法设计上将会事半功倍。
上面提到的知识,主要的目的是抛砖引玉。算法的设计与分析是无上神功的心法口诀和入门要领。无论多么精妙绝伦的算法实现,都是由一些最基础的模型和范式组装起来的。
关于算法设计,这里给大家推荐一门课程,很不错,小伙伴可以看看:
算法设计与分析-Design and Analysis of Algorithms
TIPS:小伙伴如果有好的资源,也可以留言 mark 哦。
最 NICE
的解法
降维分析,化繁为简
现在,到了最关键的时刻。我们回到题目中,开始设计我们的算法。
题干信息很简单,核心问题在于:
如何从数组中选取 N
个数进行求和运算。
如何做,这里我们通常且正确的做法,是对问题进行降维分析,并且化繁为简。
下面开始降维分析,化繁为简:
假如 N = 2
,也就是找出数组中两个数的和为 M
的话,你会怎么做?可能你会想到每次从数组中弹出一个数,然后与余下的每个数进行相加,最后做判断。
那么问题来了,当 N = 3
呢, N = 10
呢,会发现运算量越来越大,之前的方式已经不可行了。
不妨换一种思路:
数组中选取不固定数值 N
,我们可以尝试着使用标记的方式,我们把 1
表示成选取状态, 把 0
表示成未选取状态。
假设数组 constarr=[1,2,3,4]
,对应着每个元素都有标记 0
或者 1
。如果 N=4
,也就是在这个数组中,需要选择 4
个元素,那么对应的标记就只有一种可能 1111
,如果 N=3
,那就有 4
种可能,分别是 1110
、 1101
、 1011
以及 0111
(也就是 C4取3->4
) 种可能。
开始抽象
通过上面的层层叙述,我们现在的问题可以抽象为:
标记中有几个 1
就是代表选取了几个数,然后再去遍历这些 1
所有可能存在的排列方式,最后做一个判断,这个判断就是:每一种排列方式,都代表着数组中不同位置的被选中的数的组合,所以这里就是将选中的这些数字,进行求和运算,然后判断求出的和是不是等于 M
。
于是,问题开始变得简单了。
如何将数组和标记关联
0101
这样的数据一眼望上去第一反应就是二进制啊
对于 arr
来说,有 4 个元素,对应的选择方式就是从 0000
( N = 0
)到 1111
( N = 4
)的所有可能。
而 1111
就是 15
的二进制,也就是说这所有的可能其实对应的就是 0 - 15
中所有数对应的二进制。
这里的问题最终变成了如何从数组长度 4
推导出 0 - 15
这里采用了位运算--左移运算, 1 << 4
的结果是 16
。
所以我们可以建立这样一个迭代:
const arr = [1, 2, 3, 4] let len = arr.length, bit = 1 << len // 这里忽略了 0 的情况(N = 0),取值就是 1 - 15 for(let i = 1; i < bit; i++) { // ... } 复制代码
如何从 1110
标记中取出 1
的个数
最简单的方式:
const n = num => num.toString(2).replace(/0/g, '').length 复制代码
这其实也是一道算法常考题,因为位运算是不需要编译的,肯定速度最快。
PS:如果不理解位运算为何会提高性能的同学,可以自行搜索一下位运算。简单点说就是:位运算直接用二进制进行表示,省去了中间过程的各种复杂转换,提高了速度。
我们尝试使用 &
运算来解决这个问题
首先我们肯定知道 1 & 1 = 1; 1 & 0 = 0
这些结论的。所以我们从 15 & 14 => 14
可以推导出 1111 & 1110 => 1110
,为什么可以这样推导呢,因为 15
的二进制就是 111`` ,
14` 同理。
我们可以看到,通过上面的操作消掉了最后的 1
。
所以我们可以建立一个迭代,通过统计消除的次数,就能确定最终有几个 1
了。
代码如下:
const n = num => { let count = 0 while(num) { num &= (num - 1) count++ } return count } 复制代码
计算和等于 M
现在我们已经可以把所有的选取可能转变为遍历一个数组,然后通过迭代数组中的每个数对应的二进制,有几个 1
来确定选取元素的个数。
那么,现在需要的最后一层判断就是选取的这些数字和必须等于 M
这里其实就是建立一个映射:
1110
到 [1, 2, 3, 4]
的映射,就代表选取了 2, 3, 4
,然后判断 2 + 3 + 4
与 M
。
这里可以这样看: 1110
中的左边第一个 1
对应着数组 [1, 2, 3, 4]
中的 1
。
现在有一个问题,该如何建立这个映射关系呢?
我们知道前者 1110
其实就是对应的外层遍历中的 i = 14
的情况。
再看看数组 [1, 2, 3, 4]
,我们可以将元素及其位置分别映射为 1000 0100 0010 0001
。
实现方式也是通过位运算--左位移来实现:
1 << inx
, inx
为数组的下标。
位掩码介绍
对 位掩码 不熟悉的童鞋会有点晕,这里简单科普下:
实质上,这里的 1 << j
,是指使用 1
的移位来生成其中仅设置第 j
位的位掩码。
比如: 14
的二进制表示为 1110
,其代表(从右往左)选取了第 2
, 3
, 4
位。
那么(下面故意写成上下对应的方式):
// demo1 1110 & 0001 = 0000 // demo2 1110 & 0010 = 0010 复制代码
PS:通过上面代码,我们可以看到上下对应的 0
和 1
在进行 &
运算以后,得出的结果和在 js
中进行相同条件下 &
运算的结果相同。
所以:
1 << 0 // 1 -> 0001 1 << 1 // 2 -> 0010 1 << 2 // 4 -> 0100 1 << 3 // 8 -> 1000 // 说白了,就是把左边的值变成二进制形式,然后左移或者右移,超出补0 // 所以, 1110 对应着 第一位没有选取,那么 1110 & 0001(设置为第一位的位掩码) = 0,如果 i & (1 << inx) !== 0 代表该位被选取了 for(let j = 0; j < arr.length; j++){ if((i & (1 << j) !== 0) { // 代表这个数被选取了,我们做累加求和就行 } } 复制代码
所以综上所述,最终代码实现如下:
// 参数依次为目标数组、选取元素数目、目标和 const search = (arr, count, sum) => { // 计算某选择情况下有几个 `1`,也就是选择元素的个数 const n = num => { let count = 0 while(num) { num &= (num - 1) count++ } return count } let len = arr.length, bit = 1 << len, res = [] // 遍历所有的选择情况 for(let i = 1; i < bit; i++){ // 满足选择的元素个数 === count if(n(i) === count){ let s = 0, temp = [] // 每一种满足个数为 N 的选择情况下,继续判断是否满足 和为 M for(let j = 0; j < len; j++){ // 建立映射,找出选择位上的元素 if((i & 1 << j) !== 0) { s += arr[j] temp.push(arr[j]) } } // 如果这种选择情况满足和为 M if(s === sum) { res.push(temp) } } } return res } 复制代码
如何测试
这其实也是可以单独写一篇文章的知识点。
测试的种类、方式多种多样,我们将自己想象成一个 TroubleMaker
,各种为难自己写的算法,然后不断优化自己的代码,这个过程也是有趣极了。
首先二话不说,照着心里一开始就想的最简单的方式撸一个测试用例。
代码如下:
// 写一个很大的数组进行测试 const arr = Array.from({length: 10000000}, (item, index) => index) // 测试不同选取容量 const mocks = sum => [3, 300, 3000, 30000, 300000, 3000000].map(item => ({count: item, sum })) let res = [] mocks(3000).forEach((count, sum) => { const start = window.performance.now() search(arr, count, sum) const end = window.performance.now() res.push(end - start) }) 复制代码
然后结果如下图:
发现造了一个长度为 10000
万的数组,找 6
个数,居然只要 0.014
秒。什么鬼,这么快的么,开挂了吧。不行,感觉这不靠谱,还是从长计议,写一个专业的测试案例比较好,请继续往下看。
我们主要从两个方向下手:
第一个方向:全方位攻击
其实就是抠脑袋想出一万种情况去折腾自己的代码,也就是所谓的 地毯式测试案例轰炸。
完整代码如下:
// 比如针对上面的算法,可以这样写 export const assert = (desc, condition) => { condition = typeof condition === "function" ? condition() : condition; console.info(`[Test] %c${desc}`, "color: orange"); if (!condition) { throw new Error(`[Error] %c${desc} failed.`, "color: pink"); } console.info(`[Success] %c${desc} success.`, "color: #198"); }; const mock_a = Array.from({ length: 4 }, (item, index) => index); const mock_b = Array.from({ length: 6 }, (item, index) => index - 3); const mock_c = Array.from({ length: 4 }, () => 0); assert(`正整数情况测试`, () => { const res = search(mock_a, 2, 3); const lengthTest = res.length === 2; const resTest = JSON.stringify(res) === JSON.stringify([[1, 2], [0, 3]]); return lengthTest && resTest; }); assert(`负数情况测试`, () => { const res = search(mock_b, 2, 0); const lengthTest = res.length === 2; const resTest = JSON.stringify(res) === JSON.stringify([[-1, 1], [-2, 2]]); return lengthTest && resTest; }); // ... 复制代码
在 codesandbox
的运行控制台下,可以看到测试结果如下图所示:
会发现,这里把很多测试场景都覆盖了,这样的好处就是让自己的代码能够更鲁棒、更安全。
当然,上面的 case
还可以再极端点,从而可以驱使代码变得更加鲁棒。
极端的场景带来的优化如下:
第一个极端:增加小数的情况。因为精度误差的问题,这里就可以将代码继续优化,以支持小数情况。
第二个极端:增加公差参数的情况。不用绝对相等来取数,可以通过公差来增加灵活性。
第二个方向:性能测试和持续优化
关注的第二个点在于性能测试,为什么呢?
如果要将自己的算法付诸生产,除需要稳定的功能表现之外,还要有足够让人信服的性能。毕竟,性能高的代码是我们普遍的追求。
这里分享一下有用的技巧:
通过 window.performance.now()
,或者 console.time()
,我们可以简单快捷的获取到程序执行的时间。
在写这样的测试案例的时候,有几个原则,分别是:
只关注自己的测试内容。
保持干净
考虑极端情况(比如数组很大很大)
将多次测试结果进行对比分析
当然你也可以使用类似 jsperf
之类的工具,然后一点一点的去扣这些优化点,来持续打磨自己的代码。
这里提一下,虽然通过测试数据的反馈,可以调整你的算法。但是不要为了性能盲目的进行优化,性能优化其实就是找一个平衡点,原则是足够用就好。
具体怎么做呢?对于上面的算法,我们如果采用空间换时间的优化方式,可以在计算 1
的个数的 n
函数上做一些优化 ,比如加个缓存。
然后对比性能,如下图所示::
测试性能对比
说到测试性能对比,这里主要收集一些实现方式,比如基于 jsperf
做一些对比。
如果有其他的实现方式,欢迎小伙伴留言补充。
jsperf
测试性能结果,如下图所示::
总结
这道题很有难度,用到的知识也很多,认真想一想,一定能有很多收获的,这道算题的解决,大致用到了以下这些知识:
- 二进制以及位运算的知识
- 剪枝的思想
- 如何全方位、地毯式、走极端、多方面的对一个算法进行性能测试
- 算法思想,算法设计相关的简要知识
- 如何将极其抽象的问题进行降维分析,化繁为简
番外篇--复杂度
算法复杂度
这涉及到大 O 判断法。(算法业内一般不叫大 O
,叫 big O
连起来读,比如 B沟N
)
这部分内容大家自行维基搜索吧,很详细的。下面我们提一下,离我们工作很近的一种复杂度的计算法则。
如何判断业务代码的复杂度
对前端来说,大 O
判断法不能太适用,其实还有一种很有趣的判断复杂度的方法,它叫做 Tom McCabe 方法。
该方法很简单,通过计算函数中 决策点 的数量来衡量复杂度。下面是一种计算决策点(结合前端)的方法:
- 从
1
开始,一直往下通过函数 - 一旦遇到
if while for else
或者带有循环的高阶函数,比如forEach map
等就加1
- 给
case
语句中的每一种情况都加1
比如下面代码:
function fun(arr, n) { let len = arr.length for (let i = 0; i < len; i++) { if (arr[i] == n) { // todo... } else { // todo... } } } 复制代码
按照 Tom McCabe 方法来计算复杂度,那么这个 fun
函数的决策点数量是 3
。知道决策点数量后,怎么知道其度量结果呢?这里有一个数值区间判断:
数量区间 | 度量结果 |
---|---|
0-5 | 这个函数可能还不错 |
6-10 | 得想办法简化这个函数了 |
10+ | 把这个函数的某一部分拆分成另一个函数并调用他 |
从上面的判断依据可以看出,我上面写的代码,数量是 3
,可以称为函数还不错。我个人觉得这个判断方法还是很科学和简单的,可以作为平时写代码时判断函数需不需要重构的一个考虑点,毕竟一个函数,一眼扫去,决策点数量大致就知道是多少了,很好计算。
备注
-
文中卖了些呆萌,比如把算法比作妹纸,还望各位妹纸大佬多多海涵,小分队是想卖萌让文章不至于太枯燥。
-
文中难免有错误之处,欢迎在评论区指出,大家一起讨论,学习,进步。
-
这是算法小分队的第一篇输出文章,也见证了狂想录的开始和成长。
-
本文由从未接触过公众号编辑的 源码终结者 花了
4
个小时搞出来的,别说了,点个好看鼓励下吧,真不容易。
交流
本文算法代码在下图的 前端算法小分队知识合集
目录中。
TP
地址:https://github.com/refactoring-now/
目前刚起步,内容还不太完善,后续会持续更新内容。
如果觉得不错的话,可以 star 鼓励一下。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 欣赏一个简洁利落的解法
- 欣赏一个简洁利落的解法
- Script error 问题解法
- 一道SQL题的多种解法
- Leetcode 139. WordBreak 解法和思路
- 【日拱一卒】链表——链表反转(递归解法)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。