斐波那契数列、矩阵覆盖、跳台阶、变态跳台阶-Java基础

た入场券 2022-01-14 07:55 201阅读 0赞

### 1、斐波那契数列 ###

## 题目描述 ##

求斐波那契数列的第 n 项，n <= 39。

[![45be9587-6069-4ab7-b9ac-840db1a53744.jpg][]][45be9587-6069-4ab7-b9ac-840db1a53744.jpg 1]

### 解题思路： ###

1）n=0,n=1的时候，f(n)等于本身，否则就等于前两项之和

2）解决方法：1、采用数组，计算保存所有序列的数，初始化f(1)=1;  i=2循环到i=n; f(i) = f(i-1) +f(i-2) ; 这样时间复杂度为： O(n)

2、只保存前两项数据，进行计算。int fbi=0, pre1 = 0, pre2=1; i=2循环到i=n; fbi = pre1+pre2; pre1 = pre2; pre2 = fbi;   这样时间复杂度为： O(1).  减少了开销。

剑指offer的代码：

> 1.  public class Solution \{
> 2.      public int Fibonacci(int n) \{
> 3.           if(n<=1) return n;
> 4.              int array\[\] = new int \[n+1\];
> 5.              array\[0\]=0;
> 6.              array\[1\]=1;
> 7.              int result=0;
> 8.              for(int i=2;i<=n;i++)\{
> 9.                  array\[i\] = array\[i-1\]+array\[i-2\];
> 10.             \}
> 11.             return array\[n\];
> 12.         
> 13.     \}
> 14. \}

本机测试代码：

> 1.  public class testFibonacci101 \{
> 2.      /\*\*
> 3.       \* @param ycy
> 4.       \*/
> 5.      public static int searchFibonacci1(int n)\{    //原始得斐波那契数，采用数组存储所有的斐波那契数，直到n，返回需要的数。复杂度降低到O(n)
> 6.          if(n <= 1)\{
> 7.              return n;
> 8.          \}
> 9.          int fibonacci\[\] = new int\[n+1\];
> 10.         fibonacci\[0\] = 0;
> 11.         fibonacci\[1\] = 1;
> 12.         for(int i=2;i<=n;i++)\{
> 13.             fibonacci\[i\] = fibonacci\[i-1\] + fibonacci\[i-2\];
> 14.         \}
> 15.         return fibonacci\[n\];
> 16.     \}
> 17.     public static int searchFibonacci2(int n)\{     //第i项，只与第i-1项和i-2项有关系，所以只保存前两项，进行求解，这样复杂度降低到O(1)
> 18.         if(n <= 1)\{
> 19.             return n;
> 20.         \}
> 21.         int fibonacci = 0,fibpre1 = 0,fibpre2 = 1;
> 22.         for(int i=2;i<=n;i++)\{
> 23.             fibonacci = fibpre1 + fibpre2;
> 24.             fibpre1 = fibpre2;
> 25.             fibpre2 = fibonacci;
> 26.         \}
> 27.         return fibonacci;
> 28.     \}
> 29.     public static void main(String\[\] args) \{
> 30.         // TODO Auto-generated method stub
> 31.         System.out.println(searchFibonacci1(45));
> 32.         System.out.println(searchFibonacci2(45));
> 33.     \}
> 34. \}

### 2、矩阵覆盖 ###

## 题目描述 ##

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

## 解题思路 ##

当 n 为 1 时，只有一种覆盖方法；

当 n 为 2 时，有两种覆盖方法；

要覆盖 2\*n 的大矩形，可以先覆盖 2\*1 的矩形，再覆盖 2\*(n-1) 的矩形；或者先覆盖 2\*2 的矩形，再覆盖 2\*(n-2) 的矩形。而覆盖 2\*(n-1) 和 2\*(n-2) 的矩形可以看成子问题。该问题的递推公式如下：

![20190615153726745.png][]

