LeetCode动态规划

面试08.01 三步问题(跳台阶进阶版动态规划)

题目

分析

1. 原来只能一次性跳1/2节台阶，最后就是三个数字不断循环
2. 现在就相当于是四个数字变化，但是可能后面的数字比较大，因此每次计算时候b+c先进行取余之后再个d进行取余即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SanBu {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(waysToStep(n));
    }

    public static int waysToStep(int n) {
        int a=1;  //一个台阶一种走法  1
        int b=2;  //二个台阶两种走法  1+1 / 2
        int c=4;  //三个台阶四种走法  1+1+1 / 1+2 / 2+1 / 3
        int d=0;
        for(int i=1;i<n;i++){
            d=(a+(b+c)%1000000007)%1000000007;
            a=b;
            b=c;
            c=d;
        }
        return a;
    }

}

结果

面试08.02 迷路的机器人

题目

分析

代码

1
2


结果

面试08.11 硬币

题目

分析

代码

1
2


结果

面试17.16 按摩师/打家劫舍(a[0]+a[2]和a[1]对比)

题目

分析

1. 思路：(当前+前两个) ？(前一个)
2. 第一种o(n)：dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);
3. 第二种o(1): a b c三个变量递进循环

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class AnMoShi {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(massage(a));
    }

	//O（n）
    public static int massage(int[] nums) {
        int n = nums.length;  //数组长度
        if (n == 0) {
            return 0; //如果数组长度为0就返回0
        }
        if (n == 1) {
            return nums[0]; //如果只有一个就返回这个值
        }
        int[] dp = new int[n]; //存放结果
        dp[0] = nums[0];  //第一个值就是当前的第一个
        dp[1]=Math.max(nums[0], nums[1]); //判断是1开始还是2开始
        for(int i=2;i<n;i++){
            dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);
        }

        return dp[n-1];  //返回最后一个值
    }

	//O（1）
	public int massage(int[] nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            int c = Math.max(b, a + nums[i]);
            a = b;
            b = c;
        }
        return b;
    }

}

结果

面试17.23 最大黑方阵(纯劳力题不推荐)

题目

分析

参考LeetCode别人的代码思路，

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    int[][] matrix;
    int[] result=new int[]{0,0,0};
    public int[] findSquare(int[][] matrix) {
        this.matrix=matrix;
        if(matrix.length==0){
            return new int[]{};
        }
        for(int i=0;i<matrix.length-result[2];i++){
            for(int j=0;j<matrix.length-result[2];j++){
                if(matrix[i][j]==0){
                    int count=1;
                    while(count+i<matrix.length&&count+j<matrix.length
                    &&matrix[count+i][j]==0&&matrix[i][count+j]==0
                    ){
                        count++;
                    }
                    int actualLen=isBlackMatrix(i,j,count);
                    if(actualLen>result[2]){
                        result[0]=i;
                        result[1]=j;
                        result[2]=actualLen;
                    }
                }
            }
        }
        if(result[2]==0){
            return new int[]{};
        }
        return result;
    }
    public int isBlackMatrix(int i,int j,int size){//recursive check
        if(size==1){
            return size;
        }
        else{
            for(int x=0;x<size;x++){
                if(matrix[i+size-1][j+x]==0&&matrix[i+x][j+size-1]==0){
                    continue;
                }
                else{
                    int miniLen=isBlackMatrix(i,j,size-1);
                    return miniLen;
                }
            }
            return size;
        }
    }
}

结果

面试12 矩阵中的路径/单词搜索

题目

分析

代码

1
2


结果

面试42 连续子数组的最大和/最大子序列和(抓住sum大小)

题目

分析

参考大佬思路：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LianXuZiarr {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int r=input.nextInt();
        int[] a=new int[r];
        for(int i=0;i<r;i++) {
            a[i] = input.nextInt();
        }
        System.out.println(maxSubArray(a));
    }

    public static int maxSubArray(int[] nums) {
        int ans=nums[0]; //当前最大就是第一个数
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(sum>0){
                sum+=nums[i];  //sum>0就直接加进去现在的值
            }else{
                sum=nums[i];  //反之让当前值替换掉
            }
            ans=Math.max(ans,sum);  //ans相当于替换为一轮的最大值
        }
        return ans;
    }

}

