从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

栏目: 编程工具 · 发布时间: 5年前

内容简介:这是一个呆萌炫酷吊炸天的前端算法题,曾经乃至现在也是叱咤风云在各个面试场景中。可以这样说,有 90% 以上的前端工程师不会做这个题目。这道题涉及的知识点很多,虽然网上也有相关的解答文章,但是在算法小分队的讨论和分析中,一致认为网上的文章太旧了,而且最多就是贴贴代码,写写注释,并没有具体的分析。

这是一个呆萌炫酷吊炸天的前端算法题,曾经乃至现在也是叱咤风云在各个面试场景中。

可以这样说,有 90% 以上的前端工程师不会做这个题目。

这道题涉及的知识点很多,虽然网上也有相关的解答文章,但是在算法小分队的讨论和分析中,一致认为网上的文章太旧了,而且最多就是贴贴代码,写写注释,并没有具体的分析。

暴风雨前的宁静

我们看一下题目:

从一个数组中找出 N 个数,其和为 M 的所有可能。

大家可以中断 5 分钟想一下,不管想什么,反正先看着题目想 5 分钟。

想完了吗?

是不是感受到了一股杀气,好像知道些,但是又无从下手的那种胜利的感觉,嗯...?

机智(鸡贼)的我,选择先把题目留在这儿,我们先去探讨一下算法这个妹纸。

为什么妹纸就可以无法无天?

关于上面这个无解的问题,我们默默不说话。现在,我们来思考几个简单点的哲学问题:

什么是妹纸?

妹纸的作用和目的是什么?

如何设计我们的妹纸?

妹纸的复杂度该如何表示?

如何测试和优化我们的妹纸?

好啦,别闹了,赶紧把妹子用算法代替了...

嗯?我怎么感觉死循环了呢?无限递归且没有终止条件?

从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

好了,不秀了,再秀,就要被拉去写小说了,赶紧开始正文吧。

什么是妹纸

《算法导论》一书将妹纸( algorithm )描述为定义良好的计算过程,它取一个或一组值作为输入,并产生一个或一组值作为输出。

从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

能做的我都做了,剩下的就看你们了。大家自行把下面的算法想象成妹纸吧。

计算的组成

计算机主要的单元包括: I/OCPU 、内存等,这里我们要介绍的是 CPU

CPU 负责的功能主要就是解释和执行程序,它能认识的就是一堆 01 组成的机器码。

我们敲下的每一行代码最终都被编译成机器码,然后将机器码交给 CPU 执行。

想一想上面的话,我们可以知道:

我们所知的程序,其实就是指令和数据的集合,而算法的本质就是执行设计好的指令集,从输入到产生输出的过程。

算法是抽象的概念,但越是抽象的东西,其越具有清晰的特征。特征如下:

  1. 确定性: 算法的每一个步骤都是明确的、可行的、结果可预期的
  2. 有穷性: 算法要有一个终止条件
  3. 输入和输出: 算法是用来解决问题的,少不了输入和输出

大多数人只看见了树,缺未见森林

看到这,你可能有疑问,为什么要这样说呢?且听我娓娓道来:

列举一些大家可能知道的一些词吧:

递归法、贪婪法、分治法、动态规划法、线性规划法、搜索和枚举法(包括穷尽枚举)、极大极小值法、 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 种可能,分别是 111011011011 以及 0111 (也就是 C4取3->4 ) 种可能。

开始抽象

通过上面的层层叙述,我们现在的问题可以抽象为:

标记中有几个 1 就是代表选取了几个数,然后再去遍历这些 1 所有可能存在的排列方式,最后做一个判断,这个判断就是:每一种排列方式,都代表着数组中不同位置的被选中的数的组合,所以这里就是将选中的这些数字,进行求和运算,然后判断求出的和是不是等于 M

于是,问题开始变得简单了。

如何将数组和标记关联

0101 这样的数据一眼望上去第一反应就是二进制啊

对于 arr 来说,有 4 个元素,对应的选择方式就是从 0000N = 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 + 4M

这里可以这样看: 1110 中的左边第一个 1 对应着数组 [1, 2, 3, 4] 中的 1

现在有一个问题,该如何建立这个映射关系呢?

我们知道前者 1110 其实就是对应的外层遍历中的 i = 14 的情况。

再看看数组 [1, 2, 3, 4] ,我们可以将元素及其位置分别映射为 1000 0100 0010 0001

实现方式也是通过位运算--左位移来实现:

1 << inxinx 为数组的下标。

位掩码介绍

位掩码 不熟悉的童鞋会有点晕,这里简单科普下:

实质上,这里的 1 << j ,是指使用 1 的移位来生成其中仅设置第 j 位的位掩码。

比如: 14 的二进制表示为 1110 ,其代表(从右往左)选取了第 2 , 3 , 4 位。

那么(下面故意写成上下对应的方式):

// demo1
  1110