剑指offer在线测试：

> 1.  public class Solution \{
> 2.      public int RectCover(int target) \{
> 3.        //f(0)=0;f(1)=1;f(2)=2;f(3)=3;f(4)=5
> 4.          if(target<=3) return target;
> 5.          int array\[\]= new int\[target+1\];
> 6.          array\[0\]=0;array\[1\]=1;array\[2\]=2;array\[3\]=3;
> 7.          for(int i=4;i<=target;i++)
> 8.              array\[i\] = array\[i-1\] + array\[i-2\];
> 9.         return array\[target\];
> 10.     \}
> 11. \}

本机测试：

> 1.  public class testMatrixCover102 \{
> 2.      /\*\*
> 3.       \* @param ycy
> 4.       \* 题目描述:我们可以用 2\*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2\*1 的小矩形无重叠地覆盖一个 2\*n 的大矩形，总共有多少种方法？
> 5.       \* 解决思路：1)经过推理可以发现，f(1)=1, f(2)=2, f(3)=3, f(4)=5  所以  f(1)=1  f(2)=2  f(n)=f(n-1)+f(n-2)
> 6.       \*和斐波那契数一种解决思路
> 7.       \*/
> 8.      public static int matrixCover(int n)\{
> 9.          if(n<=2)\{
> 10.             return n;
> 11.         \}
> 12.         int fn = 0, pre1 = 1, pre2 = 2;
> 13.         for(int i=3;i<=n;i++)\{
> 14.             fn = pre1 + pre2;
> 15.             pre1 = pre2;
> 16.             pre2 = fn;
> 17.         \}
> 18.             
> 19.         return fn;
> 20.     \}
> 21.     public static void main(String\[\] args) \{
> 22.         // TODO Auto-generated method stub
> 23.         System.out.print(matrixCover(4));
> 24.     \}
> 25. \}

### 3、跳台阶 ###

## 题目描述 ##

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

## 解题思路 ##

当 n = 1 时，只有一种跳法；

当 n = 2 时，有两种跳法；

跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题，该问题的递推公式为：

![20190615153726745.png][]

剑指offer代码：

> 1.  public class Solution \{
> 2.      public int JumpFloor(int target) \{
> 3.          if(target<=2) return target;
> 4.          int array\[\] = new int\[target+1\];
> 5.          array\[0\]=0;
> 6.          array\[1\]=1;
> 7.          array\[2\]=2;
> 8.          for(int i=3;i<=target;i++)\{
> 9.              array\[i\] = array\[i-1\] + array\[i-2\];
> 10.         \}
> 11.         return array\[target\];
> 12.     \}
> 13. \}

本地测试代码如下：

> 1.  public class jumpStep103 \{
> 2.      /\*\*
> 3.       \* @param ycy
> 4.       \* 题目描述：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
> 5.       \* 解决思路：f(1)=1, f(2)=2,f(3)=3,f(4)=5   f(i)=f(i-1) + f(i-2)
> 6.       \*/
> 7.      public static int jumpStep(int n)\{
> 8.          if(n<=2)\{
> 9.              return n;
> 10.         \}
> 11.         int js = 0, jspre1 = 1, jspre2 = 2;
> 12.         for(int i=3;i<=n;i++)\{
> 13.             js = jspre1 + jspre2;
> 14.             jspre1 = jspre2;
> 15.             jspre2 = js;
> 16.         \}
> 17.         return js;
> 18.     \}
> 19.     public static void main(String\[\] args) \{
> 20.         // TODO Auto-generated method stub
> 21.         System.out.print(jumpStep(5));
> 22.     \}
> 23. \}

### 4、变态跳台阶 ###

## 题目描述 ##

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

## 解题思路 ##

1) f(n-1) = f(n-2) + f(n-3) + ... + f(0) f(n) = f(n-1) + f(n-2) + ... + f(0)所以  
         采取嵌套循环，每次i=1循环到i<n，嵌套j=0到j<i，一直进行dp\[i\] += dp\[j\]  
