太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考察js算法

),上面写着“1、1、2、3、5、8......,求第n个数的值”

不得不承认,当时我第一眼看这道题大脑里是懵逼的。后来才想起来,这不就是数学题里的那个斐波那契(肥婆纳妾)数列么!从第三个数开始,每个数都是前两个数的和。

能get到这个点,你已经成功了一半了。另一半就是需要你将数学公式逻辑转变成js程序逻辑。

那其实这个问题还可以换个问法:实现一个函数,输入一个数字n能返回斐波那契数列的第n个值。

大概的思路是这样的:

首先我们要把特殊的部分给独立出来做个判断,哪些数字是特殊的呢?很明显是斐波那契数列的前两项,而斐波那契数列的前两项都为1。然后定义三个变量,firstNum、secondNum、total,分别代表着第一个数字,第二个数字,还有他们俩之和。然后通过一个for循环遍历,将firstNum加上secondNum的结果赋值给total,然后将secondNum的value赋值给firstNum,把total的value赋值给secondNum,以此根据传入的n来不断地循环叠加,达到想要的total值,最后return返回出去。

思路说完后,让我们用js把它实现出来:

// 可能是最普通的解法

var series = function (n) {

var sum = [0, 1];

if(n < 2) {

return sum[n];

}

var firstNum = 0;

var secondNum = 1;

var total = 0;

for (var i = 2; i<= n; i++) {

total = firstNum + secondNum;

firstNum = secondNum;

secondNum = total;

}

return total;

}

记住,面试官与咱们应聘者的思维不同,你应聘的时候你大部分时间是在想,这道题我会不会做,能不能做出来,而他们想的是这道题的最优解。

前端的工作,“最优解”其实是一种自我追求进步的表现。

除了以上这种办法,还有什么更好的解决办法吗?答案是有的。

先来看看迭代的解法

var series = function (n) { var feipo = [0,1]; for(var i=2;i<=n;i++){ feipo[i] = feipo[i-1] + feipo[i-2] } return feipo[n]; } // console.log(series(6));

再来看看递归的解法

var series = function (n) { if(n >= 2) { return series(n-1) + series(n-2) }else { return n; } } // console.log(series(6));

究竟哪个才是最优解,相信看完文章的你们已经有了答案。

可能你们会问:

那闰土你在笔试时做出来了么? 你猜~

我想说的话

目前为止我也参加过很多次大大小小的前端面试,确实也听说过有不少面试官会问到一些算法。通常会涉及的,是链表、树、字符串、数组相关的知识。前端面试对算法要求不高,似乎已经是业内的一种共识了。虽说算法好的前端面试肯定会加分,但是仅凭常见的面试题,而不去联系需求,很难让人觉得,算法对于前端真的很重要。

直到有这么一天,太原这家公司的前端leader给我出了这么一道js算法题之后,还跟我聊了很多内容,与我固有的思维产生了强烈的碰撞。面试官还跟我讲,他们公司的技术总监是微软出身,很注重算法这块,他当初应聘进来的时候,也是考察的算法。

虽然这次面试被pass了,但是我认为工程师都应该学习算法,我觉得那不仅仅是对软件工程思想的培养,更是一种对心智的锻炼。

原文发布于微信公众号 - 闰土大叔(running_hacker)

原文发表时间:2018-06-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

关于如何培养算法思维的一点思考

最近收到公众号里一个同学的消息,大概意思是觉得自己做了很多题(可能是参考别人的题解),但是碰到问题还是经常没有思路,想问下如何才能正确的做题,以...

22720
来自专栏企鹅号快讯

或许,这会是全民皆知的一门编程语言

不久前,国务院印发了《新一代人工智能发展规划》,其中明确指出,要实施全民智能教育项目,在中小学阶段设置人工智能相关课程,逐步推广编程教育,鼓励社会力量参与寓教于...

37650
来自专栏互扯程序

15个变态的Google面试题以及答案

在当前经济形势不景气的情况下,谷歌招聘新员工是一件令人振奋的事,特别是对那些在当前金融风暴中渴望找到安全港的年轻经理们和软件开发商们来说是个好消息。  

21410
来自专栏ACM小冰成长之路

HDU-5935-Car

ACM模版 描述 ? 题解 车子从起始位置 00 开始到达终点一共有 NN 个位置被标记,每个位置被标记的时间都是整数时间,并且车子速度在每段儿都可以理解为匀速...

19580
来自专栏专知

【LeetCode 344】关关的刷题日记26 Reverse String

关关的刷题日记26 – Leetcode 344. Reverse String 题目 Write a function that takes a string...

28170
来自专栏java一日一条

程序员才看得明白的面试圣经

除了直接申请面试以外,一般说来,还有两种途径来获得面试的机会:由现在的雇主推荐,或者通过LinkedIn。虽然前者会快一些、更尊敬一些,但后者很可能是大部分应聘...

11510
来自专栏java达人

或许,这会是全民皆知的一门编程语言

不久前,国务院印发了《新一代人工智能发展规划》,其中明确指出,要实施全民智能教育项目,在中小学阶段设置人工智能相关课程,逐步推广编程教育,鼓励社会力量参与寓教于...

21580
来自专栏Crossin的编程教室

你“听”过这些经典排序算法吗?

算法是编程知识体系中的重要部分。当你已经掌握了一些编程基础之后,必然需要了解算法相关的知识,才能可以写出效率更高的代码。而排序算法又是算法中非常基础的内容。

11720
来自专栏CDA数据分析师

排序在数据分析中有多重要?

说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有...

18960
来自专栏海天一树

我是如何成为一名少儿编程竞赛老师的

2017年9月,我以前一个同事问我能不能教他小孩Theo学习编程,因为以前在同一家公司时,我那同事经常带Theo去公司,我和Theo也认识,所以我答应了。

25040

扫码关注云+社区

领取腾讯云代金券