网站开发的平台/网站推广交换链接
最长公共子序列
1143. 最长公共子序列 - 力扣(LeetCode)
代码随想录 (programmercarl.com)
最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili
本题和上一题718.最长重复子数组在很多方面相似,区别在与不需要连续,因此在dp数组的推导上有些改变。
由于不需要连续,dp[i][j]的值针对text1和text2相同及不同这两种情况有不同的表示。
首先 dp[i][j]表示序列text1[0:i-1]和text2[0:j-1]的最长公共子序列的长度
当text[i-1] == text[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]),dp[i][j]由数组左和上的较大值确定。
由此,dp[i][j]由左上部分确认,当i j为0时,表示的序列为空,空序列与任何序列的最长公共子序列均为空,长度为0,dp[0][0]、dp[0][1]、dp[1][0]都为0。
i,j两个变量循环遍历。
最后返回dp[text1.size()][text2.size()]。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// 创建一个二维向量 dp,用于存储动态规划的状态值// dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度// 初始化 dp 的大小为 (text1.size()+1) x (text2.size()+1),值全部为 0vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));// 双层循环遍历 text1 和 text2for (int i = 1; i <= text1.size(); i++) { // i 从 1 开始,直到 text1.size()for (int j = 1; j <= text2.size(); j++) { // j 从 1 开始,直到 text2.size()// 如果 text1 的第 i 个字符和 text2 的第 j 个字符相同if (text1[i - 1] == text2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相同,则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前字符不包含在 LCS 中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[text1.size()][text2.size()],即 text1 和 text2 的 LCS 长度return dp[text1.size()][text2.size()];}
算法的时间复杂度为O(m*n),空间复杂度为O(m*n),m和n分别代表两个序列的长度,二维数组,二维循环遍历。
不相交的线
1035. 不相交的线 - 力扣(LeetCode)
和上题一致,换些变量便能解决,不过真要面试的时候,希望能想到吧。
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 创建一个二维向量 dp,用于存储动态规划的状态值// dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素的最长公共子序列的长度// 初始化 dp 的大小为 (nums1.size()+1) x (nums2.size()+1),值全部为 0vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));// 双层循环遍历 nums1 和 nums2for (int i = 1; i <= nums1.size(); i++) { // i 从 1 开始,直到 nums1.size()for (int j = 1; j <= nums2.size(); j++) { // j 从 1 开始,直到 nums2.size()// 如果 nums1 的第 i 个元素和 nums2 的第 j 个元素相同if (nums1[i - 1] == nums2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相同,则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前元素不包含在 LCS 中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[nums1.size()][nums2.size()],即 nums1 和 nums2 的 LCS 长度// 这也是不相交的直线段的最大数量return dp[nums1.size()][nums2.size()];}
算法的时间复杂度为O(m*n),空间复杂度为O(m*n)。
最大子序和
53. 最大子数组和 - 力扣(LeetCode)
之前用过贪心算法解这道题,当子序和为负,则抛弃当前子序和,从下一个位置开始计算子序和。这里使用动态规划也是类似的。
由于是连续的子序和,dp[i]表示到i为止的最大子序和(此处应包含nums[i])
dp[i] = max(dp[i-1]+nums[i],nums[i]),这里可以想象贪心的思路,当dp[i-1]为负时,自然dp[i-1]+nums[i]要小于nums[i]。
因此,唯一需要的是当前元素的前一位的dp值,dp[0] = nums[0]。
从前往后遍历
最后返回dp数组中的最大值。
class Solution {
public:int maxSubArray(vector<int>& nums) {// 创建一个向量 dp,用于存储以第 i 个元素结尾的最大子数组和// 初始化 dp 的大小与 nums 相同,值全部为 0vector<int> dp(nums.size(), 0);// dp[0] 是数组第一个元素的值,因为一个元素的子数组和就是它本身dp[0] = nums[0];// 遍历数组 nums,从第二个元素开始for (int i = 1; i < nums.size(); i++) {// 如果以第 i-1 个元素结尾的最大子数组和小于 0if (dp[i - 1] < 0) {// 则以第 i 个元素结尾的最大子数组和就是第 i 个元素的值// 因为加上前面的子数组和会使得和更小dp[i] = nums[i];} else {// 如果以第 i-1 个元素结尾的最大子数组和大于等于 0// 则将第 i 个元素的值加到以第 i-1 个元素结尾的最大子数组和上// 这样可以保持子数组的连续性dp[i] = dp[i - 1] + nums[i];}}// 使用 STL 中的 max_element 函数找出 dp 中的最大值// 这个最大值就是整个数组的最大子数组和return *max_element(dp.begin(), dp.end());}
};
算法的时间复杂度为O(n),空间复杂度为O(n)。
判断子序列
392. 判断子序列 - 力扣(LeetCode)
同样和最长公共子序列相似,在遍历过程中,当dp[i][j] == s.size()时,表示s为t的子序列,否则s不是t的子序列,具体代码如下。
class Solution {
public:// 定义一个成员函数,用于判断 s 是否为 t 的子序列bool isSubsequence(string s, string t) {// 如果 s 为空字符串,那么它是任何字符串的子序列if (s.size() == 0) {return true;}// 创建一个二维向量 dp,用于存储动态规划的状态值// dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的匹配长度vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));// 双层循环遍历 s 和 tfor (int i = 1; i <= s.size(); i++) { // i 从 1 开始,直到 s.size()for (int j = 1; j <= t.size(); j++) { // j 从 1 开始,直到 t.size()// 如果 s 的第 i 个字符和 t 的第 j 个字符相同if (s[i - 1] == t[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;// 如果匹配长度等于 s 的长度,说明 s 是 t 的子序列if (dp[i][j] == s.size()) {return true;}} else {// 如果不相同,则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这表示当前字符不包含在子序列中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 如果遍历完 dp 数组后没有找到匹配长度等于 s 长度的状态,则 s 不是 t 的子序列return false;}
};
算法的时间复杂度为O(m*n),空间复杂度为O(m*n)。
相关文章:

代码随想录算法训练营Day50|1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列
最长公共子序列 1143. 最长公共子序列 - 力扣(LeetCode) 代码随想录 (programmercarl.com) 最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili 本题和上一题718.最长重复子数组在很多方面相似…...

国家自然科学基金标书大全(2002-2024)
数据来源:在20世纪80年代初,为了促进中国的科技体制革新并改革科研资金分配机制,中国科学院的89位院士联名向党和国家领导人提出建议,设立了国家自然科学基金的设立。国自然基金自创立以来,根据国家发展科学技术方针、…...

Python代码打包成exe应用
目录 一、前期准备 二、Pyinstaller打包步骤 Pyinstaller参数详解 三、测试 Spec 文件相关命令 一、前期准备 (1)首先,我们需要确保你的代码可以在本地电脑上的pycharm正常运行成功。 (2)我们要先安装Pyinstalle…...

CesiumJS【Basic】- #016 多边形面渲染“花了”的问题
文章目录 多边形面渲染“花了”的问题1 目标2 问题代码3 修正后代码4 总结多边形面渲染“花了”的问题 1 目标 解决多边形的面“花了”的问题 2 问题代码 使用Cesium.PerInstanceColorAppearance渲染后出现色斑 import * as Cesium from "cesium";const viewer …...

qt 开发对信号槽进行二次封装,实现信号槽管理接口。
最近做的一个项目,由于工程需要模块之间能够互相通信,但又不想模块之间耦合度太高 使用信号槽的话,需要两个类的对象或者指针在其中一个类都要体现,这样达不到效果, 想要一个管理类对这些互相通信的类之间进行管理,只需要在各自的类注册发送者和接收者即可,双方通过一…...

本地项目上传到gitee
本地项目通过webstorm上传到gitee 1.登录gitee选择新建仓库 2.输入新建仓库的名字(名字与本地项目名一致) 3.复制链接 4.找到本地项目,选中地址输入cmd打开命令提示框 5.输入git init初始化git,生成.git文件 6.webstorm中打开项目…...

ONLYOFFICE 8.1版本桌面编辑器测评:超越想象的办公体验!
在当今数字化办公时代,一个功能强大、操作便捷的办公套件对于提高工作效率至关重要。ONLYOFFICE 8.1作为一款备受瞩目的办公软件,凭借其全面的功能、优异的性能和出色的用户体验,为用户带来了超越想象的办公体验。下面,我们将对ON…...

中介子方程三十四
XXFXXuXXWXXuXXdXXrXXαXXuXpXXKXηXiXXαXXiXηXKXXpXuXXαXXrXXdXXuXWXπXXWXeXyXeXbXπXpXXNXXqXeXXrXXαXXuXpXXKXηXiXXαXXiXηXKXXpXuXXαXXrXXeXqXXNXXpXπXbXeXyXeXWXXπXWXuXXdXXrXXαXXuXpXXKXηXiXXαXXiXηXKXXpXuXXαXXrXXdXXuXXWXXuXXFXXEXXyXXEXXrXXαXXuXpXXK…...

最新Sublime Text软件安装包分享(汉化版本)
Sublime Text 是一款广受欢迎的跨平台文本编辑器,专为代码、标记和散文编辑而设计。它以其简洁的用户界面、强大的功能和高性能而著称,深受开发者和写作者的喜爱。 一、下载地址 链接:https://pan.baidu.com/s/1kErSkvc7WnML7fljQZlcOg?pwdk…...

AI-智能体基础设施
个性化记忆需要世界模型来协助构建 业界有一个精简的Agent表达公示,即:Agent大模型(LLM)记忆(Memory)主动规划(Planning)工具使用(Tool Use)。基于该公式&am…...

【docker】docker启动neo4j,并配置内存
注意下:--volume宿主机目录:/data 和 --publish宿主机port:7474 --publish宿主机port:7687 docker run -d \ --publish9801:7474 --publish9802:7687 \ --env NEO4J_AUTHneo4j/passwd \ --volume/opt/docker/data/vol-data/neo4j4.2:/data \ --restart always \ --…...

面试准备记录
6月26日 今日学习 MySQL的1-7题(中期报告,加上玩了游戏,就没有认真背题) 6月25日 今日复习 JVM的内存管理部分(1-31题) 6月24日 今日学习 类的生命周期?类加载过程?类加载器有…...

文件管理—linux(基础IO)
目录 编辑 一、C语言文件接口(库函数) hello.c写文件 hello.c读文件 输出信息到显示器 stdin & stdout & stderr 二、系统文件I/O(系统调用) hello.c 写文件: hello.c读文件 接口介绍 open open…...

【华为OD机试|01】最远足迹(Java/C/Py/JS)
目录 一、题目介绍 1.1 题目描述 1.2 备注: 1.3 输入描述 1.4 输出描述 1.5 用例 二、Java代码实现 2.1 实现思路 2.2 详细代码 2.3 代码讲解: 三、C语言实现 3.1实现步骤 3.2 实现代码 3.3 代码详解 四、Python实现 4.1 实现步骤 4.2 …...

conda安装管理配置
原文链接:conda管理配置 导言 安装卸载 卸载 卸载 docker sudo rm -r /opt/anaconda3 #conda安装位置安装 从镜像archive中下载sh脚本安装 bash ./software/Anaconda3-2024.02-1-Linux-x86_64.sh -b -p /opt/anaconda3 #conda安装位置管理 查看 conda --ver…...

鸿蒙开发HarmonyOS NEXT(一)
最近总听见大家讨论鸿蒙,前端转型的好方向?先入门学习下 目前官方版本和文档持续更新中 一、开发环境 提示:要占用的空间比较多,建议安装在剩余空间多的盘 1、下载:官网最新工具 - 下载中心 - 华为开发者联盟 (huaw…...

新能源革命风起云涌:创新科技引领可持续发展新篇章
随着全球气候变化和环境问题日益严峻,新能源革命正以其不可阻挡的势头,席卷着世界的每一个角落。 创新科技在这场革命中发挥着至关重要的作用,它不仅是新能源开发利用的引擎,更是推动可持续发展的关键力量。 新能源革命的核心在于…...

Java之TimeUnit类
1.TimeUnit类介绍 TimeUnit(时间单元)是一个描述时间单元的枚举类,在该枚举类中定义有以下的几个时间单元实例:天(DAYS)、时(HOURS)、分(MINUTES)、秒&#…...

【大数据】大数据时代的黎明
目录 前言 深入解读大数据的本质 大数据的起源与演进轨迹 大数据对社会经济的深远影响 经济领域的革新 社会治理与公共服务的智能化 创新体系的重构 面临的挑战与应对 前言 步入21世纪以来,人类文明正站在一个历史性的转折点上,迎来了大数据时代的…...

多接口分线盒在工业自动化中的重要性与应用
简介 多接口分线盒是现代工业自动化中不可或缺的一个组成部分,它主要用于简化复杂的接线系统,提高效率和可靠性。本文将详细探讨多接口分线盒的定义、功能、以及在工业自动化中的应用情况。 无源多接口分线盒 多接口分线盒的定义与功能 多接口分线盒是…...

C# Modbus设备信息加载的实现方式(2)
GlobalProperties是一个全局的数据,类似CoreData: public class GlobalProperties{public static Device Device { set; get; }public static Action<int, string> AddLog;public static SysAdmin CurrentAdmin;public static ModbusTCP Modbus { …...

mongoDB基本命令操作
文章目录 1. 安装(1). 启动mongodb(2). 数据库连接 2. 基本命令(1) 数据库操作(2) 集合操作(3) 文档操作1) 简单查询2) 条件查询3) 投影查询4) 文档更新5) 列值增长修改6) 删除文档7) 分页查询8) 排序查询9) 正则查询(模糊查询)10) 比较查询11) 包含查询 3. 索引(1) 执行计划 1…...

