day53【子序列】1143.最长公共子序列 1035.不相交的线 53.最大子序和

2023-11-03 11:36

本文主要是介绍day53【子序列】1143.最长公共子序列 1035.不相交的线 53.最大子序和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1143. 最长公共子序列
  • 1035.不相交的线
  • 53. 最大子序和

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 。
    
  • 思路
    dp数组代表第i-1和j-1为结尾的最长公共子序列的长度。
    所以在遍历中,for的条件要写从1开始遍历,循环条件为<=length;循环体中,如果当前字母相同,那结果就是前一个状态的dp+1;如果当前字母不是相同的,那结果就看前一个i和当前j / 前一个j和当前i中的最大值。

class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] char1 = text1.toCharArray();char[] char2 = text2.toCharArray();int[][] dp = new int[char1.length+1][char2.length+1];int res = 0;for(int i = 1; i <= char1.length; i++) {for(int j = 1; j <= char2.length; j++) {if(char1[i-1] == char2[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]);}res = Math.max(res, dp[i][j]);}}return res;}
}

1035.不相交的线

  • 力扣题目链接

  • 代码随想录讲解

  • 题意:在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

    现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:

    nums1[i] == nums2[j]
    且绘制的直线不与任何其他连线(非水平线)相交。
    请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

    以这种方法绘制线条,并返回可以绘制的最大连线数。
    在这里插入图片描述
    示例 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
    
  • 思路:和1143是一样的,求最长公共子序列即可。按照顺序相等的就不会出现线相交的情况。

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int res = 0;int[][] dp = new int[nums1.length+1][nums2.length+1];for(int i = 1; i <= nums1.length; i++) {for(int j = 1; j <= nums2.length; 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]);}res = Math.max(res, dp[i][j]);}}return res;}
}

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
    
  • 贪心算法
    局部最优:当前的连续和为负数的时候就要立刻放弃,此时从下一个元素开始重新计算连续和。因为负数加上下一个元素,连续和只会越来越小。
    全局最优:选取最大的连续和

class Solution {public int maxSubArray(int[] nums) {//动态规划int count = 0;int res = Integer.MIN_VALUE;for(int i = 0; i < nums.length; i++) {count += nums[i];res = Math.max(count, res);if(count < 0) { //如果此时的连续和为负数了,那就从下一个元素从新计算。上一个开头的元素的最大连续和已经保存在res中了,就看后面有没有比这个更大的值了。count = 0;}}return res;}
}
  • 动态规划
    dp由两个方向推来,要么是前一种状态+当前元素,要么是从当前元素开始计算连续子序和,这两种情况选最大的
class Solution {public int maxSubArray(int[] nums) {//以i结尾的最大连续子数组的最大和int[] dp = new int[nums.length+1];dp[0] = nums[0];int res = dp[0];for(int i = 1; i < nums.length; i++) {//dp要么是从前一个状态推过来的,要么是自己从头开始算dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);res = Math.max(res, dp[i]);}return res;}
}

这篇关于day53【子序列】1143.最长公共子序列 1035.不相交的线 53.最大子序和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/337891

相关文章

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta