神刀安全网

WEB前端学习:练脑算法题——求一个集合所有子集的和

Web前端开发工程师是一个很新的职业,是从事Web前端开发工作的工程师。主要进行网站开发,优化,完善的工作。网页制作是Web 1.0时代的产物,那时网站的主要内容都是静态的,用户使用网站的行为也以浏览为主。

给你学习路线,html-css-js-ajax-jq-html5-css3-bootstrap-vue.js-node.js-react.jd

WEB前端学习:练脑算法题——求一个集合所有子集的和

【题目】

给一个集合array,包含n个数。规定集合的”值”为集合中所有元素的和。求该集合的所有子集的值的和。

【示例】

数组[1,2]它的子集有空集[],[1],[2],[1,2]子集各自的值为0,1,2,3所以子集值的和为0+1+2+3=6

【解法一】

思路:简单暴力的方法就是穷举数组所有的子集,然后逐个求子集的值,然后相加得到最终的结果。

缺点:时间复杂度高,每个集合的子集个数为2^n个。

实现:

太麻烦了,不实现了。

WEB前端学习:练脑算法题——求一个集合所有子集的和

小编推荐一个学Web前端的学习裙【 五四七,三零二,三八三 】,无论你是大牛还是小白,是想转行还是想入行都可以来了解一起进步一起学习!裙内有开发工具,很多干货和技术资料分享!

【解法二】

思路:通过计算每个元素在求和过程中出现的次数,尝试获取一种规律。

[1]==> 0+1=1 // 1出现一次[1,2]==>0+1+2+(1+2)=6 // 1出现2次,2出现2次[1,2,3]===>0+1+2+3+(1+2)+(1+3)+(2+3)+(1+2+3)=24 // 1,2,3出现4次

好像有点规律了,每个元素在求和过程中出现的次数是一样的。假设出现的次数是N。

sum = (1+2+3+4+…+n) * N

N的值又和数组的长度有关系,N=2^(n-1)

sum = (1+2+3+4+…+n) * 2^(n-1)

【实现】

var childrenArraySum = function(array){ var sum = array.reduce(function (a,b) { return a+b; }) return sum * Math.pow(2, array.length-1);;};childrenArraySum([1,2,3]); // 24

第二种解法的思路很巧妙,把原本很复杂的问题用简单的方式解决了。算法或者说数学对程序员的影响还是很大的。如果在工作中能多思考一下又没有更简单的方法,下面这种写法就不会出现了。

if(a){ for(var i=0;i

WEB前端学习:练脑算法题——求一个集合所有子集的和

小编推荐一个学Web前端的学习裙【 五四七,三零二,三八三 】,无论你是大牛还是小白,是想转行还是想入行都可以来了解一起进步一起学习!裙内有开发工具,很多干货和技术资料分享!

如果有觉得有意思,欢迎转发收藏~~

WEB前端学习:练脑算法题——求一个集合所有子集的和

WEB前端学习:练脑算法题——求一个集合所有子集的和

WEB前端学习:练脑算法题——求一个集合所有子集的和

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » WEB前端学习:练脑算法题——求一个集合所有子集的和

分享到:更多 ()