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

35次阅读

共计 1896 个字符,预计需要花费 5 分钟才能阅读完成。

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

题目会相似于上面这样:

假如你正在爬楼梯,须要 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) = 1f(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 为以后办法个数,ab 别离为 前一个 前前一个 的办法个数,能够失去一个新的循环形式:

咱们是从第 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 思否征文「如何“反杀”面试官?」,欢送正在浏览的你也退出。

正文完
 0