MySQL索引,事务
一.MySQL索引介绍 索引是一个排序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址。在数据十分大的时候,索引可以大大加快查询的速度。这是因为使用索引后可以不用扫描全表来定位某行的数据,而是先通过索引表找到该行数…...

嵌入式软件面试记录(5)
1.FreeRTOS使用,是自己移植的吗,移植过程中设置了多少个任务? 答:是自己移植的,从官网下载的包根据手册移植的。 主要涉及以下几个任务: 主任务:负责系统初始化和创建其他任务。创建队列任务点…...

Linux-笔记 OverlayFS文件系统入门
目录 前言 主要概念 工作原理 特点特性 1、上下合并 2、同名文件覆盖 3、同名目录合并 4、写时拷贝 实操入门 内核配置 挂载文件系统 验证 1、同名文件覆盖 2、同名目录合并 3、写时拷贝 1)验证新增文件或目录 2)验证修改文件 3&…...

Kubernetes面试整理-如何配置和使用Service, Ingress?
在 Kubernetes 中,Service 和 Ingress 是用于管理和暴露应用程序的网络访问的主要资源。以下是如何配置和使用 Service 和 Ingress 的详细指南: Service Service 是一种抽象,用于定义一组 Pod 的逻辑集合,并提供一种访问这些 Pod 的策略。Service 可以使应用程序内部或外部…...

