共计 1896 个字符,预计需要花费 5 分钟才能阅读完成。
爬楼梯这个问题也是一个很经典的面试题,能够换各种人物动物,比方青蛙、小兔子跳台阶,张三李四爬楼梯等等。
题目会相似于上面这样:
假如你正在爬楼梯,须要 n 阶你能力达到楼顶,每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢?
假如有 2 个台阶,那么有两种办法能够爬到楼顶:
- 1 个台阶 + 1 个台阶
- 2 个台阶
假如有 3 个台阶,那么有三种办法能够爬到楼顶:
- 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 2 个台阶
- 2 个台阶 + 1 个台阶
假如有 5 个台阶,那么有八种办法能够爬到楼顶:
- 1 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 1 个台阶 + 1 个台阶 + 2 个台阶
- 1 个台阶 + 2 个台阶 + 2 个台阶
- 2 个台阶 + 2 个台阶 + 1 个台阶
- 2 个台阶 + 1 个台阶 + 2 个台阶
- 2 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 2 个台阶 + 1 个台阶 + 1 个台阶
- 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 思否征文「如何“反杀”面试官?」,欢送正在浏览的你也退出。