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

ゝ一纸荒年。 2022-06-12 07:22 212阅读 0赞

## 完整代码地址 ##

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

## 题目 ##

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

## 思路 ##

跳上1级台阶有1种跳法（1）  
跳上2级台阶有2种跳法（1-1、2）  
跳上3级台阶有4种跳法（1-1-1、1-2、2-1、3）  
**设跳上n级台阶有f(n)种跳法**  
f(n)种方法包括：  
1. 跳上1级台阶后直接跳上n级台阶  
2. 跳上2级台阶后直接跳上n级台阶  
3. 跳上3级台阶后直接跳上n级台阶  
4. ……  
n-1. 跳上n-1级台阶后直接跳上n级台阶  
n. 直接跳上n级台阶  
**so, 当n=1时，f(n) = 1**  
**当n>1时， f(n) = f(1) + f(2) + … + f(n-1) + 1**  
综上  
f(n) = 2 ^ (n-1)

## 代码 ##

public static int JumpFloorII(int target) {
        if(target <= 0) 
            return 0;
        int result = 1;
        for(int i = 0; i < target-1; ++i) {
            result *= 2;
        }
        return result;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    /**
     * 功能测试
     */
    private static void test1() {
        for(int i = 1; i < 10; ++i) {
            System.out.println(_998_JumpFloorII.JumpFloorII(i));
        }
        System.out.println();
        System.out.println();
    }
    
    /**
     * 极端测试
     */
    private static void test2() {
        int i = _998_JumpFloorII.JumpFloorII(0);
        System.out.println(i);
        i = _998_JumpFloorII.JumpFloorII(-1);
        System.out.println(i);
    }

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

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer 变态跳台阶

目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 public class Solut...

叁歲伎倆/ 2024年04月18日 10:04/ 0 赞/ 85 阅读

相关剑指offer - 变态跳台阶

找规律题 public class Solution { public int JumpFloorII(int n) { in

灰太狼/ 2022年09月25日 01:26/ 0 赞/ 166 阅读

相关剑指Offer-变态跳台阶

变态跳台阶题目描述: 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路：仔

谁借莪１个温暖的怀抱￠/ 2022年08月04日 12:50/ 0 赞/ 190 阅读

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

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

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

相关剑指Offer | 变态跳台阶

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

谁践踏了优雅/ 2022年05月25日 12:39/ 0 赞/ 189 阅读

相关剑指offer：变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。因为n级台阶，第一步有n种跳法：跳1级、跳2级

快来打我*/ 2022年04月14日 05:13/ 0 赞/ 204 阅读

相关剑指Offer-变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。初步解题思想：跳上一级台阶有1中跳法，跳上两级

系统管理员/ 2022年03月01日 05:40/ 0 赞/ 199 阅读

相关剑指offer-变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。实现思想 ①这里的f(n) 代表的是n个

叁歲伎倆/ 2022年02月15日 20:51/ 0 赞/ 251 阅读

相关剑指offer 变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。【分析】因为n级台阶，第一步有n种跳法：跳

男娘i/ 2022年02月01日 07:27/ 0 赞/ 217 阅读

相关剑指offer：变态跳台阶

试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：同理，从后往前想： f(n) =

Love The Way You Lie/ 2021年06月24日 16:00/ 0 赞/ 357 阅读