前端刷题路-Day21|刷题打卡

我心飞翔 分类:javascript

掘金团队号上线,助你 Offer 临门! 点击 查看详情

爬楼梯(题号70)

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶
 

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
 

链接

leetcode-cn.com/problems/cl…

解释

乍一看一脸懵逼,仔细一看就是斐波那契数列,问题迎刃而解。

自己的答案(简单递归)

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

确实很简单,但递归次数太多,会直接超时,无法采用

自己的答案(递归+记忆化)

var climbStairs = function(n) {
  var res = [0,  1, 2]
  function findNum(n) {
    if (!res[n]) {
      res[n] = (res[n - 1] || findNum(n - 1)) + (res[n - 2] || findNum(n - 2))
      return res[n]
    }
    return res[n]
  }
  return findNum(n)
};
 

利用res存储已经算过的值,如果有直接取,如果没有则开始i计算。

其实这种方法的性能已经不错了,跑了几次,最高能到90%以上,也不知道为啥,但仍然有更优解。

自己的答案(动态规划)

var climbStairs = function(n) {
  var res = [0, 1, 2]
  for (let i = 3; i < n + 1; i++) {
    res[i] = res[i - 1] + res[i - 2]
  }
  return res[n]
};
 

先给res赋值,为了解决n是1或者2的情况。

之后从3开始循环,直到i等于n,每次新的i值等于前两位的和。

最后取res的最后一位即可。

倒序思想,从小到大递增,简单易懂。

自己的答案(动态规划升级)

从👆的答案可以看出来,其实每次n只要取n-1n-2的值即可,那么数组里是不是只要留两个值就行了?答案是可以的:

var climbStairs = function(n) {
  if (n <= 2) return n
  var res = [1, 2]
  for (let i = 3; i < n + 1; i++) {
    res = [res[1], res[0] + res[1]]
  }
  return res[1]
};
 

当然了,其实用两个变量来代替res[0]res[1]也可以,性能上的细微差别。

更好的方法

更好的方法当然是有的,但笔者这辈子是不可能想出来的,有两种:

  1. 矩阵快速幂

  2. 通项公式

有兴趣的同学可以看看LeetCode的官方题解,说的比较详细:leetcode-cn.com/problems/cl…

PS:想查看往期文章和题目可以点击下面的链接:

这里是按照日期分类的👇

前端刷题路-目录(日期分类)

经过有些朋友的提醒,感觉也应该按照题型分类
这里是按照题型分类的👇

前端刷题路-目录(题型分类)

有兴趣的也可以看看我的个人主页👇

Here is RZ

回复

我来回复
  • 暂无回复内容