1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录

[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录

第 10-1 题:跳台阶(斐波拉契数列、滚动变量)

传送门:AcWing:跳台阶牛客网 online judge 地址牛客网 online judge 地址

输入一个整数 n ,求斐波那契数列的第 n 项。

假定从 0 开始,第 0 项为 0 。(n \\le 39)

样例:

输入整数 n=5

返回 5

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路:这题的数据范围很小,我们直接模拟即可。当数据范围很大时,就需要采用其他方式了,可以参考求解斐波那契数列的若干方法。写成动态规划,如果使用递归,一定要加上缓存,否则会重复求解子问题,导致效率低下。

  • 题目背景是斐波拉契数列。
  • 在实现的时候思考如何节约空间,其实使用常数级别的辅助空间就可以了。

时间复杂度:总共需要计算 n 次,所以时间复杂度是 O(n)

Python 代码1:用两个变量滚动式往后计算,a 表示第 n−1 项,b 表示第 n 项。则令 c=a+b 表示第 n+1 项,然后让 ab 顺次往后移一位。

  class Solution(object):
        def Fibonacci(self, n):
            """
            :type n: int
            :rtype: int
            """

            if n == 0:
                return 0
            if n == 1:
                return 1
            a = 0
            b = 1

            while n:
                c = a + b
                # “滚动变量”:接下来重新定义 a 和 b
                a = b
                b = c
                n -= 1
            return a

Python 代码2:Python 语法糖,了解即可

  class Solution(object):
        def Fibonacci(self, n):
            """
            :type n: int
            :rtype: int
            """

            if n == 0:
                return 0
            if n == 1:
                return 1
            a = 0
            b = 1

            while n:
                a , b = a + b , a
                n -= 1
            return a

Python 代码3:

  class Solution:
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            a = 0
            b = 1

            while n:
                a , b = b , a + b 
                n -= 1
            return b

参考资料:面试官问你斐波那契数列的时候不要高兴得太早。书上斐波拉契数列数列空间更省的写法,P76。

Java 代码:

  public class Solution {

        // 1 1 2 3 5 8
        // 0 1 2 3 4 5
        public int Fibonacci(int n) {
            if (n == 0) {
                return 0;
            }
            if (n == 1) {
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int fibonacci = solution.Fibonacci(5);
            System.out.println(fibonacci);
        }
    }

Java 代码:

  public class Solution {

        // 1 2 3 5 8
        // 1 2 3 4 5
        public int JumpFloor(int target) {
            int n = target;
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        // i j (i+j)
        // 1 2 3 5
        // 1 2 3 4
        public int JumpFloor1(int target) {
            if (target == 1) {
                return 1;
            }
            int n = target;
            int i = 1;
            int j = 2;
            int temp;
            for (int k = 3; k <= n; k++) {
                temp = j;
                j = i + j;
                i = temp;
            }
            return j;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            for (int i = 1; i < 5; i++) {
                int jumpFloor = solution.JumpFloor1(i);
                System.out.println(jumpFloor);
            }
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录

链接:https://www.javajike.com/article/3261.html

« [剑指 Offer 第 2 版第 10 题] “变态跳台阶”做题记录
[剑指 Offer 第 2 版第 11 题] “旋转数组的最小数字”做题记录»

相关推荐

QR code