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

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

70. 爬楼梯（medium）

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

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

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

示例 1：

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

1. 1 阶 + 1 阶
2. 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;
    }
}

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

目录：

1. 开篇介绍

2. 工夫空间复杂度

3. 动静布局

4. 贪婪

5. 二分查找

6. 深度优先 & 广度优先

7. 双指针

8. 滑动窗口

9. 位运算

10. 递归 & 分治

11 剪枝 & 回溯

12. 堆

13. 枯燥栈

14. 排序算法

15. 链表

16.set&map

17. 栈

18. 队列

19. 数组

20. 字符串

21. 树

22. 字典树

23. 并查集

24. 其余类型题