乐趣区

关于2022招聘季:不管是青蛙跳台阶还是who爬楼梯能上去就行

jiezi

爬楼梯这个问题也是一个很经典的面试题，能够换各种人物动物，比方青蛙、小兔子跳台阶，张三李四爬楼梯等等。

题目会相似于上面这样：

假如你正在爬楼梯，须要 n 阶你能力达到楼顶，每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

假如有 2 个台阶，那么有两种办法能够爬到楼顶：

  1. 1 个台阶 + 1 个台阶
  2. 2 个台阶

假如有 3 个台阶，那么有三种办法能够爬到楼顶：

  1. 1 个台阶 + 1 个台阶 + 1 个台阶
  2. 1 个台阶 + 2 个台阶
  3. 2 个台阶 + 1 个台阶

假如有 5 个台阶，那么有八种办法能够爬到楼顶：

  1. 1 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶
  2. 1 个台阶 + 1 个台阶 + 1 个台阶 + 2 个台阶
  3. 1 个台阶 + 2 个台阶 + 2 个台阶
  4. 2 个台阶 + 2 个台阶 + 1 个台阶
  5. 2 个台阶 + 1 个台阶 + 2 个台阶
  6. 2 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶
  7. 1 个台阶 + 2 个台阶 + 1 个台阶 + 1 个台阶
  8. 1 个台阶 + 1 个台阶 + 2 个台阶 + 1 个台阶

有了三个例子，咱们来倒推一下，变成代码的模式。

假如爬到楼顶的办法为f(n)，依据题目意思有两种可能

  • 爬一个台阶：f(n-1)
  • 爬两个台阶：f(n−2)

只有这两种可能，将这两种可能相加，能够失去递推公式：

f(n) = f(n-1) + f(n-2)

这样咱们就能够应用递归来实现：

但在递归时也须要解决边界问题，比方f(1) = 1，f(2) = 2，这两种状况咱们能够间接返回，而不须要递归。

所以能够失去这样的递归函数：

function climbStairs($n) {if ($n == 1) return 1;
    if ($n == 2) return 2;
    return climbStairs($n - 1) + climbStairs($n - 2);
}

echo climbStairs(2); // 2
echo climbStairs(3); // 3
echo climbStairs(5); // 8

再来看看应用循环是否能解决问题？

假如咱们应用循环来实现，那么能够应用一个数组来保留曾经计算过的值，假如应用一个数组 dp[] 来保留爬一个台阶有多少种办法：

dp[n] = dp[n-1] + dp[n-2]

和递归一样，也满足dp[1] = 1, dp[2] = 2，能够失去以下函数

function climbStairs($n) {$dp = [];
    $dp[1] = 1;
    $dp[2] = 2;
    for ($i = 3; $i <= $n; $i++) {$dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    return $dp[$n];
}

在应用递归时，咱们是从最初一个台阶开始，朝着底下的台阶去找，并不的确下一个是不是起点，只能一个一个去找。

而在应用循环时，咱们是从第一个台阶开始，往上爬，这个时候是晓得后面的办法个数的，间接拿来用就好了，不必再从新算了。

echo climbStairs(3), PHP_EOL; // 3
echo climbStairs(4), PHP_EOL; // 5
echo climbStairs(5), PHP_EOL; // 8
echo climbStairs(6), PHP_EOL; // 13
echo climbStairs(7), PHP_EOL; // 21
echo climbStairs(8), PHP_EOL; // 34

下面的枚举也能够验证咱们的猜测，实际上咱们只须要晓得：以后办法个数 = 前一个办法个数 + 前前一个办法个数。

假如 f 为以后办法个数，a和 b 别离为 前一个 和前前一个 的办法个数，能够失去一个新的循环形式：

咱们是从第 0 级开始爬的，从第 0 个到第 0 个台阶，咱们也能够当成一种办法，即f=1

function climbStairs($n) {
    $a = $b = 0;
    $f = 1;

    for ($i = 1; $i <= $n; $i++) {
        $a = $b;
        $b = $f;
        $f = $a + $b;
    }
    return $f;
}

以上就是一个动静布局的代码，间接看的话可能比拟难懂为什么这么写，通过递归和循环的验证与了解，看上去就很简略了。

在面试中遇到算法题时不要慌，能够先从简略暴力的办法动手，再尝试有没有最优解。

同时也倡议有空时能够去力扣刷刷算法题，了解一些相干概念和思路，这样就不会在遇到算法题时恐慌，不晓得该从何处动手了。

除此之外也要相熟所用的语言，特地是内置的一些函数办法，比方验证一个数是不是回文数时，PHP 就能够应用 strrev 函数，将它进行反转后再进行比拟就能够直接判断是与否了。

$n1 = 21;
$n2 = 22;
$n3 = -22;
var_dump(strrev($n1) == $n1);
var_dump(strrev($n2) == $n2);
var_dump(strrev($n3) == $n3);

面试后记得及时复盘，下次必定比这次更好~

本文参加了 SegmentFault 思否征文「如何“反杀”面试官？」，欢送正在浏览的你也退出。

退出移动版