041、子序列类型问题(labuladong)
子序列类型问题
一、经典动态规划:编辑距离
基于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)相关文章:
041、子序列类型问题(labuladong)
子序列类型问题 一、经典动态规划:编辑距离 基于labuladong的算法网站,经典动态规划:编辑距离; 总结: 一般来说涉及到两个字符串的问题,需要依赖上一次的各种操作,一般使用dp tableÿ…...
linux系统开机文段释义
第一段Version 2.01.1204. Copyright (C) 2010American Megatrends, Inc.Press <DEL> or <F2> to entersetup. Press <F7> for BBS POPUP Menu.设备上电,提示按DEL键或者F2键进入BIOS设置。按F8可以调出启动设备列表,可以选择性的启动…...
抽奖动画大转盘抽奖思路与做法
抽奖是各类营销活动中最常见的一种形式,本产品需求大致如下:转盘周围跑马灯交替闪烁,点击抽奖,大转盘旋转,调用接口获取抽奖结果,大转盘指针指向对应的奖品。高保如下图12.整体思路本需求要求跑马灯交替闪烁…...
Java实现 - 华为2016研发工程师编程题
文章目录删数字符集合数独删数 题目描述 有一个数组 a[N] 顺序存放 0 ~ N-1 ,要求每隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉的数的原始下标位置。以 8 个数 (N7) 为例 :{ 0,1,2…...
nginx的七层负载均衡
文章目录一、负载均衡介绍二、nginx的配置文件三、实验过程总结一、负载均衡介绍 四层负载均衡 所谓四层负载均衡是指OSI七层模型中的传输层, 那么传输层Nginx已经支持TCP/IP的控制, 所以只需要对客户端的请求进行TCP/IP协议的包转发就可以实现负载, 那么他的好处是性能非常快,…...
信息加密技术
介绍信息加密 信息加密是实现数据保密性的手段。 信息加密(Encryption)是将明文信息转换为密文信息,使之在缺少特殊信息时不可读的过程。只有拥有解密方法的对象,经由解密过程,才能将密文还原为正常可读的内容。 现…...
RS485通信总线详解
RS485 总线详解 RS-485 是美国电子工业协会(EIA)在 1983 年批准了一个新的平衡传输标准(Balanced Transmission Standard)也称作差分,EIA 刚开始将 RS(Recommended Standard)做为标准的前缀&am…...
罗技LogitechFlow技术--惊艳的多电脑切换体验
作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。所以可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。…...
社招中级前端笔试面试题总结
HTTP世界全览 互联网上绝大部分资源都使用 HTTP 协议传输;浏览器是 HTTP 协议里的请求方,即 User Agent;服务器是 HTTP 协议里的应答方,常用的有 Apache 和 Nginx;CDN 位于浏览器和服务器之间,主要起到缓存…...
东南大学研究生上学期英语期末总结
写在前面 作者:夏日 博客地址:https://blog.csdn.net/zss192 本文为东南大学研究生英语上学期期末总结,内容为根据老师所发 PPT 总结得来 相关资料: 点我查看 题型说明 Module 1 International Conference 50% 题型范围&am…...
leaflet 删除所有的marker图层,保留其他图层(085)
第085个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet项目中清除所有的marker图层,保留其他图层,详情请参考源代码。这里面主要用到了(layer instanceof L.Marker ,注意 L.Marker中Marker首字母要大写。 直接复制下面的 vue+leaflet源代码,操作2分钟即可运行…...
双因素方差分析全流程
上篇文章讲述了“单因素方差分析全流程总结”,单因素方差分析只是考虑了一个自变量(定类)与一个因变量(定量)之间的关系,但是在实际问题研究中可能研究两个或者几个因素与因变量之间的关系,例如…...
微信公众号抽奖怎么做_分享微信抽奖小程序制作的好处
在H5游戏中,抽奖是最受消费者喜爱的模式之一。将H5微信抽奖活动结合到营销中,可以带来意想不到的效果,带流量和曝光率,所以许多企业也会在做活动时添加上不同类型的H5微信抽奖活动。编辑那么,新手怎么搭建微信抽奖活动…...
逻辑回归—分类问题的操作顺序
对于二元分类问题来说,分类的结果和数据的特征之间仍呈现相关关系,但是y的值不再是连续的,是0~1的跃迁。但是在这个过程中,什么仍然是连续的呢?”是概率,概率是逐渐升高的,当达到一个…...
查询服务器tns文件路径,oracle数据库tns配置方法详解
查询服务器tns文件路径,oracle数据库tns配置方法详解 TNS简要介绍与应用 Oracle中TNS的完整定义:transparence Network Substrate透明网络底层, 监听服务是它重要的一部分,不是全部,不要把TNS当作只是监听器。 TNS是Oracle Net…...
【数据结构】链表
目录 数据结构之链表:: SList.h 1.链表的概念及结构 2.链表的分类 SList.c 3.动态申请一个结点 4.单链表打印 5.单链表销毁 6.单链表头插 7.单链表头删 8.单链表尾插 9.单链表尾删 10.单链表查找 11.单链表在pos之前插入…...
一文讲明Hystrix熔断器
前言 解决问题: 主要防止服务器集群发生雪崩, 起到对服务器的保护作用 GitHub地址:https://github.com/Netflix/Hystrix/wiki 1 Hystrix是什么 1.1 分布式系统面临的问题 复杂分布式体系结构中的应用程序有数十个依赖关系,每个依赖关系在某些时候将不…...
第12篇:Java类核心构成要素分析
目录 1、Java类构成要素 1.1 如何定义类 1.2 如何定义变量 1.2.1 类变量 1.2.2 实例变量...
记一次 .NET 某医保平台 CPU 爆高分析
一:背景 1. 讲故事 一直在追这个系列的朋友应该能感受到,我给这个行业中无数的陌生人分析过各种dump,终于在上周有位老同学找到我,还是个大妹子,必须有求必应 😁😁😁。 妹子公司的…...
滤波算法 | 无迹卡尔曼滤波(UKF)算法及其MATLAB实现
目录简介UKF滤波滤波流程和公式MATLAB程序结论简介 本文接着分享位姿跟踪和滤波算法中用到的一些常用程序,希望为后来者减少一些基础性内容的工作时间。以往分享总结见文章:位姿跟踪 | 相关内容目录和链接总结(不断更新中~~~) 本…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
