关于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]，请计算出你能抢到的最大金额是多少。

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

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

后记

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

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