专栏首页java工会PDD面试官问我如何上楼,有点懵圈

PDD面试官问我如何上楼,有点懵圈

品品这种一步娘炮,两步扯淡的阶梯!

这个是面试PDD的时候当场要写的题目,大家可以借鉴一下哈~

呆萌程序员

算法养成记

LeetCode70

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2

Output: 2

Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: 3

Output: 3

Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

中文意思就是:

假设你正在爬楼梯。需要 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 阶

暴力法!

在暴力法中,我们将会把所有可能爬的阶数进行组合,也就是 1 和 2 。

而在每一步中我们都会继续调用 climbStairs这个函数模拟爬 1 阶和 2 阶的情形,并返回两个函数的返回值之和。

其中 i 定义了当前阶数,而 n 定义了目标阶数。

public int climbStairs1(int n) {
    return climb_Stairs(0, n);
}

public int climb_Stairs(int i, int n) {
    if (i > n) {
        return 0;
    }
    if (i == n) {
       return 1;
    }
    return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}

时间复杂度:O(2^n)

空间复杂度:O(n),递归树的深度可以达到 n

这个方法是跑不出结果的,因为成指数增长

在 n = 5 时的递归树将是这样的:

记忆化递归!

在上一种方法中,我们计算每一步的结果时出现了冗余。另一种思路是,我们可以把每一步的结果存储在 memo 数组之中,每当函数再次被调用,我们就直接从 memo 数组返回结果。

在 memo 数组的帮助下,我们得到了一个修复的递归树,其大小减少到 n。

public int climbStairs2(int n) {
    int memo[] = new int[n + 1];
    return climb_Stairs(0, n, memo);
}
public int climb_Stairs(int i, int n, int memo[]) {
    if (i > n) {
        return 0;
    }
    if (i == n) {
        return 1;
    }
    if (memo[i] > 0) {
        return memo[i];
    }
    memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
    return memo[i];
}

时间复杂度:O(n)

空间复杂度:O(n)

动态规划!

不难发现,这个问题可以被分解为一些包含最优子结构的子问题,即它的最优解可以从其子问题的最优解来有效地构建,我们可以使用动态规划来解决这一问题。

第 i 阶可以由以下两种方法得到:

在第 (i−1)阶后向上爬一阶。

在第 (i−2) 阶后向上爬 2 阶。

所以到达第 i 阶的方法总数就是到第 (i−1) 阶和第 (i−2) 阶的方法数之和。

令 dp[i]表示能到达第 i阶的方法总数:

public int climbStairs3(int n) {
    if (n == 1) {
        return 1;
    }
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

时间复杂度:O(n),单循环到 n 。

空间复杂度:O(n),dp 数组用了 n 的空间。

斐波那契数

在上述方法中,我们使用 dp 数组,其中 dp[i]=dp[i−1]+dp[i−2]。

可以很容易通过分析得出 dp[i] 其实就是第 i 个斐波那契数。

现在我们必须找出以 1 和 2 作为第一项和第二项的斐波那契数列中的第 n 个数,也就是说 Fib(1)=1且 Fib(2)=2。

public int climbStairs4(int n) {
    if (n == 1) {
        return 1;
    }
    int first = 1;
    int second = 2;
    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
    return second;
}

时间复杂度:O(n),单循环到n,需要计算第 n个斐波那契数。

空间复杂度:O(1),使用常量级空间

本文分享自微信公众号 - java工会(javagonghui),作者:除却巫山

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java改善性能小技巧

    不管有多少经验,都会被问到一些优化建议,从代码层面到数据库层面,下面介绍一些改善性能的小技巧

    三哥
  • 猿诗·用java随机生成一首诗

    三哥
  • Java能写外挂吗?那就写个跳一跳辅助程序吧

    ##起初是想使用按键精灵脚本程序控制,但还是选择熟悉的java。我这里使用了工具,造成延迟问题。也求教:java控制安卓的正确姿势,

    三哥
  • 和为0的最长连续子数组【转载+优化代码】

    题目描述和思路来自博客:http://www.cnblogs.com/coding-wtf/p/5849222.html,在此表示感谢。

    xiaoxi666
  • HDU 2389 Rain on your Parade(二分图最大匹配--Hopcroft-Karp算法)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2389

    Ch_Zaqdt
  • 算法细节系列(19):广度搜索优先

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

    题意: 求字符串 s[i…len−1] and s[0…len−1] i>0 最长公共前缀长度求解过程的比较次数

    用户2965768
  • 05:素数回文数的个数

    05:素数回文数的个数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求11到n之间(包括n),既是素数又是回文数的整数...

    attack
  • Glide 加载大尺寸图片 OOM

    而假如再执行 imageView.setImageBitmap(bitmap) 上,Graphics 也出现一个峰值,增加了近 100M

    七适散人
  • C++上机考试试题解析

    慕白

扫码关注云+社区

领取腾讯云代金券