1143.最长公共子序列
给定两个字符串 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 。
提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
思路：
这道题跟最长重复子序列有点相像，但是它跟最长重复子序列不同的是，它不需要连续，它可以隔一个再算下一个，所以我们不仅要判断连续的情况还需要判断不同的情况，相同时我们要在前一个上加上1，不同时我们要找出最大值来使其子序列最长，最终返回答案即可。
解答：
int longestCommonSubsequence(char* text1, char* text2) {
int a1 = strlen(text1);
int a2 = strlen(text2);
int** dp = calloc(a1+1,sizeof(int*));
for(int i = 0;i < a1+1;i++)
{
dp[i] = calloc(a2+1,sizeof(int));
}
for(int i = 1;i <= a1;i++)
{
for(int j = 1;j <= a2;j++)
{
if(text1[i-1] == text2[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
{
dp[i][j] = fmax(dp[i-1][j],dp[i][j-1]);
}
}
}
int max = dp[0][0];
for(int i = 0;i <= a1;i++)
{
for(int j = 0;j <= a2;j++)
{
if(max < dp[i][j])
{
max = dp[i][j];
}
}
}
return dp[a1][a2];
}
1035.不相交的线
在两条独立的水平线上按给定的顺序写下 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
思路：
这道题跟上面的题目一样，只不过换了一种说法，相等且不能相交就是上面的求最大公共子序列，后面的做法跟上面的一样，很轻松求出答案。
解答：
int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int** dp = calloc(nums1Size+1,sizeof(int*));
for(int i = 0;i < nums1Size+1;i++)
{
dp[i] = calloc(nums2Size+1,sizeof(int));
}
for(int i = 1;i <= nums1Size;i++)
{
for(int j = 1;j <= nums2Size;j++)
{
if(nums1[i-1] == nums2[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
{
dp[i][j] = fmax(dp[i-1][j],dp[i][j-1]);
}
}
}
int max = dp[0][0];
for(int i = 0;i <= nums1Size;i++)
{
for(int j = 0;j <= nums2Size;j++)
{
if(max < dp[i][j])
{
max = dp[i][j];
}
}
}
return max;
}
53.最大子数组和
给你一个整数数组 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
思路：
这道题我们用动态规划做的话，我们要设置dp[i]为前i个中的最大子序列之和，而找到最大子序列之和我们需要看是这个元素大还是前面的子序列之和加上这个元素大，最后返回最大值就行了。
解答：
int maxSubArray(int* nums, int numsSize) {
if(numsSize == 0)return 0;
int* dp = calloc(numsSize+1,sizeof(int));
dp[0] = nums[0];
int result = dp[0];
for(int i = 1;i < numsSize;i++)
{
dp[i] = fmax(dp[i-1]+nums[i],nums[i]);
if(result < dp[i])
{
result = dp[i];
}
}
return result;
}
392.判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
思路：
这道题要我们寻找s是否为t的子序列，所以我们要进行判断，这里我设置了一个用来索引的变量，和一个用来判断是否是子集的变量，这个索引的变量是用来防止t又重新从零开始遍历导致不满足题目条件，如果找到有相同字符，判断变量变为true，否则就为false，最后很简单就能找到答案。
解答：
bool isSubsequence(char* s, char* t) {
int index = 0;
for(int i = 0;i < strlen(s);i++)
{
bool find = false;
for(int j = index;j < strlen(t);j++)
{
if(s[i] == t[j])
{
index = j+1;
find = true;
break;
}
}
if(!find)
{
return false;
}
}
return true;
}
反思
今天的题目适中，不是特别难，但是有一些地方还是要多多去理解。
标签：示例,int,代码,第四十四,随想录,字符串,序列,nums1,dp From： https://blog.csdn.net/2301_80630236/article/details/144118889