2) f(n-1) = f(n-2) + f(n-3) + ... + f(0)与f(n) = f(n-1) + f(n-2) + ... + f(0)进行推导  
         f(n) - f(n-1) = f(n-1)   所以f(n) = 2\*f(n-1)； 所以dp = 1,dppre = 1; i=2循环到i<=n; dp = 2\*dppre; dppre = dp;

剑指offer代码：

> 1.  public class Solution \{
> 2.      public int JumpFloorII(int target) \{
> 3.     //f(0)=0,f(1)=1,f(2)=2;f(3)=4;f(4)=8 f(n)= 2\*f(n-1)
> 4.          int array\[\] = new int\[target+1\];
> 5.          if(target<=2) return target;
> 6.          array\[0\]=0; array\[1\]=1; array\[2\]=2;
> 7.          for(int i=3;i<=target;i++)
> 8.              array\[i\] = 2\*array\[i-1\];
> 9.           return array\[target\];
> 10.     \}
> 11. \}

本地代码：

> 1.  import java.util.Arrays;
> 2.  public class strageJumpStep104 \{
> 3.      /\*\*
> 4.       \* @param ycy
> 5.       \* 题目描述：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
> 6.       \* 解题思路:
> 7.       \* 1)f(n-1) = f(n-2) + f(n-3) + ... + f(0) f(n) = f(n-1) + f(n-2) + ... + f(0)所以
> 8.       \*   采取嵌套循环，每次i=1循环到i<n，嵌套j=0到j<i，一直进行dp\[i\] += dp\[j\]
> 9.       \* 2)f(n-1) = f(n-2) + f(n-3) + ... + f(0)与f(n) = f(n-1) + f(n-2) + ... + f(0)进行推导
> 10.      \*   f(n) - f(n-1) = f(n-1)   所以f(n) = 2\*f(n-1)； 所以dp = 1,dppre = 1; i=2循环到i<=n; dp = 2\*dppre; dppre = dp;
> 11.      \*/
> 12.     public static int strageJumpStep1(int n)\{  //f(n-1) = f(n-2) + f(n-3) + ... + f(0)  
> 13.         int dp\[\] = new int\[n\];                 //f(n) = f(n-1) + f(n-2) + ... + f(0)
> 14.         Arrays.fill(dp, 1);                   
> 15.         for(int i=1;i<n;i++)\{
> 16.             for(int j=0;j<i;j++)\{
> 17.                 dp\[i\] += dp\[j\];
> 18.             \}
> 19.         \}
> 20.         return dp\[n-1\];
> 21.     \}
> 22.     public static int strageJumpStep2(int n)\{  //
> 23.         int dp = 1,dppre = 1;
> 24.         for(int i=2;i<=n;i++)\{
> 25.             dp = 2\*dppre;
> 26.             dppre = dp;
> 27.         \}
> 28.         return dp;
> 29.     \}
> 30.     public static void main(String\[\] args) \{
> 31.         // TODO Auto-generated method stub
> 32.         System.out.println(strageJumpStep1(8));
> 33.         System.out.println(strageJumpStep2(8));
> 34.     \}
> 35. \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[45be9587-6069-4ab7-b9ac-840db1a53744.jpg]: https://github.com/CyC2018/CS-Notes/raw/master/notes/pics/45be9587-6069-4ab7-b9ac-840db1a53744.jpg
[45be9587-6069-4ab7-b9ac-840db1a53744.jpg 1]: https://github.com/CyC2018/CS-Notes/blob/master/notes/pics/45be9587-6069-4ab7-b9ac-840db1a53744.jpg
[20190615153726745.png]: /images/20220114/0efd4fa3c9fa40eda24b6c47b7258b65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20220114/e4fd7e2716d24e61994a117938cc8e96.png