当前位置: 首页 > news >正文

代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和

LeetCode T1143 最长公共子序列

题目链接:1143. 最长公共子序列 - 力扣(LeetCode)

题目思路:

动规五部曲分析

1.确定dp数组的含义

这里dp数组的含义是结尾分别为i-1,j-1的text1和text2的最长公共子序列长度

至于为什么是i-1,j-1我之前已经说过了,这里再说一次,因为如果定义为i和j 的话就需要比较两个字符串的首字母分别是否相等来初始化dp[0][i]和dp[0][j],因为这样定义的话dp[0][j]和    dp[i][0]就没有含义,省去了初始化的部分

2.确定递推公式

dp[i][j]可以从dp[i-1][j-1],dp[i-1][j]和dp[i][j-1]三个推出来

当text1[i]和text2[j]相等时,就是dp[i-1][j-1]+1

当两者不相等时,就是剩下两者的最大值

3.初始化dp数组

无需初始化,原因上面说清楚了,而剩下的所有值都会被覆盖,所以无所谓

4.遍历顺序

从前向后,因为后面的数据是前面产生的

5.打印排错

题目代码:

class Solution {public int longestCommonSubsequence(String text1, String text2) {int dp[][] = new int[text1.length()+1][text2.length()+1];for(int i = 1;i<=text1.length();i++){char c = text1.charAt(i-1);for(int j = 1;j<=text2.length();j++){char c2 = text2.charAt(j-1);if(c == c2){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[text1.length()][text2.length()];}
}

LeetCode T1135 不相交的线

题目链接:1035. 不相交的线 - 力扣(LeetCode)

题目思路:

这里我们可以将这一题的思路转化一下,其实就和第一题的思路一模一样,题目要求两条对应的线不能相交,其实就是交代了有序性,这也满足了第一题的条件,求最长公共子序列,所以不做过多赘述.

题目代码:

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

LeetCode T53 最大子数组和

题目链接:53. 最大子数组和 - 力扣(LeetCode)

题目思路:

动规五部曲分析

1.确定dp数组的含义

这里dp数组的含义是i位置之前(包括i在内)最大连续子序列之和

这一题我们在之前也用过贪心的思路来求解,见文章

代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和-CSDN博客

2.确定递推公式

dp[i][j]可以从前面一个推出,如果累计和小于当前的nums[i],就从nums[i]开始记录

3.初始化dp数组

dp[0] = nums[0];不能初始化为0,因为有一个元素的情况存在

4.遍历顺序

从前向后遍历即可

5.打印排错

注意:这题的结果不在结尾取,要定义一个res在赋值的时候顺便记录最大值

题目代码:

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int res = dp[0];for(int i = 1;i<nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);res = Math.max(res,dp[i]);}return res;}
}

相关文章:

代码随想录Day45 动态规划13 LeetCode T1143最长公共子序列 T1135 不相交的线 T53最大子数组和

LeetCode T1143 最长公共子序列 题目链接:1143. 最长公共子序列 - 力扣&#xff08;LeetCode&#xff09; 题目思路: 动规五部曲分析 1.确定dp数组的含义 这里dp数组的含义是结尾分别为i-1,j-1的text1和text2的最长公共子序列长度 至于为什么是i-1,j-1我之前已经说过了,这里再…...

写了个监控 ElasticSearch 进程异常的脚本!

服务器配置免密钥环境准备&#xff1a; 配置免密钥前&#xff0c;需要在服务器的 hosts 文件中配置目标主机名称与 IP 对应关系。 vim /etc/hosts IP1 hostname1 IP2 hostname2 ...... 将 mianmiyaojiaoben.zip 安装包解压在当前目录下 cd /usr/local/jiaoben unzip mianmi…...

第三篇 基于JSP 技术的网上购书系统—— 数据库系统设计(网上商城、仿淘宝、当当、亚马逊)

目录 1.逻辑关系设计 2.物理设计 2.1管理员表 2.2留言表 2.3会员登录表 2.4会员表 2.5订单表 2.6订单商品表 2.7产品表 2.8产品货架表 2.9收藏表 2.10类别表 2.11新闻表 数据库系统是用来保存数据的软件系统&#xff0c;当今比较流行的数据库系统&#xff0c;如 MS…...

电脑检测温度软件有哪些?

环境&#xff1a; Win10 专业版 问题描述&#xff1a; 电脑检测温度软件有哪些&#xff1f; 解决方案&#xff1a; 有很多电脑检测温度的软件可供选择&#xff0c;以下是一些常用的电脑温度监测工具&#xff1a; HWMonitor&#xff1a;一款免费的硬件监控软件&#xff0…...

设计模式 -- 单例模式(Singleton Pattern)

单例模式&#xff1a;最简单的设计模式之一。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。这种模式涉及到一个单一的类&#xff0c;该类负责创建自己的对象&#xff0c;同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式…...

ubuntu给终端加代理服务器

ubuntu给终端加代理 访问google.com 是否可以访问通 curl https://www.google.com如果访问不通说明代理服务器没有配置好。 使用 gedit ~/.bashrc 打开网络配置 gedit ~/.bashrc找到文章的最后添加代理 export http_proxyhttp://127.0.0.1:7890 export https_proxyhttp://…...

centos 6.10 安装 readline 6.2.0

下载地址 解压文件 cd readline-6.2 ./configure -prefix /usr/local/readline-6.2 make && make install安装完成...

IDEA 2023搭建 SpringMVC +FreeMarker+JDBC

