Letcode动态规划专题-困难

10. 正则表达式匹配

1.递归

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        char[] strings = str.toCharArray();
        char[] patterns = pattern.toCharArray();
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(strings, strIndex, patterns, patternIndex);
    }

    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        // 有效性检验：str到尾，pattern到尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        // pattern先到尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        // 模式下一位是*，且字符串当前位跟模式当前位匹配,分3种匹配模式；如不匹配，模式后移2位
        // 模式下一位为'*'
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            // 字符串当前位与模式当前位匹配
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                    || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                        // 模式后移2，视为x*匹配0个字符
                return matchCore(str, strIndex, pattern, patternIndex + 2)
                        // 视为模式匹配1个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2)
                        // *匹配1个，再匹配str中的下一个
                        || matchCore(str, strIndex + 1, pattern, patternIndex);
            // 字符串当前位与模式当前位不匹配
            } else {
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        // 模式下一位不是*，且字符串当前位跟模式当前位匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}
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
50
51
52
53
54
55
56

2.动态规划

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 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

42. 接雨水

1.传统方式-按照行的方式计算

整个思路就是，求第 i 层的水，遍历每个位置，如果当前的高度小于 i，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加 11。

如果求高度为 i 的水，首先用一个变量 temp 保存当前累积的水，初始化为 0。从左到右遍历墙的高度，遇到高度大于等于 i 的时候，开始更新 temp。更新原则是遇到高度小于 i 的就把 temp 加 1，遇到高度大于等于 i 的，就把 temp 加到最终的答案 ans 里，并且 temp 置零，然后继续循环。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        // 获取目前的最大值 
        int max = height[0];
        for(int i=1;i<height.length;i++){
            max = Math.max(max,height[i]);
        }

        // 外层的循环代表着层数 
        for(int i=1;i<=max;i++){
            boolean isFlag = false;
            int temp_sum = 0;
             // 内层的循环代表每个位置
            for(int j=0;j<height.length;j++){
                if(isFlag&&height[j]<i){
                    temp_sum++;
                }

                if(height[j]>=i){
                    sum += temp_sum;
                    isFlag = true;
                    temp_sum = 0;
                }

            }
        }

        return sum;
    }
}
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

2.传统方式-按照列的方式计算

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        int n =  height.length;
        
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for(int i=1;i<n-1;i++){
            
            //找出左边最高
            int max_left = 0;
            for(int j=0;j<=i-1;j++){
                max_left = Math.max(max_left,height[j]);
            }

            //找出右边最高
            int max_right = 0;
            for(int k=i+1;k<n;k++){
                max_right = Math.max(max_right,height[k]);
            }

            //找出两端较小的
            int min = Math.min(max_left,max_right);
           //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if(min>height[i]){           
                sum += min-height[i];
            }

        }
        return sum;
    }
}
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

3.动态规划
我们注意到，解法二中。对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。

首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）

对于 max_left我们其实可以这样求。

max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。

对于 max_right我们可以这样求。

max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。

这样，我们再利用解法二的算法，就不用在 for 循环里每次重新遍历一次求 max_left 和 max_right 了。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] max_left = new int[n];
        int[] max_right = new int[n];

        int sum =0;
        max_left[0] = height[0];
        for(int i=1;i<height.length;i++){
            max_left[i] = Math.max(max_left[i-1],height[i]);
        }


        max_right[height.length-1] = height[height.length-1];
        for(int j=height.length-2;j>=0;j--){
            max_right[j] = Math.max(max_right[j+1],height[j]);
        }

        for(int i=1;i<n-1;i++){
            int min = Math.min(max_left[i],max_right[i]);
            if(min-height[i]>0){
                sum+=(min-height[i]);
            }
        }

        return sum;

    }
}
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

接雨水的详细地址

72. 编辑距离

1.动态规划方程

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();

        // dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少
        int[][] dp= new int[n1+1][n2+1];

        for(int i=1;i<=n1;i++){
            dp[i][0] = dp[i-1][0]+1;
        }

        for(int j=1;j<=n2;j++){
            dp[0][j] = dp[0][j-1]+1;
        }

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                // 分为第i位字符和第j位字符相等与不等的情况

                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }

        return dp[n1][n2];

    }
}
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

参考链接

312. 戳气球
     

1.动态规划

