代码随想录算法训练营第53天 | 1143、1035、53

1143. 最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例1：
输入：$text1="abcde",text2="ace"$
输出：$3$
示例2：
输入：$text1="abc",text2="abc"$
输出：$3$
示例3：
输入：$text1="abc",text2="def"$
输出：$0$

思路

1、确定dp数组：
dp[i][j]:长度玮[0,i-1]的字符串text1和长度[0,j-1]的字符串text2的最长公共子序列为dp[i][j]
2、确定递推公式
当text1[i-1]和text2[j-1]相同时，找到了一个公共元素，所以dp[i][j] = dp[i-1][j-1]+1
当text1[i-1]和text2[j-1]不同时，dp[i][j] = max(dp[i-1][j],dp[i][j-1)

解法

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for(int i = 1;i<=text1.length();i++){
            char char1 = text1.charAt(i-1);
            for(int j = 1;j<=text2.length();j++){
                char char2 = text2.charAt(j-1);
                if(char1 == char2){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

最近有点忙，这类题目也没有好好总结，只能是看答案理解，等过段时间再来好好总结一波

1035. 不相交的线

题目描述

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例1：
输入：$nums1=[1,4,2],nums2=[1,2,4]$
输出：$2$
示例2：
输入：$nums1=[2,5,1,2,5],nums2=[10,5,2,1,5,2]$
输出：$3$
示例3：
输入：$nums1=[1,3,7,1,7,5],nums2=[1,9,2,5,1]$
输出：$2$

思路

直线不能相交就说明在A中找到一个与B中相同的子序列，且这个子序列不能改变相对顺序，因为只要相对不改变，链接相同数字的直线就永远不会相交。
故而本题与上一题从本质上来说是完全相同的。

解法

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1+1][len2+1];
        for(int i = 1;i<=len1;i++){
            for(int j = 1;j <= len2;j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

怎么说呢，我开始是没看出来相同，看了答案之后才明白过来的。

53. 最大子序和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例1：
输入：$nums=[-2,1,-3,4,-1,2,1,-5,4]$
输出：$6$
示例2：
输入：$nums=[1]$
输出：$1$
示例3：
输入：$nums=[5,4,-1,7,8]$
输出：$23$

思路

1、确定dp数组
dp[i]表示包括下标i的最大连续子序列和为dp[i]
2、确定递推公式
从头开始计算和将nums[i]放入当前连续子序列和。

解法

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int res = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            res = res > dp[i] ? res : dp[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

好好看，好好学