第九章 动态规划 part14 1143. 最长公共子序列 1035. 不相交的线 53. 最大子序和
第五十六天| 第九章 动态规划 part14 1143. 最长公共子序列 1035. 不相交的线 53. 最大子序和
一、1143. 最长公共子序列
-
题目链接:
-
题目介绍:
-
思路:
-
本题和“最长重复子数组”区别在于**这里不要求是连续的了,但要有相对顺序**,即:“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
-
dp五部曲:
-
(1)确定dp数组及下标含义:
-
dp[i][j]:表示的是以下标i-1为结尾的text1和以下标j-1为结尾的text2的最长公共子序列的长度
-
-
(2)确定递推公式:
-
本题不再要求连续,因此dp[i][j]可以由三个方向推出
-
如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
-
-
-
(3)初始化dp数组:
-
根据dp数组的含义,char1[0, i-1]和空数组的公共子序列长度为0;同理,char2[0, j-1]和空数组的公共子序列长度也为0。因此,dp[i][0] = 0,dp[0][j] = 0。其他位置在后续均可以覆盖,因此都初始化为0。
-
-
(4)确定遍历顺序:
- 根据递推公式可知是正序
-
-
和重复子数组(连续公共子序列)不同,本题的最终结果是在二维dp数组的最右下角,因为根据递推公式,如果不相同还是会根据左边的和上边的推导出来。
-
-
代码:
class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] char1 = text1.toCharArray();char[] char2 = text2.toCharArray();// (1)确定dp数组及下标含义// dp[i][j]:表示的是以下标i-1为结尾的text1和以下标j-1为结尾的text2的最长公共子序列的长度int[][] dp = new int[char1.length + 1][char2.length + 1];// (3)初始化dp数组// 根据dp数组的含义,char1[0, i-1]和空数组的公共子序列长度为0;同理,char2[0, j-1]和空数组的公共子序列长度也为0。因此,dp[i][0] = 0,dp[0][j] = 0。其他位置在后续均可以覆盖,因此都初始化为0。// (4)确定遍历顺序// 根据递推公式可知是正序for (int i = 1; i <= char1.length; i++) {for (int j = 1; j <= char2.length; j++) {// (2)确定递推公式// 本题不再要求连续,因此dp[i][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]);}}}// 和重复子数组(连续公共子序列)不同,本题的最终结果是在二维dp数组的最右下角,因为根据递推公式,如果不相同还是会根据左边的和上边的推导出来。return dp[char1.length][char2.length];}
}
二、1035. 不相交的线
-
题目链接:https://leetcode.cn/problems/uncrossed-lines/
-
题目介绍:
-
在两条独立的水平线上按给定的顺序写下
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 的直线相交。
-
-
思路:
- 套壳的“最长公共子序列”
- 思路和解法与上道题目是一样的
-
代码:
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {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]);}}}return dp[nums1.length][nums2.length];}
}
三、53. 最大子序和
-
题目链接:https://leetcode.cn/problems/maximum-subarray
-
题目介绍:
-
相关企业
给你一个整数数组
nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
-
-
思路:
-
dp五部曲:
-
(1)确定dp数组及下标含义
-
dp[i]:表示的是以nums[i]为结尾的最大连续子序列之和
-
-
(2)确定递推公式
-
dp[i]只能由两个方向推出来:一个是:因为是连续的所以是dp[i-1] + nums[i]另一个是:当前nums[i]
-
-
(3)初始化dp数组
-
dp[0]:表示的是以nums[0]为结尾的最大连续子序列的和,所以dp[0] = nums[0]
-
-
(4)遍历顺序:正序
-
-
-
代码:
class Solution {public int maxSubArray(int[] nums) {if (nums == null || nums.length == 0) return 0;int result = nums[0];// (1)确定dp数组及下标含义// dp[i]:表示的是以nums[i]为结尾的最大连续子序列之和int[] dp = new int[nums.length];// (3)初始化dp数组// dp[0]:表示的是以nums[0]为结尾的最大连续子序列的和,所以dp[0] = nums[0].dp[0] = nums[0];// (4)遍历顺序:正序for (int i = 1; i < nums.length; i++) {// (2)确定递推公式// dp[i]只能由两个方向推出来:// 一个是:因为是连续的所以是dp[i-1] + nums[i]// 另一个是:当前nums[i]dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);if (dp[i] > result) result = dp[i];}return result;}
}
总结:
- 子数组:求解的就是**连续子序列**
- 子序列:没有强调的连续,只要是子序列即可
相关文章:

第九章 动态规划 part14 1143. 最长公共子序列 1035. 不相交的线 53. 最大子序和
第五十六天| 第九章 动态规划 part14 1143. 最长公共子序列 1035. 不相交的线 53. 最大子序和 一、1143. 最长公共子序列 题目链接: 题目介绍: 思路: 本题和“最长重复子数组”区别在于**这里不要求是连续的了,但要有相对顺序*…...

腾讯云服务器南京地域详细介绍、测试IP和Ping值测速
腾讯云服务器南京地域怎么样?南京地域很不错,正好处于中间的位置,南方北方用户均可以选择,网络延迟更低速度更快,并且目前南京地域有活动,南京地域可用区可选南京一区、南京二区和南京三区,腾讯…...

理解CSS的层叠性和继承性
CSS的层叠性(cascading)指的是在同一元素上应用多个样式时,不同样式之间的优先级别以及如何进行组合和冲突解决的规则。具体来说,CSS采用的是“选择器优先级”规则来判断哪个样式优先级更高,如果多个样式的优先级相同&…...

OSI体系结构和TCP/IP体系结构
在第一章( 计网第一章 )的时候,曾经提到过OSI体系结构和TCP/IP体系结构,并对它们进行了简单的对比。这篇博客在其基础上进行更深层次的理解。 一.OSI体系结构: 通信子网: 计算机网络在逻辑功能上可以分为…...

侯捷 C++ STL标准库和泛型编程 —— 8 适配器
8 适配器 适配器 Adapter 只是一个小变化,比如改个接口,函数名称等等其出现在三个地方:仿函数适配器,迭代器适配器,容器适配器可以使用继承 / 复合的两种方式实现,STL中都用复合 其思想就是将该记的东西记…...

每日一题 416 分割等和子集(01背包)
题目 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] …...