class Solution {
    public int maxCoins(int[] nums) {
        // 感恩宇宙

        // 定義基礎數組
        int[] bases = new int[nums.length+2];
        bases[0] = 1;
        bases[nums.length+1] = 1;
        for(int i=1;i<=nums.length;i++){
            bases[i] = nums[i-1];
        }

        // 定義動態規劃數組
        int[][] dp = new int[nums.length+2][nums.length+2];
        // dp[i][j]表示从i到j戳气球的n    0 <= i <= n+1, j <= i+1
        dp[0][0] = 0;

        for(int i=nums.length;i>=0;i--){
            for(int j=i+1;j<nums.length+2;j++){
                for(int k=i+1;k<j;k++){
                    int sum = bases[i]*bases[j]*bases[k];
                    dp[i][j] = Math.max(dp[i][j],dp[i][k]+dp[k][j]+sum);
                }
            }
        }
        return dp[0][nums.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

动态规划相信答案地址

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

1.暴力破解
循环矩阵的每一个点，这道题参考 「84. 柱状图中最大的矩形」

class Solution {
    public int maximalRectangle(char[][] matrix) {
        // 首先第一步创造矩阵
        if(matrix==null||matrix[0].length==0){
            return 0;
        }

         // 填充矩阵
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] left = new int[m][n];

       // 填充数据 
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }

        int ret = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='0'){
                    continue;
                }

                // 接着计算面积
                int width = left[i][j];
                int area = width;
                for(int k=i-1;k>=0;k--){
                     width = Math.min(width,left[k][j]);
                     area = Math.max(area,width*(i-k+1));
                }

                ret = Math.max(ret,area);
            }
        }

        return ret;

    }
}
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

2.单调栈的解法

import java.util.*;
class Solution {
    public int maximalRectangle(char[][] matrix) {
        // 首先第一步创造矩阵
        if(matrix==null||matrix[0].length==0){
            return 0;
        }

         // 填充矩阵
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] left = new int[m][n];

       // 填充数据 
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }

        int ret = 0;
        // 对于每一列，使用基于柱状图的方法
        for(int j=0;j<n;j++){
            int[] down = new int[m];
            int[] up = new int[m];

            Stack<Integer> stack = new Stack<Integer>();
            for(int i=0;i<m;i++){
                while(!stack.isEmpty() && left[stack.peek()][j]>=left[i][j]){
                    stack.pop();
                }
                down[i] = stack.isEmpty()?-1:stack.peek();
                stack.push(i);
            }

            stack.clear();
            for(int i =m-1;i>=0;i--){
                while(!stack.isEmpty()&&left[stack.peek()][j]>=left[i][j]){
                    stack.pop();
                }
                up[i] = stack.isEmpty()?m:stack.peek();
                stack.push(i);
            }

             for(int i=0;i<m;i++){
                 int height = up[i] - down[i]-1;
                 int area = height*left[i][j];
                 ret = Math.max(ret,area);
                 }
        }
        return ret;

    }
}
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
50
51
52
53
54
55
56
57

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

124.二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return maxSum;
    }

    public int maxSum(TreeNode node){
        if(node==null){
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有最大值贡献值大于0的时候，才会选取 对应的子节点
        int leftValue = Math.max(maxSum(node.left),0);
        int rightValue = Math.max(maxSum(node.right),0);

        // 当前节点的值
        int priceNewPath = node.val + leftValue + rightValue;

        // 更新答案
        maxSum = Math.max(maxSum,priceNewPath);

        return node.val + Math.max(leftValue,rightValue);
    }
}
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

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

1.通过栈的方式

括号匹配的问题，最先想到的就是用栈解决。题目的要求是找到最长的有效括号子串，注意这里子串是连续的。

栈是后进先出的数据结构，首先要确定往栈里放什么东西。因为我们需要知道长度，因此往栈里放括号的下标是更合理的。具体逻辑是这样：

我们需要预先往括号里保存一个-1变量，用于后续使用；

每次遇到一个左括号，则把左括号的下标入栈；

每次遇到一个右括号，则先把栈顶的元素弹出，如果弹出后当前栈变成空栈，则需要将当前右括号所在位置入栈，否则需要根据当前栈顶元素和当前右括号下标计算当前有效括号子串的长度，并更新结果变量res。

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    maxLen = Math.max(maxLen,i-stack.peek());
                }
            }
        }
        return maxLen;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.动态规划方程

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for(int i=1;i<s.length;i++){
            if(s.charAt(i)==")"){
                if(s.charAt(i-1)=="("){
                    dp[i] = (i>=2?dp[i-2]:0)+2;
                } else if(i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i] = dp[i-1] +((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;
                }
                maxans = Math.max(maxans,dp[i]);
            }
        }
        return maxans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17