欢迎光临
我的个人博客网站

面试官在“逗”你系列:到底应该怎么爬楼梯?!


直奔主题

算法题是在面试过程中考察候选人逻辑思维能力、手写代码能力的一种方式,因为有一句古话说的好:“说一千道一万,不如写段代码看一看”。

面试官在“逗”你系列:到底应该怎么爬楼梯?!

今天我们就来个单刀直入,直奔主题,从一个真实面试题到底怎么爬楼梯来聊一聊算法中的动态规划

面试真题

小明家有一楼梯共有10级台阶,每次可以爬1级或2级,问小明爬到第10级台阶,一共有多少种走法?

为什么是“小明”呢?这是个奇怪的问题~

真题分析

很多同学在第一次遇到这个爬楼梯的问题可能会比较,不知道该如何来解决。我们首先需要做的就是寻找这个问题的关键点:每次只能爬1级或2级

递归思想

小明每次只能爬1级或2级,那么对于爬到第10级台阶来说,最后一次操作为走1级(此时处于第9级台阶上)或走2级(此时处于第8级台阶上)。
假定我们有个表达式f可以来计算到达某阶台阶的走法,那么对于第10阶来说,这个表达式就应该为:f(10) = f(9) + f(8)

对于这个表达式,是不是有种瞬间回到那初、高中的年代~

按如上规则,再次考虑,爬到第9级台阶时,最后一次操作为走1级(此时处于第8级台阶上)或走2级(此时处于第7级台阶上),此处的表达式为:f(9) = f(8) + f(7)

……

依次处理,当爬到第3级台阶时,计算的表达式就是f(3) = f(2) + f(1)

那爬到第2级台阶有几种方式呢:每次走1级或者一次走2级,也就是一共有2种走法,f(2) = 2

爬到第1级台阶的方式肯定只有一种:走1级,f(1) = 1

按我们的思考逻辑,相关代码如下:

/**  * @method climbStairs  * @description 爬楼梯  * @param {number} n 楼梯台阶数  * @return {number} 一共有多少种走法 */ function climbStairs (n) {   if (n === 1) { return 1 };   if (n === 2) { return 2 };    let num = 0;   num = climbStairs(n - 1) + climbStairs(n - 2);   return num; }  // 调用函数,输出结果 let num = climbStairs(10); console.log(num); // 89 

Congratulations~我们已经完成啦,得到了正确的结果。

就在你满脸微笑、志得意满的向面试官讲解思路的时候,面试官十有八九会一副老狐狸得逞的样子,继续问你,假如n的值比较大的,如40之类的,上面定义的climbStairs的执行性能如何。

我们来看下执行的性能:

测试代码如下:

console.time(); let num = climbStairs(40); console.log(num); console.timeEnd() 

我的mac配置如下:

MacBook Pro  处理器:2.5 GHz 四核Intel Core i7 内存: 16GB 

连续执行三次数据如下:

序号 结果 执行时间
1 165580141 811.077ms
2 165580141 817.025ms
3 165580141 814.803ms

注:在执行过程中有卡顿,不是瞬间输出,如果执行的是“`climbStairs(100)“`,你应该会瞬间听到风扇启动的呜呜声

递归思想优化

在上面代码climbStairs的基础上我们来进行优化处理。我们仔细分析代码的执行流程,就会发现有很多重复计算的地方,比如说f(5)就会在f(6-1)f(7-2)时被重复计算,这就浪费了时间和性能。

那我们就选择使用空间换时间的策略,设置对象numbers,保存爬到某级台阶的结果,避免重复计算,numbers对象的结果如下:

let numbers = {   1: 1,   2: 2 } 

优化后代码如下:

/**  * @method climbStairs  * @description 爬楼梯  * @param {number} n 楼梯台阶数  * @return {number} 一共有多少种走法 */ function climbStairs (n) {   // 存储计算的结果,key(台阶) : num(走法)   let numbers = {     1: 1,     2: 2   };    let tmpClimbStairs = function (n) {     // 已存在的数据,直接返回,不再重新计算     if (numbers[n]) {       return numbers[n];     }      // 不存在的数据,进行计算     let num = tmpClimbStairs(n - 1) + tmpClimbStairs(n - 2);     // 计算完成后,存放如numbers中,下次可以直接使用     numbers[n] = num;      // 返回结果     return num;   }    // 计算结果   let num = tmpClimbStairs(n);   // 返回结果   return num; } 

相同环境下,我们再来执行测试,连续执行三次数据如下:

序号 结果 执行时间
1 165580141 7.100ms
2 165580141 7.478ms
3 165580141 6.260ms

消耗的时间竟然相差百倍之多,It’s amazing!说明我们使用空间换时间的策略是正确的。

执行结果几乎是瞬间输出的,执行如丝袜奶茶般顺滑~此时此刻你可以再次执行climbStairs(100)来体验下绝对的性能飙升!

这道面试题处理成这样已经是非常OK的了,但是如果你已经感到彻底满足,为自己的聪明才智感到骄傲了,你就会听到面试官可爱(恨)的声音传来:”还有别的方法或性能更好的方法来实现吗?“

是不是心中一口老血想喷出来面试官是不是故意的,是不是在针对我

哈哈,不慌不慌,小场面~

递归与递推

递归与递推是两种不同的看待、分析问题的思路。

递归:自顶向下的处理逻辑,有相应的临界点(终止递归的点);

递推:自底向上的处理逻辑,到达目标点结束。

递推思想

我们重新使用递推的方式再来看这个问题。

  1. 爬到第1级台阶,有1种方式。 f(1) = 1

  2. 爬到第2级台阶,有2种方式:每次1级或1次2级。f(2) = 2

  3. 爬到第3级台阶的情况呢?

    不要忘了我们之前分析的关键点:每次只能1级或2级,
    对于第3级台阶来说,可以是从第1级台阶出发也可以是从第2级台阶出发,
    所以f(3) = f(2) + f(1)

  4. 同理可得爬到第4级台阶的情况,f(4) = f(3) + f(2)

我们得出一个结论:对于第N(N > 2)级台阶,其表达式为f(N) = f(N-1) + f(N-2)。那么我们在结算的过程中,每次都记录下f(N-1)f(N-2)的值,逐级迁移这个值,就可以得到f(N)了。

现在climbStairs代码如下:

/**  * @method climbStairs  * @description 爬楼梯  * @param {number} n 楼梯台阶数  * @return {number} 一共有多少种走法 */ function climbStair (n) {   // 通过观察,我们可只第1级和第2级都是返回对应的n   if (n <= 2) {     return n;   } else {     // 对于n > 2的情况     let i = 1;  // 初始存放第1级台阶的走法,对应的是f(N-2)     let j = 2;  // 初始存放第2级台阶的走法,对应的是f(N-1);      // 定义走法num     let num;      // 从第3级开始,执行循环操作     for (let k = 3; k <= n; k++) {       // f(N) = f(N-1) + f(N-2)       num = i + j;        // 同时移动       // 将f(N-1)的值给f(N-2)       i = j;       // 将当前值给f(N-1)       j = num;     }     // 返回结果     return num;   } } 

这一次我们直接在时间复杂度上降低了,变成了O(N),执行起来更加是和那啥一样,流畅、顺滑~

我们来看下测试效果,连续执行三次测试结果如下:

序号 结果 执行时间
1 165580141 6.570ms
2 165580141 6.647ms
3 165580141 6.658ms

相对于递归的实现方式,递推的实现从时间复杂度上更低,执行也会更高效~

此时此刻,这个爬楼梯的问题终于是回答圆满了,这个时候面试官看你就会像丈母娘看女婿一样,怎么看怎么可爱

动态规划的算法问题有很多种不同的形式,爬楼梯是其中的一种。在这里胡哥要给大家留一道面试题啦,看看大家对动态规划是不是有了深刻的理解。

面试真题如下:

你是一个有信仰的强盗,有一排房屋等待你去抢劫,在抢劫中不能相邻的房屋不能抢,只能间隔一个或多个房屋进行抢劫,房屋中钱财都是非负整数,数据格式如下:[3, 4, 5, 2, 1, 1],请计算出你能抢到的最大金额是多少。

这个强盗相当有信仰,竟然不都抢走~

欢迎各位小伙伴留言,谈谈你对动态规划的理解,留下这道面试题的答案,一起来探讨交流~

后记

以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞收藏呦,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流…

胡哥有话说,专注于大前端技术领域,分享前端系统架构,框架实现原理,最新最高效的技术实践!

赞(1) 打赏
未经允许不得转载:张拓的天空 » 面试官在“逗”你系列:到底应该怎么爬楼梯?!
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