U盘插上就显示让格式化是坏了吗?
U盘以其体积小巧、存储容量大、读写速度快的特点,在各种工作和个人使用场合中得到了广泛应用,因此深得用户好评。然而,在日常使用U盘的过程中,经常会遇到一些问题和挑战。今天,我将为大家详细解释U盘出现要求格式化的现…...

分布式应用程序协调服务 ZooKeeper 详解
目录 1、ZooKeeper简介 2、ZooKeeper的使用场景 3、ZooKeeper设计目的 4、ZooKeeper数据模型 5、ZooKeeper几个重要概念 5.1、ZooKeeper Session 5.2、ZooKeeper Watch 5.3、Consistency Guarantees 6、ZooKeeper的工作原理 6.1、Leader Election 6.2、Leader工作流…...

Anniversary party(树形dp 基础题)
1.题目大意 There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In …...

Junit的常用操作
注:本篇文章讲解的是junit5 目录 Juint是什么 Juint需要导入的依赖 Juint常用注解 Junit执行顺序 参数化 断言 测试套件 Juint是什么 Juint 是 Java 的一个单元测试框架. 也是回归测试框架. 使用 Junit 能让我们快速的完成单元测试。 注意:Junit 测试也是程序…...

Elasticsearch安装并使用Postman访问
Elasticsearch,一个强大的开源搜索和分析引擎,已经在全球范围内被广泛应用于各种场景,包括网站搜索、日志分析、实时应用等。由于其强大的功能和灵活性,Elasticsearch 已经成为大数据处理的重要工具。然而,对于许多初次…...

Pytorch深度学习训练模型保存问题,找不到保存路径
执行torch.save(net.state_dict(), save_path_pth)报错: RuntimeError: Parent directory D:\xxxxxxxxxxx\weights does not exist. 将文件路径的中文改成全英文就可以了。 注意:这个代码在torch1.7版本无报错,但是在1.13.1版本报错。在linu…...

数据结构与算法之堆: Leetcode 23. 合并 K 个升序链表 (Typescript版)
合并 K 个升序链表 https://leetcode.cn/problems/merge-k-sorted-lists/ 描述 给你一个链表数组,每个链表都已经按升序排列请你将所有链表合并到一个升序链表中,返回合并后的链表 示例 1 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出&…...

代码随想录算法训练营第五十七天 | 392.判断子序列 115.不同的子序列
1. 判断子序列 392. 判断子序列 - 力扣(LeetCode) dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度。 class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j] 表示…...

Kafka日志索引详解以及生产常见问题分析与总结
文章目录 1、Kafka的Log日志梳理1.1、Topic下的消息是如何存储的?1.1.1、 log文件追加记录所有消息1.1.2、 index和timeindex加速读取log消息日志。 1.2、文件清理机制1.2.1、如何判断哪些日志文件过期了1.2.2、过期的日志文件如何处理 1.3、Kafka的文件高效读写机制…...

vue中 css scoped原理
Vue中css的逻辑是先放子组件,然后放父组件,所以同样的css类名,子组件会被父组件覆盖 html 如下 子被父覆盖 scoped是通过给组件加hash值,锁定组件。 父子组件均scoped的情况下,子仍会覆盖 还是被覆盖了 如何避免被…...

