头条前端面经之算法题,走阶梯步数问题

来自于2019年5月, 头条前端面试, 一个长阶梯有n级,可以一次走1级,一次走2级,一共有多少种走法

这是一个非常抽象的现实问题,要用算法编程实现,首先我们得分析出算法模型出来

我们来看下逐步学习下:

从问题中抽象出模型

假设我们给阶梯编号依次为 1 - n,因此阶梯是
1 2 3 4 5 … (n-2) (n-1) (n)

我们要从阶梯1 走到阶梯 n,每次只能跨1或者2阶

我们用递归思想来看下,要走到第 n 阶,只能

  • 从第 n - 1 阶跨 1步 到第 n 阶
  • 从第 n - 2 阶跨 2步 到第 n 阶

对吧,别无他法了
那有人就会说我也可以从 n -3 跨1步、2步或者2步、1步到 n阶啊,但是你别忘了,你说的这两种方法都是先到 n -1 或 n - 2,已经被计算在内了

因此假设我们走到 n 的方法有 fn,走到 n - 1阶的方法有 f(n-1) ,走到 n - 2阶的方法有 f(n-2)
于是得出:
f(n) = f(n - 1) + f(n - 2),此时 n >= 2

因此得出的公式是:

  • n = 1 f(n) = 1
  • n = 2 f(n) = 2↵
  • n >= 3 f(n) = f(n-1) + f(n-2)

有没有发现类似于斐波那契数列,唯一的区别在于 f(2) 的时候不一样而已

最后,我们得到的模型结论是,这是一个类斐波那契数列,公式如上

代码实现

既然是一个类斐波那契数列,那我们就好办了

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 步行n阶的走法数,n是正整数
*/
function fibornacci(n) {
if (n <= 2) return n;

let [pre, cur] = [1, 2]
for (let i = 3; i <= n; ++ i) {
[pre,cur] = [cur, pre + cur];
}

return cur
}

当然我们也可以用递归方式实现,具体这里不写递归版本了,可以参考本博客斐波那契数列一章

斐波那契序列的算法 – 头条面试题

 
更多前端面试题和算法题,请搜索微信小程序 前端面试精华
前端面试精华
前端面试精华

坚持原创技术分享,谢谢鼓励我继续创作!