跳台阶(思路和实现)

KLQ 2020-05-12 10:53:49 java常见问答 7337

下面要给大家分享的实例同样是和跳台阶相关的内容,一起来看看具体的题目,以及解题思路和实现方式吧。

题目:

一只青蛙一次能够跳上1级台阶,也能够跳上2级台阶。

求:

这只青蛙跳上一个n级台阶一共的跳法有多少种?

注:

先后次序不同算不同的结果

思路1:

对于这个题目的话,前提是只有1次1阶或者是2阶的跳法

1、假如2种跳法,1阶或者是2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1)

2、假如,第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2)

3、由a假设可以得出总跳法为:f(n)=f(n-1)+f(n-2)

4、之后通过实际的情况可以得出:只有一阶的时候f(1)=1 ,只有两阶的时候可以有f(2)=2

5、最终得出一个斐波那契数列:

跳台阶

代码实现:

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

思路2:

这道题假如用递归的话提交会显示以下的情况:

运行超时:

您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。

所以考虑用迭代解决。

代码实现:

public int JumpFloor(int target) {
 
    if(target == 1 || target == 2) {
 
    return target;
 
    }
 
    // 第一阶和第二阶考虑过了,初始当前台阶为第三阶,向后迭代
 
    // 思路:当前台阶的跳法总数=当前台阶后退一阶的台阶的跳法总数+当前台阶后退二阶的台阶的跳法总数
 
    int jumpSum = 0;// 当前台阶的跳法总数
 
    int jumpSumBackStep1 = 2;// 当前台阶后退一阶的台阶的跳法总数(初始值当前台阶是第3阶)
 
    int jumpSumBackStep2 = 1;// 当前台阶后退二阶的台阶的跳法总数(初始值当前台阶是第3阶)
 
     
 
    for(int i = 3; i <= target; i++) {
 
    jumpSum= jumpSumBackStep1 + jumpSumBackStep2;
 
    jumpSumBackStep2 = jumpSumBackStep1;// 后退一阶在下一次迭代变为后退两阶
 
    jumpSumBackStep1 = jumpSum;                   // 当前台阶在下一次迭代变为后退一阶
 
    }
 
    return jumpSum;
 
    }

思路3:

对于第n个台阶来说,只能从n-1或者是n-2的台阶跳上来。

所以,F(n) = F(n-1) + F(n-2)

斐波拉契数序列,初始条件

n=1:只能一种方法

n=2:两种方法

递归一下就可以了。

代码实现:

class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 0)
            return 0;
        else if(number == 1)
            return 1;
        else if(number == 2)
            return 2;
        else
            return jumpFloor(number-1) + jumpFloor(number-2);
    }
};

更多java实例,请继续关注本站了解吧!更多实例内容,可以分享给大家呢。

推荐阅读:

变态跳台阶(思路和实现)

调整数组顺序使奇数位于偶数前面(思路和实现)

二进制中1的个数(思路和实现)