结果

面试63 购票最大利润(双指针/动态规划)

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class GuPiao {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int r=input.nextInt();
        int[] a=new int[r];
        for(int i=0;i<r;i++) {
            a[i] = input.nextInt();
        }
        System.out.println(maxProfit(a));
    }

    public static int maxProfit(int[] prices) {
        if(prices.length == 0) {
            return 0;
        }
         int min=prices[0];
         int[] dp=new int[prices.length];
         for(int i=1;i<prices.length;i++){
             min=Math.min(prices[i-1],min);  //当前i所在值前面一个的最小值
             dp[i]=Math.max(dp[i-1],prices[i]-min); //前面的最优解和最小的收益差的比较
         }
         return dp[prices.length-1];
    }

}

结果

数组中的最长山脉(分两个动规解决)

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] nums=new int[]{2,1,4,7,3,2,5};  //可以设定数组 或者初始化
        System.out.println(longestMountain(nums));  //调用方法返回结果
    }

    public static int longestMountain(int[] a) {
        int res=0; //接住结果
        int len=a.length;  //获取数组长度
        int flag=3; //山脉的标准长度
        int[] left=new int[len];  //记录所有节点左边的最大扩展
            left[0]=0;  //第一位赋值0
        int[] right=new int[len];  //记录所有节点右边的最大扩展
            right[a.length-1]=0;  //最后一位赋值0
        //计算所有节点左边能扩展多少
        for(int i=1;i<a.length;i++){
            if(a[i]>a[i-1]){   // 2 8 这样的话说明可以扩展
                left[i]=left[i-1]+1; //前面的基础上+1
            }else{
                left[i]=0;
            }
        }
        //计算所有节点右边能扩展多少
        for(int i=a.length-2;i>=0;i--){
            if(a[i]>a[i+1]){   // 8 2 这样的话说明可以扩展
                right[i]=right[i+1]+1; //前面的基础上+1
            }else{
                right[i]=0;
            }
        }
        //最终找到最长的结果
        for(int i=0;i<len;i++){
            if(left[i]>0&&right[i]>0){  //一定要都有左右山脉
                res=Math.max(res,(left[i]+right[i]+1));  //求左右之和最大的
            }
        }
        return res;
    }

}

结果

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:LeetCode动态规划

文章作者:Larkkkkkkk

发布时间:2020年06月13日 - 16时31分

最后更新:2020年10月25日 - 11时05分

原始链接:https://larkkkkkkk.github.io/2020/06/13/LeetCode%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 面试08.01 三步问题(跳台阶进阶版动态规划)
    1. 1.1. 题目
    2. 1.2. 分析
    3. 1.3. 代码
    4. 1.4. 结果
  2. 2. 面试08.02 迷路的机器人
    1. 2.1. 题目
    2. 2.2. 分析
    3. 2.3. 代码
    4. 2.4. 结果
  3. 3. 面试08.11 硬币
    1. 3.1. 题目
    2. 3.2. 分析
    3. 3.3. 代码
    4. 3.4. 结果
  4. 4. 面试17.16 按摩师/打家劫舍(a[0]+a[2]和a[1]对比)
    1. 4.1. 题目
    2. 4.2. 分析
    3. 4.3. 代码
    4. 4.4. 结果
  5. 5. 面试17.23 最大黑方阵(纯劳力题不推荐)
    1. 5.1. 题目
    2. 5.2. 分析
    3. 5.3. 代码
    4. 5.4. 结果
  6. 6. 面试12 矩阵中的路径/单词搜索
    1. 6.1. 题目
    2. 6.2. 分析
    3. 6.3. 代码
    4. 6.4. 结果
  7. 7. 面试42 连续子数组的最大和/最大子序列和(抓住sum大小)
    1. 7.1. 题目
    2. 7.2. 分析
    3. 7.3. 代码
    4. 7.4. 结果
  8. 8. 面试63 购票最大利润(双指针/动态规划)
    1. 8.1. 题目
    2. 8.2. 分析
    3. 8.3. 代码
    4. 8.4. 结果
  9. 9. 数组中的最长山脉(分两个动规解决)
    1. 9.1. 题目
    2. 9.2. 分析
    3. 9.3. 代码
    4. 9.4. 结果
,