深入浅出:NPM常用命令详解与实践
深入浅出地讲解npm常用命令及其实践,可以帮助开发者更好地理解和使用这个强大的Node.js 包管理工具。以下是一些常用的npm命令及其详细解释和实践案例: 1:初始化项目: 命令:npm init用途:生成一个package…...

IPv6 address status lifetime
IPv6 地址状态转换 Address lifetime (地址生存期) 每个配置的 IPv6 单播地址都有一个生存期设置,该设置确定该地址在必须刷新或替换之前可以使用多长时间。某些地址设置为“永久”并且不会过期。“首选”和“有效”生存期用于指定其使用期限和可用性。 自动配置的…...

OpenVINO部署
OpenVINO部署 什么是 OpenVINO?OpenVINO 的优势安装指南系统要求:安装步骤 环境设置部署示例代码优化和部署步骤详细部署示例 什么是 OpenVINO? OpenVINO(Open Visual Inference and Neural Network Optimization)是由…...

面试题:MySQL优化,项目中举例
目录 一、SQL优化分两部分,如何发现慢SQL和如何优化慢SQL 二、项目举例 一、SQL优化分两部分,如何发现慢SQL和如何优化慢SQL 发现慢SQL有两种方案:第一种是开启我们的慢日志, 第二种就是使用skywalling发现慢的接口,进…...