一、斐波那契数列大家都知道斐波那契数列现在要求输入一个正整数 n 请你输出斐波那契数列的第 n 项。数据范围1≤n≤40要求空间复杂度 O(1)时间复杂度 O(n)本题也有时间复杂度 O(logn)的解法import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param n int整型 * return int整型 */ public int Fibonacci (int n) { if(n 1 || n 2) return 1; return Fibonacci(n-1) Fibonacci(n-2); } }运行结果二、跳台阶一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法先后次序不同算不同的结果。数据范围1≤n≤40要求时间复杂度O(n) 空间复杂度 O(1)import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param number int整型 * return int整型 */ public int jumpFloor (int number) { if(number 2) return number; return jumpFloor(number - 1) jumpFloor(number - 2); } }运行结果三、最小花费爬楼梯给定一个整数数组 cost 其中 cost[i] 是从楼梯第ii个台阶向上爬需要支付的费用下标从0开始。一旦你支付此费用即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。数据范围数组长度满足 1≤n≤105 数组中的值满足 1≤costi≤104import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param cost int整型一维数组 * return int整型 */ public int minCostClimbingStairs (int[] cost) { // write code here int n cost.length; int[] dp new int[n 1]; dp[0] 0; dp[1] 0; for (int i 2; i n; i) { dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]); } return dp[n]; } }运行结果四、最长公共子序列给定两个字符串str1和str2输出两个字符串的最长公共子序列。如果最长公共子序列为空则返回-1。目前给出的数据仅仅会存在一个最长的公共子序列数据范围0≤∣str1∣,∣str2∣≤2000import java.util.*; public class Solution { public String LCS(String s1, String s2) { char[] a1 s1.toCharArray(), a2 s2.toCharArray(); int m a1.length, n a2.length; int[][] dp new int[m 1][n 1]; for (int i 0; i m; i) { for (int j 0; j n; j) { if (a1[i] a2[j]) { dp[i 1][j 1] dp[i][j] 1; } else { dp[i 1][j 1] Math.max(dp[i][j 1], dp[i 1][j]); } } } if (dp[m][n] 0) { return -1; } StringBuilder res new StringBuilder(); for (int i m, j n; i ! 0 j ! 0; ) { if (a1[i - 1] a2[j - 1]) { res.append(a1[i - 1]); i--; j--; } else if (dp[i - 1][j] dp[i][j - 1]) { i--; } else { j--; } } return res.reverse().toString(); } }运行结果五、最长公共子串给定两个字符串str1和str2,输出两个字符串的最长公共子串题目保证str1和str2的最长公共子串存在且唯一。import java.util.*; public class Solution { public String LCS(String str1, String str2) { char[] a1 str1.toCharArray(), a2 str2.toCharArray(); int m a1.length, n a2.length, cnt 0, from 0; int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { if (a1[i - 1] ! a2[j - 1]) { dp[i][j] 0; } else { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] cnt) { cnt dp[i][j]; from i - cnt; } } } } return new String(a1, from, cnt); } }运行结果六、不同路径的数目一个机器人在m×n大小的地图的左上角起点。机器人每次可以向下或向右移动。机器人要到达地图的右下角终点。可以有多少种不同的路径从起点走到终点import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param m int整型 * param n int整型 * return int整型 */ public int uniquePaths (int m, int n) { int dp[][] new int[m 1][n 1]; dp[0][1] 1; for (int i 1; i m 1; i) { for (int j 1; j n 1; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } return dp[m][n]; } }运行结果