&
  0001
=
  0000 
  
// demo2
  1110
&
  0010
=
  0010 
复制代码

PS:通过上面代码,我们可以看到上下对应的 01 在进行 & 运算以后,得出的结果和在 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)
})

复制代码

然后结果如下图:

从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

发现造了一个长度为 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 完整代码地址

codesandbox 的运行控制台下,可以看到测试结果如下图所示:

从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

会发现,这里把很多测试场景都覆盖了,这样的好处就是让自己的代码能够更鲁棒、更安全。

当然,上面的 case 还可以再极端点,从而可以驱使代码变得更加鲁棒。

极端的场景带来的优化如下:

第一个极端:增加小数的情况。因为精度误差的问题,这里就可以将代码继续优化,以支持小数情况。

第二个极端:增加公差参数的情况。不用绝对相等来取数,可以通过公差来增加灵活性。

第二个方向:性能测试和持续优化

关注的第二个点在于性能测试,为什么呢?

如果要将自己的算法付诸生产,除需要稳定的功能表现之外,还要有足够让人信服的性能。毕竟,性能高的代码是我们普遍的追求。

这里分享一下有用的技巧:

通过 window.performance.now() ,或者 console.time() ,我们可以简单快捷的获取到程序执行的时间。

在写这样的测试案例的时候,有几个原则,分别是:

只关注自己的测试内容。

保持干净

考虑极端情况(比如数组很大很大)

将多次测试结果进行对比分析

当然你也可以使用类似 jsperf 之类的工具,然后一点一点的去扣这些优化点,来持续打磨自己的代码。

这里提一下,虽然通过测试数据的反馈,可以调整你的算法。但是不要为了性能盲目的进行优化,性能优化其实就是找一个平衡点,原则是足够用就好。

具体怎么做呢?对于上面的算法,我们如果采用空间换时间的优化方式,可以在计算 1 的个数的 n 函数上做一些优化 ,比如加个缓存。

然后对比性能,如下图所示::

从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

完整的测试案例地址

测试性能对比

说到测试性能对比,这里主要收集一些实现方式,比如基于 jsperf 做一些对比。

如果有其他的实现方式,欢迎小伙伴留言补充。

jsperf 测试性能结果,如下图所示::

从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法

完整的测试案例地址

总结

这道题很有难度,用到的知识也很多,认真想一想,一定能有很多收获的,这道算题的解决,大致用到了以下这些知识:

  1. 二进制以及位运算的知识
  2. 剪枝的思想
  3. 如何全方位、地毯式、走极端、多方面的对一个算法进行性能测试
  4. 算法思想,算法设计相关的简要知识
  5. 如何将极其抽象的问题进行降维分析,化繁为简

番外篇--复杂度

算法复杂度

这涉及到大 O 判断法。(算法业内一般不叫大 O ,叫 big O 连起来读,比如 B沟N )

这部分内容大家自行维基搜索吧,很详细的。下面我们提一下,离我们工作很近的一种复杂度的计算法则。

如何判断业务代码的复杂度

对前端来说,大 O 判断法不能太适用,其实还有一种很有趣的判断复杂度的方法,它叫做 Tom McCabe 方法。

该方法很简单,通过计算函数中 决策点 的数量来衡量复杂度。下面是一种计算决策点(结合前端)的方法:

  1. 1 开始,一直往下通过函数
  2. 一旦遇到 if while for else 或者带有循环的高阶函数,比如 forEach map 等就加 1
  3. 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 ,可以称为函数还不错。我个人觉得这个判断方法还是很科学和简单的,可以作为平时写代码时判断函数需不需要重构的一个考虑点,毕竟一个函数,一眼扫去,决策点数量大致就知道是多少了,很好计算。

备注

  1. 文中卖了些呆萌,比如把算法比作妹纸,还望各位妹纸大佬多多海涵,小分队是想卖萌让文章不至于太枯燥。

  2. 文中难免有错误之处,欢迎在评论区指出,大家一起讨论,学习,进步。

  3. 这是算法小分队的第一篇输出文章,也见证了狂想录的开始和成长。

  4. 本文由从未接触过公众号编辑的 源码终结者 花了 4 个小时搞出来的,别说了,点个好看鼓励下吧,真不容易。

交流

本文算法代码在下图的 前端算法小分队知识合集 目录中。

TP 地址:https://github.com/refactoring-now/

目前刚起步,内容还不太完善,后续会持续更新内容。

如果觉得不错的话,可以 star 鼓励一下。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Parsing Techniques

Parsing Techniques

Dick Grune、Ceriel J.H. Jacobs / Springer / 2010-2-12 / USD 109.00

This second edition of Grune and Jacobs' brilliant work presents new developments and discoveries that have been made in the field. Parsing, also referred to as syntax analysis, has been and continues......一起来看看 《Parsing Techniques》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

html转js在线工具
html转js在线工具

html转js在线工具