关于leetcode:记字节前端面试一道简单的算法题

记字节前端面试一道简略的算法题

70. 爬楼梯（medium）

假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

留神：给定 n 是一个正整数。

示例 1：

输出： 2
输入： 2
解释：有两种办法能够爬到楼顶。

1 阶 + 1 阶
2 阶

办法1.动静布局

思路：因为每次能够爬 1 或 2 个台阶，所以到第n阶台阶能够从第n-2或n-1上来，其实就是斐波那契的dp方程
复杂度剖析：工夫复杂度O(n)，空间复杂度O(1)

Js:

var climbStairs = function (n) {    const memo = [];    memo[1] = 1;    memo[2] = 2;    for (let i = 3; i <= n; i++) {        memo[i] = memo[i - 2] + memo[i - 1];//所以到第n阶台阶能够从第n-2或n-1上来    }    return memo[n];};//状态压缩var climbStairs = (n) => {    let prev = 1;    let cur = 1;    for (let i = 2; i < n + 1; i++) {        [prev, cur] = [cur, prev + cur]        // const temp = cur;   // 暂存上一次的cur        // cur = prev + cur;   // 以后的cur = 上上次cur + 上一次cur        // prev = temp;        // prev 更新为 上一次的cur    }    return cur;}

Java:

class Solution {    public int climbStairs(int n) {        int prev = 1, cur = 1;        for (int i = 2; i < n + 1; i++) {        int temp = cur;        cur = prev + cur;          prev = temp;         }        return cur;    }}

关于leetcode:记字节前端面试一道简单的算法题

70. 爬楼梯（medium）

办法1.动静布局

视频解说（高效学习）:点击学习

目录：

70. 爬楼梯 （medium）

办法1.动静布局

视频解说（高效学习）:点击学习

目录：

70. 爬楼梯（medium）