【Java面试题】青蛙跳台阶

一、青蛙跳台阶

【题目】：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

【示例】：

台阶	青蛙跳法
1级台阶	1种跳法
2级台阶	2种跳法
3级台阶	3种跳法
4级台阶	5种跳法

【关键点】： 进阶斐波那契数列，动态规划

思路：
跳到第n个台阶，只有两种可能：

• 从第n-1个台阶跳1个台阶
• 从第n-2个台阶跳2个台阶

只需求出跳到第n-1个台阶和第n-2个台阶的可能跳法即可

解：设F（n）: n个台阶的跳法
递推公式：F（n）=F（n-1）+F（n-2）

不难发现这是一个斐波那契数列——起始条件为F（0）=1，F（1）=1

【Java】：

解法一：迭代（由下向上跳）

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 0) return 0;//0
        if(target == 1) return 1;//1
        if(target == 2) return 2;//1+1,2
        int one = 1;
        int two = 2;
        int result = 0;
        for(int i = 2; i < target; i++){//3级台阶以上
            result = one+ two;//前三级
            one = two;
            two = result;
        }
        return result;
    }
}

迭代优化（最快！！）

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 0) return 0;//0
        if(target == 1) return 1;//1
        if(target == 2) return 2;//1+1,2
        int a = 1;
        int b = 2;
        int c = 0;
        while(target>2){//3阶以上
            c = a+ b;//从第三个数开始，斐波那契数等于前两个数的和；
            a = b;//将前一个数给到a，开始下一次求值
            b = c;//将斐波那契数给b，开始下一次求值
            target--;
        }
        return c;
    }
}

解法二：递归（由上向下减）

public class Solution {
    public int JumpFloor(int target) {
        if(target==1){
            return 1;
        }
        else if(target==2){
            return 2;
        }
        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

二、变态跳台阶

【题目】：

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

【示例】：

台阶	变态跳法
1级台阶	1种跳法
2级台阶	2种跳法
3级台阶	4种跳法
4级台阶	8种跳法

【关键点】： 斐波那契数列的变种，贪心算法

思路： 本质上是斐波那契数列的变种，普通跳台阶是一步与两步，问题规模缩小到分成最后要跳到第 n 阶可以跳两次或者一次去求解，所以，在普通跳台阶，设置两个临时变量存下跳一次或者两次时，前面会有多少种可能的结果

这里用同一个套路来分析一下（跳数为n，n-1，…3，2，1的情况）

• 若楼梯阶级 n = 3
  跳 3 步到 3：没有剩下步数没跳的，只有这样一种跳法
  跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种
  跳 1 步到 3：剩下的是第二步没跳，起始跳到第二步有两种
  求得，n = 3 时，有 4 种跳法

• 若楼梯阶级 n = 4
  跳 4 步到 4：没有剩下步数没跳的，只有这样一种跳法
  跳 3 步到 4：剩下的是第一步没跳，起始跳到第一步只有一种
  跳 2 步到 4：剩下的是第二步没跳，起始跳到第二步只有两种
  跳 1 步到 4：剩下的是第三步没跳，起始跳到第三步有四种
  求得，n = 4 时，有 8 种跳法

若楼梯阶级 n = n

跳 x 步到 n 有几种的和

易知 f(n)=f(n-1)+f(n-2)+……f(1)
f(n-1)=f(n-2)+……f(1)

两式相减得f(n)=2f(n-1)

【Java】：
迭代：

public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 0) return 0;
        if (target == 1) return 1;
        int a = 1;
        int b = 2;
        for (int i = 2; i <= target; i++) {
            b = 2 * a;
            a = b;
        }
        return b;
    }
}

public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 0) return 0;
        if (target == 1) return 1;
        int a = 1;
        int b = 2;
        while(target>=2){
            b = 2 * a;
            a = b;
            target--;
        }
        return b;
    }
}

其他解法：

位移操做：（<<有符号左移位，将运算数的二进制整体左移指定位数，低位用0补齐。）

public class Solution {
    public int JumpFloorII(int target) {
        //位移操作
        int a=1;
        return a<<(target-1);
    }
}

公式变形：2^(n-1)

public class Solution {
    public int JumpFloorII(int target) {
        //位移操作
        if (target <= 0) return 0;
        return (int) Math.pow(2, target - 1);
    }
}

转载：https://blog.csdn.net/cungudafa/article/details/101152378