1.IDEA的版本&#xff0c;目前最新是2023&#xff0c;要选择旗舰版。笔者曾选择社区版&#xff0c;发现少了很多功能。只能重新安装。 2.安装好以后的第1件事&#xff0c;是设置Maven&#xff0c;并将下载地址改为淘定站&#xff0c;参照这篇一次包会——最新IDEA配置Maven指南…...

RabbitMQ传统数据持久化和Lazy queue的区别

问题引出&#xff1a; 在了解这个问题前我们需要一些前置知识&#xff1a; 关于MQ可靠性&#xff0c;在默认情况下&#xff0c;RabbitMQ会将接收到的信息保存在内存中以降低消息收发的延迟。这样会导致两个问题&#xff1a; 一旦MQ宕机&#xff0c;内存中的信息会丢失 内存空…...

docker部署lnmp环境

文章目录 前期准备&#xff1a;一、部署mysql1.1 获取 Mysql 5.7.22 镜像1.2 启动mysql容器 二、部署php2.1 获取php 7.2镜像2.2 启动php 容器2.3 php的扩展安装 三、部署nginx3.1 获取nginx:1.14镜像3.2 启动nginx容器3.3 编写nginx虚拟主机配置文件&#xff0c;使其支持php3.…...

数据结构 | 带头双向循环链表专题

数据结构 | 带头双向循环链表专题 前言 前面我们学了单链表&#xff0c;我们这次来看一个专题带头的双向循环链表~~ 文章目录 数据结构 | 带头双向循环链表专题前言带头双向循环链表的结构实现双向链表头文件的定义创建节点哨兵位初始化尾插尾删头插头删打印查找指定位置前插入…...

Redis使用Pipeline(管道)批量处理

Redis 批量处理 在开发中&#xff0c;有时需要对Redis 进行大批量的处理。 比如Redis批量查询多个Hash。如果是在for循环中逐个查询&#xff0c;那性能会很差。 这时&#xff0c;可以使用 Pipeline (管道)。 Pipeline (管道) Pipeline (管道) 可以一次性发送多条命令并在执…...

Linux中at命令添加一次性任务

1、工作原理 功能&#xff1a;在某个时间点&#xff0c;执行一次命令。 特点&#xff1a;任务是用户隔离的。 条件&#xff1a;必须要保证atd进程存在。 ps -ef |grep atd 原理&#xff1a;atd进程循环遍历队列里的任务&#xff0c;有任务&#xff0c;且到达执行时间&#xff…...

交换机基础知识之安全配置

交换机在网络基础设施中扮演着重要角色&#xff0c;它促进了设备之间数据包的流动。正因此&#xff0c;采取适当的安全措施来保护网络免受未经授权的访问和潜在攻击至关重要。本文将全面解读交换机基础安全配置知识&#xff0c;并提供实践方案&#xff0c;以保证安全的网络环境…...

Netty入门指南之Reactor模型

作者简介&#xff1a;☕️大家好&#xff0c;我是Aomsir&#xff0c;一个爱折腾的开发者&#xff01; 个人主页&#xff1a;Aomsir_Spring5应用专栏,Netty应用专栏,RPC应用专栏-CSDN博客 当前专栏&#xff1a;Netty应用专栏_Aomsir的博客-CSDN博客 文章目录 参考文献前言单线程…...

Ubuntu20.04软件安装顺序

目录 0.网卡驱动1. sogoupinyin2. terminator3.1zsh3.2升级Cmake&#xff08;有些后面的软件需要高版本Cmake&#xff09;4.显卡驱动(在cuda之前)5.CUDA与cudnn,TensorRT6.OpenCV(在ROS之前)6.1先安装各种依赖6.2安装Ceres-1.14.06.3安装Pangolin6.4安装Sophus6.5安装VTK6.5编译…...

适配器模式 ( Adapter Pattern )(6)

适配器模式 ( Adapter Pattern ) 适配器模式&#xff08;Adapter Pattern&#xff09;是作为两个不兼容的接口之间的桥梁 适配器模式涉及到一个单一的类&#xff0c;该类负责加入独立的或不兼容的接口功能 举个真实的例子&#xff0c;读卡器是作为内存卡和笔记本之间的适配器…...

JAVA G1垃圾收集器介绍

为解决CMS算法产生空间碎片和其它一系列的问题缺陷&#xff0c;HotSpot提供了另外一种垃圾回收策略&#xff0c;G1&#xff08;Garbage First&#xff09;算法&#xff0c;通过参数-XX:UseG1GC来启用&#xff0c;该算法在JDK 7u4版本被正式推出&#xff0c;官网对此描述如下&am…...

十方影视后期“领进门”,成长与成就还得靠自身

在这个充满视觉冲击的时代&#xff0c;影视后期制作已经成为了一种炙手可热的艺术形式。而在这个领域&#xff0c;Adobe After Effects&#xff08;AE&#xff09;这款软件无疑是王者之一。十方影视后期作为十方教育科技旗下的艺术设计学科&#xff0c;不仅培养了数万名优秀的后…...

Golang之火爆原因

引言 在计算机编程领域&#xff0c;有很多种编程语言可供选择。然而&#xff0c;近年来&#xff0c;Golang&#xff08;Go&#xff09;这门相对年轻的编程语言却越来越受欢迎&#xff0c;备受推崇。那么&#xff0c;为什么Golang如此火爆&#xff1f;本文将探讨Golang之火爆原…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起&#xff0c;为了跨网段推流&#xff0c;千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...