Day53代码随想录
1143.最长公共子序列
1.题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
2.解题思路及代码实现
同时也是二维dp，但是要考虑的是递推公式，
if (text1.charAt(i-1)==text2.charAt(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]);
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] dp = new int[n+1][m+1];
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < m+1; j++) {
if (text1.charAt(i-1)==text2.charAt(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[n][m];
}
}
1035.不相交的线
1.题目描述
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=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
2.解题思路及代码实现
本题就是思路跟最长公共子序列一个思路
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[][] dp = new int[n+1][m+1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m+1; 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[n][m];
}
}
53.最大子数组和
1.题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
2.解题思路及代码实现
本题之前用贪心解决过，所以这题用动态规划的思路如下，定义dp数组及下标含义
dp[i]是指以nums[i]为结尾的最大子数组和，那么递推公式为dp[i] = Math.max(dp[i-1]+nums[i],nums[i])
初始化dp[0]=nums[0]
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int res = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i]+nums[i],dp[i-1]+nums[i]);
res = Math.max(res,dp[i]);
}
return res;
}
}
