刷题第1篇：青蛙跳

上周结束了javaweb的全部学习，下面开始学习框架了。发现框架的学习周期较长，不太好分享出来。恰巧现在开始刷题了，后面的话小白准备每周分享几道刷题过程中遇到的比较有意思的题目。提供一下解决思路，以及代码实现。

另外，小白自己建立了一个刷题的微信群，有时候自己刷题看不懂解析的话，可以发在群里，大家一起交流。自己遇到比较好的题目的话，也可以发在群里，大家一起来学习。主要还是面对2020年秋招的同学。感兴趣的同学，可以扫描下面的二维码进群。题目的主要来源是牛客和力扣上面的题目，欢迎各位小伙伴进群交流哟！

前言

这道题是群里面一位小伙伴在牛客上面刷到的题目，觉得蛮有意思，就发到群里了。小白觉得是一道很nice的题目，可以去探究一下。这次就当做分享吧！

一、青蛙跳

1、原题描述

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

2、解析

第一眼看到这个题目，觉得是一种排列组合的解法，不过想了半天也没有想明白怎么去解，后来看了一下题目解析。是使用斐波那契数列的思想进行解答。

（1）背后知识点介绍

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

（2）应用到题目

我们的青蛙每次都可以跳1级或者2级。当我们用逆向思维来看的时候，当前的每一级f(n),要么是从f(n-1)跳过来的，或者就是从f(n-2)跳过来的，只有这两种可能性。所以我们的最后一级f(n)=f(n-1)+f(n-2)。由此，我们就知道了如何计算整个最后的结果。

3、代码实现

代码实现有很多种实现方式，我们这里介绍一种。

public class Solution{
    public int JumpFloor(int target){
        if(target == 2){
            return 2;
        }
        if(target == 1){
            return 1;
        }
        if(target <= 0){
            return -1;
        }
        int a = 1;
        int b = 2;
        int c = 0;
        for(int i=3;i<=target;i++){
            c = a+b;
            a = b;
            b = c;
        }
        return c;
    }
}

二、青蛙跳变形

1、题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问使用n个2*1的小矩形无重叠的覆盖一个2*n的大矩形，总共有多少中方法？

2、题目分析

这道题目可以说和上面的青蛙跳是一模一样的。依旧是使用斐波那契数列进行计算。每一次的拼接都是有两种方法，横着拼接两个，或者竖着拼接一个。所以代码实现也与上面相同。

三、青蛙跳（变态版）

1、题目描述

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

2、题目分析

这道题依旧可以使用斐波那契数列思想。然而此时公式就不再是f(n) = f(n-1)+f(n-2) 了，由于每次的跳动的可能性变多了，而且跳法是从1~n。计算公式应该为：

f(n) = f(n-1)+f(n-2)+....+f(2)+f(1)

但是，这样的解法，效率将会非常低。类似于枚举。此时我们想，能不能换一种解题方法，于是新的思路产生了，如下所示： 青蛙有多种跳法，也就是说每一级都可能被跳上去，也可能不被跳上去，但是最后一级肯定会被跳上去，此时我们就可以得到最后的答案为：2^(n-1)种方案。

3、代码实现

此时的代码实现也有一个技巧。

public class Solution{
    public int JumpFloor(int target){
        return 1 << (target-1);
    }
}

可以使用位移运算，来提高整体的运算效率。

以上就是本周的刷题分享啦，内容不是很多，主要是精简一些比较有意思的题目，欢迎各位同学一起加入刷题小分队呀！