041、子序列类型问题(labuladong)

news/2024/3/29 22:07:17/文章来源:https://blog.csdn.net/Yora123/article/details/129137610

子序列类型问题

一、经典动态规划:编辑距离

基于labuladong的算法网站,经典动态规划:编辑距离;

总结:

  • 一般来说涉及到两个字符串的问题,需要依赖上一次的各种操作,一般使用dp table;
  • dp数组和dp函数:
    • 本质上是一样的;
    • 只不过dp数组是利用数组去体现结果值;
    • dp函数是在函数返回结果中体现;
[72]编辑距离//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// 利用 dp table 进行自下而上的求解public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// dp[i][j] : word1中从[0,i] 变成 word2[0,j] 所需要的最少步骤int[][] dp = new int[m + 1][n + 1];// base casefor (int i = 1; i <= m; i++) {dp[i][0] = i;}for (int i = 1; i <= n; i++) {dp[0][i] = i;}// 开始遍历for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 判断if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {// 插入、删除、替换dp[i][j] = min(dp[i][j - 1] + 1,// 添加dp[i - 1][j] + 1,// 删除dp[i - 1][j - 1] + 1// 替换);}}}return dp[m][n];}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));}
}
//leetcode submit region end(Prohibit modification and deletion)

二、动态规划设计:最大子数组

基于labuladong的算法网站,动态规划设计:最大子数组;

力扣第53题,最大子数组和;

[53]最大子数组和//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// dp tablepublic int maxSubArray(int[] nums) {int length = nums.length;// 需要明确dp数组的定义,dp[i]:以nums[i]为结尾时,最大连续子数组的最大和int[] dp = new int[length];// base casedp[0] = nums[0];for (int i = 1; i < length; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);}// 遍历得到最大值int res = Integer.MIN_VALUE;for (int i = 0; i < length; i++) {if (dp[i] > res) {res = dp[i];}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)

三、经典动态规划:最长公共子序列

基于labuladong的算法网站,经典动态规划:最长公共子序列;

1、最长公共子序列

力扣第1143题,最长公共子序列;

[1143]最长公共子序列//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// dp tablepublic int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();// dp[i][j] 代表字符串 text1[0,i] 和 text2[0,j] 的最长公共子序列长度int[][] dp = new int[m + 1][n + 1];// base casefor (int i = 0; i <= m; i++) {dp[m][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][n] = 0;}// 开始遍历子串for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}// 返回return dp[m][n];}int max(int a, int b, int c) {return Math.max(a, Math.max(b, c));}
}
//leetcode submit region end(Prohibit modification and deletion)

2、两个字符串的删除操作

力扣第583题,两个字符串的删除操作;

