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程序结论简介 本文接着分享位姿跟踪和滤波算法中用到的一些常用程序,希望为后来者减少一些基础性内容的工作时间。以往分享总结见文章:位姿跟踪 | 相关内容目录和链接总结(不断更新中~~~) 本…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
