【剑指offer】面试题：跳台阶

矫情吗；* 2022-06-12 07:21 271阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

很明显的求斐波那契数列类型的题目  
当跳n级台阶的时候，设跳法有f(n)种  
青蛙的第一步，可以跳1级，也可以跳2级（只有这两种选择）  
1. 当跳1级的时候，剩下的有f(n-1)种  
2. 当跳2级的时候，剩下的有f(n-2)种  
so, f(0) = 0, f(1) = 1, f(2) = 2, f(n) = f(n-1) + f(n-2)

## 代码 ##

public static int JumpFloor(int target) {
        if(target <= 0) 
            return 0;
        if(target <= 2)
            return target;
    
        int min = 1;
        int max = 2;
        int fib = 0;
    
        for(int i = 3; i <= target; ++i) {
            fib = min + max;
            min = max;
            max = fib;
        }
    
        return fib;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
        test3();
    }
    
    /**
     * 功能测试
     */
    private static void test1() {
        for(int i = 1; i <= 10; ++i) {
            System.out.print(_999_JumpFloor.JumpFloor(i) + " ");
        }
        System.out.println();
        System.out.println();
    }
    
    /**
     * 性能测试
     */
    private static void test2() {
        int i = _999_JumpFloor.JumpFloor(20);
        System.out.println(i);
        i = _999_JumpFloor.JumpFloor(40);
        System.out.println(i);
        System.out.println();
    }
    
    /**
     * 极端测试
     */
    private static void test3() {
        int i = _999_JumpFloor.JumpFloor(-5);
        System.out.println(i);
        i = _999_JumpFloor.JumpFloor(0);
        System.out.println(i);
        System.out.println();
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews

发表评论取消回复

表情：

评论列表（有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer-跳台阶

跳台阶题目描述: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路：其实仔细分析一下，可以发现

叁歲伎倆/ 2022年08月04日 12:50/ 0 赞/ 149 阅读

相关剑指offer面试题[9-1]-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析：如果台阶数为0，就有0种跳法；如果台阶数为1，

Dear 丶/ 2022年06月13日 02:16/ 0 赞/ 166 阅读

相关【剑指offer】面试题：变态跳台阶

完整代码地址 [完整代码地址][Link 1] 题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

ゝ一纸荒年。/ 2022年06月12日 07:22/ 0 赞/ 193 阅读

相关【剑指offer】面试题：跳台阶

完整代码地址 [完整代码地址][Link 1] 题目一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路很

矫情吗；*/ 2022年06月12日 07:21/ 0 赞/ 272 阅读

相关剑指Offer | 跳台阶

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

雨点打透心脏的1/2处/ 2022年05月25日 11:20/ 0 赞/ 173 阅读

相关剑指offer：跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。跳台阶还是个斐波那契数列 c

冷不防/ 2022年04月14日 05:13/ 0 赞/ 206 阅读

相关剑指Offer-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。初步解题思路：这题与[斐波那契数列][

深碍√TFBOYSˉ_/ 2022年03月01日 01:20/ 0 赞/ 188 阅读

相关剑指offer-跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。实现思想对于本题，可以从后往前

梦里梦外;/ 2022年02月17日 05:39/ 0 赞/ 173 阅读

相关【剑指offer】跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。题目解析：当只有一节台阶的时候由于每

深碍√TFBOYSˉ_/ 2021年11月09日 14:16/ 0 赞/ 285 阅读

相关剑指offer：跳台阶

试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。代码：跳到第n台阶有两种方式，从第n-1

た入场券/ 2021年06月24日 16:00/ 0 赞/ 375 阅读