关于javascript:面试官在逗你系列到底应该怎么爬楼梯

直奔主题

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

明天咱们就来个单刀直入，直奔主题，从一个实在面试题到底怎么爬楼梯来聊一聊算法中的动静布局 。

面试真题

小明家有一楼梯共有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

间断执行三次数据如下：

注：在执行过程中有卡顿，不是霎时输入~，如果执行的是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;}

雷同环境下，咱们再来执行测试，间断执行三次数据如下：

耗费的工夫居然相差百倍之多，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),执行起来更加是和那啥一样，晦涩、顺滑~

咱们来看下测试成果，间断执行三次测试后果如下：

绝对于递归的实现形式，递推的实现从工夫复杂度上更低，执行也会更高效~

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

动静布局的算法问题有很多种不同的模式，爬楼梯是其中的一种。在这里胡哥要给大家留一道面试题啦，看看大家对动静布局是不是有了粗浅的了解。

面试真题如下：

你是一个有信奉的匪徒，有一排屋宇期待你去抢劫，在抢劫中不能相邻的屋宇不能抢，只能距离一个或多个屋宇进行抢劫，屋宇中钱财都是非负整数，数据格式如下：[3, 4, 5, 2, 1, 1]，请计算出你能抢到的最大金额是多少。

这个匪徒相当有信奉，居然不都抢走~

欢送各位小伙伴留言，谈谈你对动静布局的了解，留下这道面试题的答案，一起来探讨交换~

后记

以上就是胡哥明天给大家分享的内容，喜爱的小伙伴记得点赞、珍藏呦，关注胡哥有话说，学习前端不迷路，欢送多多留言交换...

胡哥有话说，专一于大前端技术畛域，分享前端零碎架构，框架实现原理，最新最高效的技术实际！