tf.compat.v1.global_variables()
tf.global_variables tf.global_variables() 是 TensorFlow 1.x 中的一个函数,它返回图中所有的全局变量。在 TensorFlow 2.x 中,这个函数已经被移除了,取而代之的是 tf.compat.v1.global_variables()。 然而,在 TensorFlow 2.x …...

登录注册实现
一、前端页面注册到Vue 1.创建登录和注册组件 <template><div>login</div></template><script> export default {name: HomeView,data() {return {}},methods: {}, } </script><template><div>register</div></tem…...

Push rejected: Push to origin/master was rejected
Push rejected: Push to origin/master was rejected 原因:推拒绝:推送到起源/主人被拒绝 解决方案如下: 方案1: 1.在Idea打开终端 方案2: 1、在对应项目文件里打开 Git Bash 然后依次输入: git pull …...

在线OJ项目核心思路
文章目录 在线OJ项目核心思路1. 项目介绍2.预备知识理解多进程编程为啥采用多进程而不使用多线程?标准输入&标准输出&标准错误 3.项目实现题目API实现相关实体类定义新增/修改题目获取题目列表 编译运行编译运行流程 4.统一功能处理 在线OJ项目核心思路 1. 项目介绍 …...

Spring MVC:数据绑定
Spring MVC 数据绑定数据类型转换数据格式化数据校验 附 数据绑定 数据绑定,指 Web 页面上请求和响应的数据与 Controller 中对应处理方法上的对象绑定(即是将用户提交的表单数据绑定到 Java 对象中)。 过程如下: ServletRequest…...

STM32CubeMX学习笔记-USB接口使用(HID按键)
STM32CubeMX学习笔记-USB接口使用(HID按键) 一、USB简介1.1 USB HID简介 二、新建工程1. 打开 STM32CubeMX 软件,点击“新建工程”2. 选择 MCU 和封装3. 配置时钟4. 配置调试模式 三、USB3.1 参数配置3.2 引脚配置3.3 配置时钟3.4 USB Device…...

C#,数值计算——Ranq2的计算方法与源程序
1 文本格式 using System; namespace Legalsoft.Truffer { /// <summary> /// Backup generator if Ranq1 has too short a period and Ran is too slow.The /// period is 8.5E37. Calling conventions same as Ran, above. /// </summary> …...

C/C++ 数据结构 - 链表
1.单链表 https://blog.csdn.net/qq_36806987/article/details/79858957 1 #include<stdio.h>2 #include<stdlib.h>3 4 /*结构体部分*/5 typedef struct Node6 {7 int data; //数值域8 struct Node *next; //指针域9 }N;10 11 N *Init() //初始化单…...

【算法基础】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序
目录 1 冒泡排序(Bubble Sort) 2 插入排序(Insertion Sort) 3 选择排序(Selection Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6 堆排序 …...

javascript二维数组(3):指定数组元素的特定属性进行搜索
js中对数组, var data [{“name”: “《西游记》”, “author”: “吴承恩”, “cat”: “A级书刊”, “num”: 3},{“name”: “《三国演义》”, “author”: “罗贯中”, “cat”: “A级书刊”, “num”: 8},{“name”: “《红楼梦》”, “author”: “曹雪芹”,…...

使用Qt进行HTTP通信的方法
文章目录 1 HTTP协议简介1.1 HTTP协议的历史和发展1.2 HTTP协议的特点1.3 HTTP的工作过程1.4 请求报文1.5 响应报文 2 使用Qt进行HTTP通信2.1 Qt的HTTP通信类2.2 HTTP通信过程 3 JSON3.1 cJSON库简介3.2 cJSON库的设计思想和数据结构3.3 cJSON库的使用方法 1 HTTP协议简介 1.1…...

第45节——页面中修改redux里的数据
一、什么是action 在 Redux 中,Action 是一个简单的 JavaScript 对象,用于描述对应应用中的某个事件(例如用户操作)所发生的变化。它包含了一个 type 属性,用于表示事件的类型,以及其他一些可选的数据。 …...

软考 系统架构设计师系列知识点之软件架构风格(2)
接前一篇文章:软考 系统架构设计师系列知识点之软件架构风格(1) 这个十一注定是一个不能放松、保持“紧”的十一。由于报名了全国计算机技术与软件专业技术资格(水平)考试,11月4号就要考试,因此…...

【C++11】Lambda 表达式:基本使用 和 底层原理
文章目录 Lambda 表达式1. 不考虑捕捉列表1.1 简单使用介绍1.2 简单使用举例 2. 捕捉列表 [ ] 和 mutable 关键字2.1 使用方法传值捕捉传引用捕捉 2.2 捕捉方法一览2.3 使用举例 3. lambda 的底层分析 Lambda 表达式 书写格式: [capture_list](parameters) mutabl…...