leetcode之动态规划的面试题
1.连续子数组的最大和
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
数据范围: 1 <= n <= 10^51<=n<=105-100 <= a[i] <= 100?100<=a[i]<=100
要求:时间复杂度为 O(n)，空间复杂度为 O(n)
进阶:时间复杂度为 O(n)，空间复杂度为 O(1)
有以下几种方法：
方法一：暴力方法，从分别以数组的每个节点为起点，计算出从该起点到末尾的最大值；
1 public class Solution { 2 public int FindGreatestSumOfSubArray(int[] array) { 3 int max = Integer.MIN_VALUE; 4 for(int i = 0; i < array.length; i++){ 5 int sum = lengthOfsubArray(array, i); 6 if(max < sum){ 7 max = sum; 8 } 9 } 10 return max; 11 } 12 13 public int lengthOfsubArray(int[] arr, int startNum){ 14 int max = Integer.MIN_VALUE; 15 int sum = 0; 16 for(int i = startNum; i < arr.length; i++){ 17 sum += arr[i]; 18 if(sum > max){ 19 max = sum; 20 } 21 } 22 return max; 23 } 24 }
该方法可能会超时；
方法二：采用动态规划的方法，创建dp[]数组；
dp[i] = Math.max(dp[i-1]+array[i], array[i]);
1 public class Solution { 2 public int FindGreatestSumOfSubArray(int[] array) { 3 int length = array.length; 4 int[] dp = new int[length]; 5 int max = array[0]; 6 dp[0] = array[0]; 7 for(int i = 1; i < length; i++){ 8 if(dp[i-1] + array[i] > array[i]){ 9 dp[i] = dp[i-1]+array[i]; 10 }else{ 11 dp[i]=array[i]; 12 } 13 if(max<dp[i]){ 14 max=dp[i]; 15 } 16 } 17 return max; 18 } 19 }
2.连续子数组的最大和(二)
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。 1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组 2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个 3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组 4.返回的数组不计入空间复杂度计算 数据范围: 1<=n<=10^51<=n<=105-100 <= a[i] <= 100?100<=a[i]<=100
要求:时间复杂度O(n)，空间复杂度O(n)
进阶:时间复杂度O(n)，空间复杂度O(1)
有以下几种方法； 方法一：采用暴力方法，两次循环获取连续子数组最大和；
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindGreatestSumOfSubArray (int[] array) {
int max=Integer.MIN_VALUE;
int sum=0;
int startNum=0;
int endNum=0;
int length=0;
for(int i=0;imax){
max=sum;
startNum=i;
endNum=j;
length=endNum-startNum+1;
}else if(sum == max && length
方法二：方法和上题一样，采用动态规划的算法；
1 import java.util.*;
2
3
4 public class Solution {
5 /**
6 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
7 *
8 *
9 * @param array int整型一维数组
10 * @return int整型一维数组
11 */
12 public int[] FindGreatestSumOfSubArray (int[] array) {
13 int[] dp = new int[array.length];
14 dp[0] = array[0];
15 int maxEndIndex=0;
16 int max=dp[0];
17 ArrayList maxEndIndexArr = new ArrayList<>();
18 for(int i=1;i){
19 if(dp[i-1]+array[i]>array[i]){
20 dp[i]=dp[i-1]+array[i];
21 }else{
22 dp[i]=array[i];
23 }
24 if(max<=dp[i]){
25 max=dp[i];
26 maxEndIndex=i;
27 }
28 }
29 //收集所有的最大值的末尾索引
30 for(int i=0; i<=maxEndIndex;i++){
31 if(dp[i] == max){
32 maxEndIndexArr.add(i);
33 }
34 }
35 int startIndex = 0;
36 int maxLength = 0;
37 for(Integer m:maxEndIndexArr){
38 int tempMax=max;
39 int tempStartIndex=m;
40 for(int i=m;i>=0;i--){
41 tempMax = tempMax - array[i];
42 if(tempMax==0){
43 tempStartIndex=i;
44 }
45 }
46 if(maxLength){
47 maxLength=m-tempStartIndex+1;
48 startIndex=tempStartIndex;
49 maxEndIndex=m;
50 }
51 }
52 int[] result = new int[maxEndIndex-startIndex+1];
53 for(int i=0;i){
54 result[i]=array[i+startIndex];
55 }
56 return result;
57 }
58 }
3. 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围：0≤n≤40
要求：时间复杂度：O(n) ，空间复杂度：O(1)
有以下几种求解方法：
方法一：递归方法；
public class Solution {
public int jumpFloor(int target) {
if(target==1){
return 1;
}else if(target==2){
return 2;
}else{
return jumpFloor(target-1) + jumpFloor(target-2);
}
}
}
方法二：动态规划的方式，创建数组dp[]，递推公式如下：
dp[1]=1,dp[2]=2;
dp[n]=dp[n-1]+dp[n-2];
public class Solution {
public int jumpFloor(int target) {
if(target==1||target==2){
return target;
}
int[] dp = new int[target+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=target;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[target];
}
}
4.斐波那契数列
和3的跳台阶一直，代码基本相似，都可以利用动态规划和递归的方式进行编写；
5.正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
数据范围:
(1).str 可能为空，且只包含从 a-z 的小写字母。
(2).pattern 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
(3).1 <= str.length <= 20
(4).1 <= pattern.length <= 30
要求：空间复杂度 O(1)，时间复杂度 O(n)