[583]两个字符串的删除操作//leetcode submit region begin(Prohibit modification and deletion)
class Solution {/*** @param word1* @param word2* @return 返回使得 word1 和 word2 相同所需的最小步数*/public int minDistance(String word1, String word2) {int length = get(word1, word2);return word1.length() + word2.length() - length - length;}// 求 word1 和 word2 的最长公共子序列int get(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[m][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][n] = 0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

3、两个字符串的最小ASCII删除和

力扣第712题,两个字符串的最小ASCII删除和;

[712]两个字符串的最小ASCII删除和//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int minimumDeleteSum(String s1, String s2) {int m = s1.length();int n = s2.length();// dp[i][j] 使字符串 s1[0,i] 和 s2[0,j] 两个相等所需要删除的字符的 ASCII 值的最小和int[][] dp = new int[m + 1][n + 1];// base casefor (int i = 1; i <= m; i++) {dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);}for (int i = 1; i <= n; i++) {dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);}// 开始遍历for (int i = 1; i <= m; i++) {int code1 = s1.charAt(i - 1);for (int j = 1; j <= n; j++) {int code2 = s2.charAt(j - 1);// 判断此时两个字母是否相等if (code1 == code2) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(dp[i - 1][j] + code1, dp[i][j - 1] + code2);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

四、动态规划之子序列问题解题模板

基于labuladong的算法网站,动态规划之子序列问题解题模板;

1、最长回文子序列

力扣第516题,最长回文子序列;

[516]最长回文子序列//leetcode submit region begin(Prohibit modification and deletion)
class Solution {// 可以看成两个字符串,找最长公共子序列的长度public int longestPalindromeSubseq(String s) {StringBuffer sb = new StringBuffer();int length = s.length();for (int i = length - 1; i >= 0; i--) {sb.append(s.charAt(i));}return get(s, sb.toString());}int get(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

2、让字符串成为回文串的最少插入次数

力扣第1312题,让字符串成为回文串的最少插入次数;

[1312]让字符串成为回文串的最少插入次数//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int minInsertions(String s) {StringBuffer sb = new StringBuffer();int length = s.length();for (int i = length - 1; i >= 0; i--) {sb.append(s.charAt(i));}int max = get(s, sb.toString());return length - max;}int get(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}
//leetcode submit region end(Prohibit modification and deletion)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_72299.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CSS预处理器sass和less

文章目录CSS预处理器什么是CSS预处理器Sass和LESS背景介绍Sass背景介绍LESS的背景介绍Sass安装Sass下载Ruby安装文件安装Ruby安装Sass编译Sass命令行编译命令行编译配置选项四种编译排版演示nested 编译排版格式expanded 编译排版格式compact 编译排版格式compressed 编译排版格…

登录逻辑漏洞整理集合

目录一、任意用户注册1.未验证邮箱/手机号2、不安全验证邮箱/手机号3.批量注册4.个人信息伪造5.前端验证审核绕过6.用户名覆盖二、任意用户登录1、万能密码2、验证码、密码回显3、登录检测不安全三、任意账号重置1、重置账号名2、验证码3、MVC数据对象自动绑定4、Unicode字符处…

独立产品灵感周刊 DecoHack #048 - 优秀独立开发产品推荐

如果有关注我的 Twitter 的朋友应该看到了&#xff0c;我上周末研究了两天 AI 画图&#xff0c;现在用 Ai 做图太强了&#xff0c;上周又升级 Stable Diffusion 玩了一下&#xff0c;和我去年试的时候相比强大了好多&#xff0c;而且插件LoRA模型玩法都还在快速迭代&#xff0c…

强化学习DQN之俄罗斯方块

强化学习DQN之俄罗斯方块强化学习DQN之俄罗斯方块算法流程文件目录结构模型结构游戏环境训练代码测试代码结果展示强化学习DQN之俄罗斯方块 算法流程 本项目目的是训练一个基于深度强化学习的俄罗斯方块。具体来说&#xff0c;这个代码通过以下步骤实现训练&#xff1a; 首先…

车机开发【Android SystemUI 架构音量控制详解】

SystemUI介绍 SystemUI摘要 在Android系统中SystemUI是以应用的形式运行在Android系统当中&#xff0c;即编译SystemUI模块会生产APK文件&#xff0c;源代码路径在frameworks/base/packages/SystemUI/&#xff0c;安装路径system/priv-app/-SystemUI。 什么是SystemUI 在前…

使用带有 Moveit 的深度相机来避免碰撞

文章目录 什么是深度相机?如何将 Kinect 深度相机添加到您的环境中在 Rviz 中可视化深度相机数据在取放场景中使用深度相机将深度相机与您的 Moveit 设置一起使用有很多优势。机器人可以避免未知环境中的碰撞,甚至可以对周围的变化做出反应。然而,将深度相机连接到您的设置并…

FlinkSQL行级权限解决方案及源码

FlinkSQL的行级权限解决方案及源码&#xff0c;支持面向用户级别的行级数据访问控制&#xff0c;即特定用户只能访问授权过的行&#xff0c;隐藏未授权的行数据。此方案是实时领域Flink的解决方案&#xff0c;类似离线数仓Hive中Ranger Row-level Filter方案。 源码地址: https…

数据分片(mycat)

1. 数据分片概念&#xff1a; 1.1. 分库分表 什么是分库分表&#xff1a; 将存放在一台数据库服务器中的数据&#xff0c;按照特定方式&#xff08;指的是程序开发的算法&#xff09;进行拆分&#xff0c;分散存放到多台数据库服务器中&#xff0c;以达到分散单台服务器负载的…

第51篇-某彩网登录参数分析-webpack【2023-02-21】

声明:该专栏涉及的所有案例均为学习使用,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关!如有侵权,请私信联系本人删帖! 文章目录 一、前言二、网站分析一、前言 今天我们看一个webpack的网站 aHR0cHM6Ly8xMGNhaTUwMC5jYy9sb2dpbg==二、网站分析 首先…

网络协议(一)应用层(自定制协议、HTTP协议)

目录 应用层&#xff1a;负责应用程序之间的数据沟通 一、自定制协议&#xff08;私有协议&#xff09; 二、HTTP协议 1&#xff09;、请求行解析&#xff1a;GET /index.html HTTP/1.1 第一部分&#xff1a;请求方法&#xff1a;多种多样&#xff0c;描述不同的请求目的 …

大数据知识图谱项目——基于知识图谱的医疗知识问答系统(详细讲解及源码)

基于知识图谱的医疗知识问答系统 一、项目概述 本项目基于医疗方面知识的问答&#xff0c;通过搭建一个医疗领域知识图谱&#xff0c;并以该知识图谱完成自动问答与分析服务。本项目以neo4j作为存储&#xff0c;基于传统规则的方式完成了知识问答&#xff0c;并最终以关键词执…

Verilog 学习第五节(串口发送部分)

小梅哥串口部分学习part1 串口通信发送原理串口通信发送的Verilog设计与调试串口发送应用之发送数据串口发送应用之采用状态机实现多字节数据发送串口通信发送原理 1&#xff1a;串口通信模块设计的目的是用来发送数据的&#xff0c;因此需要有一个数据输入端口 2&#xff1a;…

Qt中修改界面类的类名时需要注意的几个修改点

有些时候因为一些原因&#xff0c;需要修改Qt中创建的界面类&#xff0c;需要特别注意几个修改点。 比如将test类修改为test2类 修改test.h名称为test2.h文件&#xff1b;修改test.cpp名称为test2.cpp文件&#xff1b;修改test.ui名称为test2.ui文件&#xff1b;修改pro文件中…

多层感知机的区间随机初始化方法

摘要&#xff1a; 训练是构建神经网络模型的一个关键环节&#xff0c;该过程对网络中的参数不断进行微调&#xff0c;优化模型在训练数据集上的损失函数。参数初始化是训练之前的一个重要步骤&#xff0c;决定了训练过程的起点&#xff0c;对模型训练的收敛速度和收敛结果有重要…

Java基础43 异常(Exception)

异常&#xff08;Exception&#xff09;Exception1.1 异常的概念1.2 异常体系图&#xff08;☆&#xff09;1.3 异常处理分类1.3.1 运行时异常&#xff08;☆&#xff09;1.3.2 编译时异常&#xff08;☆&#xff09;1.4 异常处理&#xff08;☆&#xff09;1.4.1 try-catch异常…

【Git】Git下载安装与使用(一)

目录 1. 前言 1.1 什么是Git 1.2 使用Git能做什么 2. Git概述 2.1 Git简介 2.2 Git下载与安装 3. Git代码托管服务 3.1 常用的Git代码托管服务 3.2 码云代码托管服务 1. 前言 1.1 什么是Git Git是一个分布式版本控制工具&#xff0c;主要用于管理开发过程中的源代码…

Cookies与Session会话技术详解

引言:日常生活中&#xff0c;人和人之间沟通交流&#xff0c;涉及到一个词----会话&#xff0c;软件中一样存在会话&#xff0c;如&#xff1a;网购登录&#xff0c;访问公司OA系统也是不断的会话&#xff0c;软件中如何管理浏览器客户端和服务端之间会话过程中的会话数据呢&am…

盘点四种自动化测试模型实例及优缺点

一&#xff0c;线性测试 1.概念&#xff1a; 通过录制或编写对应应用程序的操作步骤产生的线性脚本。单纯的来模拟用户完整的操作场景。 &#xff08;操作&#xff0c;重复操作&#xff0c;数据&#xff09;都混合在一起。 2.优点&#xff1a; 每个脚本相对独立&#xff0…

【java】java sftp传输 ,java smb传输访问共享文件夹 集成springboot

文章目录java的sftp传输sftp注意事项java smb传输smb注意事项tips: 集成springboot与不集成springboot区别不大&#xff0c;springboot中无非是引入一个maven依赖 加一个Component注解 &#xff0c; 默认是单例&#xff1b; 复制代码前 请先认真看注意事项 java的sftp传输 依赖…

网络安全态势感知研究综述

摘要&#xff1a;随着物联网、云计算和数字化的迅速发展&#xff0c;传统网络安全防护技术无法应对复杂的网络威胁。网络安全态势感知能够全面的对网络中各种活动进行辨识、理解和预测。首先分别对态势感知和网络安全态势感知的定义进行了归纳整理&#xff0c;介绍了网络安全态…