关于javascript:图解算法-LeetCode第-70-题爬楼梯问题

38次阅读

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

最近开始致力钻研算法,遇到这个很有意思的题目,因为从中温习到斐波那契数列,又通过某篇材料,查到中科院官网,看了很多科普文章。深挖上来能看到很多货色。

本着酷爱分享的初衷,整顿本文与大家分享,题目自身没啥难度,欢送一起交换,算法大佬求不喷,多谢。

进入主题。


本题为 LeetCode 第 70 题爬楼梯,题目如下:

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

大家能够先想想

流程剖析

本题中,能够每次能够走 1 级,也能够一次走 2 级,因而咱们会有 3 种走法:

  • 全程任意走,如全副 1 级走;
  • 后面任意走,最初一步只走 1 级;
  • 后面任意走,最初一步只走 2 级;

我画了几张图不便大家了解,如下:

第一种走法就不做具体介绍。

第二种走法,倒数第二步的走法如下,有 1 步和 2 步两种形式:

第三种走法,倒数第二步的走法如下,也有 1 步和 2 步两种形式:

下面这个过程形容的是,从最初一层开始往下的每一层的走法。

在最初一步时,有 1 步和 2 步两种形式,能够了解为只能 1 步或者 2 步达到最初一层。

  • 当最初一步为 1 步时,即从 n-1 层开始;
  • 当最初一步为 2 步时,即从 n-2 层开始;

再了解一下这个过程,就是第 n 层的走法数量是第 n-1 层和第 n-2 层走法数量之和。

如果还不太了解,能够再看看后面的图。

归纳法剖析

当然,遇事不决,归纳法走起,咱们能够列举几种状况进行剖析:

台阶层数 走法数量 走法
1 1 1
2 2 11、2
3 3 111、12、21
4 5 1111、112、121、211、22
5 8 11111、1112、1121、1211、2111、221、212、122

能够发现有个简略的法则,当台阶层数为 n 层,它的走法数量就有 n-1 层的走法数量加上 n-2 层的走法数量。

记做:f(n)=f(n-1)+f(n-2)

第 1 层固定 1 种走法;
第 2 层固定 2 种走法;

第 5 层走法的数量等于第 4 层加上第 5 层走法数量。

了解分明整个流程法则当前,咱们就能够编码就简略多了:

解法 1:循环累加计算

通过简略的循环累加就能失去后果:

const climbStairs = (n = 1) => {if(n <= 2) return n;
    let res = 0, n1 = 1, n2 = 2; // n1 示意前 2 项,n2 示意前 1 项
    for(let i = 3; i<= n; i++){  // 前两项值固定,因而从第 3 项开始循环
        res = n1 + n2;
        n1 = n2;
        n2 = res;
    }
    return res;
}

测试下第 6 层的走法数量:

climbStairs(6); // 13

解法 2:递归计算

依照 f(n)=f(n-1)+f(n-2),这个办法更加简略:

const climbStairs = (n = 1) => {if(n <= 2) return n;
    return climbStairs(n-1) + climbStairs(n-2);
}

测试下第 6 层的走法数量:

climbStairs(6); // 13

这个办法比拟简洁易懂,但递归比拟费时,容易呈现 LeetCode 超出工夫限度的提醒。

解法 3:利用数组个性

利用 f(n)=f(n-1)+f(n-2) 这个法则,先预设好前 2 项,再开始循环,最初返回数组最初一项即可:

const climbStairs = n => {let result = [1,2];
    for (let i = 2; i < n; i++) {result.push(result[i-1] + result[i-2]);
    }
    return result[n-1];
};

解法 4:利用 JavaScript ES6 新个性

利用数组构造赋值操作:[a, b] = [c, d]

const climbStairs = n => {
    let a = b = 1;
    for (let i = 0; i < n; i++) {[a, b] = [b, a + b];
    }
    return a;
};

当然,大家还有其余解法,欢送一起探讨~

拓展常识:每次能够走 1 步、2 步、3 步

这里多减少了一次能够走 3 步,这时候最初一步会有以下状况:

  • 当最初一步为 1 步时,即从 n-1 层开始;
  • 当最初一步为 2 步时,即从 n-2 层开始;
  • 当最初一步为 3 步时,即从 n-3 层开始;

革新一下后面解法,还是一样:

const climbStairs = (n = 1) => {if(n <= 2) return n;
      if(n == 3) return 4;
    return climbStairs(n-1) + climbStairs(n-2) + climbStairs(n-3);
}

测试下第 6 层的走法数量:

climbStairs(6); // 24

拓展常识:斐波那契数列

这一题次要考查的内容相似斐波那契数列(Fibonacci sequence)的计算,如果你还不分明什么是斐波那契数列,这边先简略介绍一下,另外举荐李永乐老师解说的斐波那契的课。

最早是有由数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子滋生为例子而引入的,数列大抵如:0、1、1、2、3、5、8、13、21、34、….。
认真察看,咱们能够发现一个法则: 从第 3 项开始,每一项的值都等于前两项之和

在自然界中,存在着许许多多的斐波那契数列的排列形式,比方一棵一般的树,它的树枝成长状况就像上面这样:

(图片起源网络)

能够看到每一层枝干的数量为 1、2、3、5、8、… 排列上来。当然还有很多其余的:

(自然界中各种各样的裴波那契螺旋,图片来源于网络)

依据斐波那契数列的法则,失去这样的公式 f(n)=f(n-1)+f(n-2)。跟咱们后面列的差不多。

总结

这道题自身难度不大,然而如果没有理清流程和法则,很容易掉坑,写多余的代码。本文只列举 4 个简略实现办法,如果大家有其余实现形式,欢送一起探讨,哈哈。

正文完
 0