【算法-动态规划】最长公共子序列
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
- 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
- 导航
- 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
- 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
- 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
- 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
- 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂
非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨
博客目录
- 1.题目
- 2.示例
- 3.题解
1.题目
给定两个字符串
text1
和text2
,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回0
。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
- 例如,
"ace"
是"abcde"
的子序列,但"aec"
不是"abcde"
的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
2.示例
示例 1:
输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。
示例 2:
输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。
示例 3:
输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。
3.题解
public class LCSubsequence {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {char a = text1.charAt(i - 1);for (int j = 1; j < n + 1; j++) {char b = text2.charAt(j - 1);if (a == b) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);}}}print(dp, text2, text1);return dp[m][n];}static void print(int[][] dp, String a, String b) {System.out.println("-".repeat(23));Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();System.out.printf(" " + "%2s ".repeat(a.length()) + "%n", array);for (int i = 0; i < b.length(); i++) {int[] d = dp[i + 1];array = Arrays.stream(d).boxed().toArray();System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);}}public static void main(String[] args) {LCSubsequence code = new LCSubsequence();System.out.println(code.longestCommonSubsequence("abcde", "ace"));System.out.println(code.longestCommonSubsequence("ba", "yby"));}
}
觉得有用的话点个赞
👍🏻
呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍
🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙
相关文章:

【算法-动态规划】最长公共子序列
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…...

区块链游戏的开发流程
链游(Blockchain Games)的开发流程与传统游戏开发有许多相似之处,但它涉及到区块链技术的集成和智能合约的开发。以下是链游的一般开发流程,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司&…...
目标检测网络系列——YOLO V2
文章目录 YOLO9000better,更准batch Normalization高分辨率的训练使用anchor锚框尺寸的选择——聚类锚框集成改进——直接预测bounding box细粒度的特征图——passthrough layer多尺度训练数据集比对实验VOC 2007VOC 2012COCOFaster,更快网络模型——Darknet19训练方法Strong…...

15. Java反射和注解
Java —— 反射和注解 1. 反射2. 注解 1. 反射 动态语言:变量的类型和属性可以在运行时动态确定,而不需要在编译时指定 常见动态语言:Python,JavaScript,Ruby,PHP,Perl;常见静态语言…...

pdf处理工具 Enfocus PitStop Pro 2022 中文 for mac
Enfocus PitStop Pro 2022是一款专业的PDF预检和编辑软件,旨在帮助用户提高生产效率、确保印刷品质量并减少错误。以下是该软件的一些特色功能: PDF预检。PitStop Pro可以自动检测和修复常见的PDF文件问题,如缺失字体、图像分辨率低、颜色空…...

微信小程序入门开发教程
🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是Java方文山,一个在CSDN分享笔记的博主。📚📚 🌟推荐给大家我的专栏《微信小程序开发实战》。🎯Ἲ…...
php函数
1. strstr() 返回a在b中的第一个位置 2.substr() 截取字符串 3.PHP字符串函数parse_str(将字符串解析成多个变量)-CSDN博客 4.explode() 字符串分割为数组 5.trim() 1.去除字符串两边的 空白字符 2.去除指定字符 6.extract()函数从数组里…...

3.3 封装性
思维导图: 3.3.1 为什么要封装 ### 3.3.1 为什么要封装 **封装**,在Java的面向对象编程中,是一个核心的思想。它主要是为了保护对象的状态不被外部随意修改,确保数据的完整性和安全性。 #### **核心思想:** - 保护…...

Redis魔法:点燃分布式锁的奇妙实现
分布式锁是一种用于在分布式系统中控制对共享资源的访问的锁。它与传统的单机锁不同,因为它需要在多个节点之间协调以确保互斥访问。 本文将介绍什么是分布式锁,以及使用Redis实现分布式锁的几种方案。 一、前言 了解分布式锁之前,需要先了…...
iOS 项目避坑:多个分类中方法重复实现检测
#前言 在项目中,我们经常会使用分类 -> category。category在实际项目中一般有两个左右:1.给已有class增加方法,扩充起能力、2.将代码打散到多个文件中,避免因为一个类过于复杂而导致代码篇幅过长(应用于viewController中很好用) 但是 category 也有很多弊端~ **首…...

【003】EIS数据分析_#LIB
EIS数据分析 1. EIS测试及数据获取2. EIS数据分析2.1 EIS曲线划分 1. EIS测试及数据获取 点击查看往期介绍 2. EIS数据分析 2.1 EIS曲线划分 一般来说,实轴处的截获表示体电阻(Rb),它反映了电解质,隔膜和电极的电导率。高频区的半圆对应于…...

Sprint framework Day07:注解结合 xml 配置
前言 Spring注解结合XML配置是指在Spring应用中,使用注解和XML配置的方式来进行Bean的定义、依赖注入和其他配置。这种方式可以充分利用Spring框架的注解和XML配置两种不同的配置方式的特点。 在Spring框架中,我们可以使用注解来定义Bean,如…...

LiveGBS流媒体平台GB/T28181功能-国标流媒体服务同时兼容内网收流外网收流多网段设备收流
LiveGBS流媒体平台GB/T28181功能-国标流媒体服务同时兼容内网收流外网收流多网段设备收流 1、背景2、设备接入播放2.1、查看通道2.2、直播播放 3、默认收流地址配置4、其它网络设备收流配置5、搭建GB28181视频直播平台 1、背景 服务器部署的时候,可能有多个网卡多个…...
js题解(四)
文章目录 批量改变对象的属性判断是否包含数字判断是否符合指定格式 批量改变对象的属性 给定一个构造函数 constructor,请完成 alterObjects 方法,将 constructor 的所有实例的 greeting 属性指向给定的 greeting 变量。 function alterObjects(const…...
如何进行大数运算和高精度计算?
大数运算和高精度计算是在计算机编程中常见的需求,尤其是当处理大整数、分数、复数、浮点数等需要更多位数的数据时。在C语言中,由于原生的数据类型有限,您需要使用自定义的数据结构和算法来执行大数运算和高精度计算。在本文中,我…...

身份证读卡器跟OCR有何区别?哪个好?
二代身份证读卡器(以下简称读卡器)和OCR(光学字符识别)是两种常见的身份证信息获取技术,它们在原理、功能和应用方面存在一些区别。下面将详细介绍二者的区别并探讨哪个更好。 1. 原理: - 读卡器ÿ…...

华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 网络监控神器 bmon
华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 网络监控神器 bmon 介绍华为云云耀云服务器 华为云云耀云服务器 (目前已经全新升级为 华为云云耀云服务器L实例) 华为云云耀云服务器是什…...

C++ 设计模式 —— 组合模式
C 设计模式 —— 组合模式 0. 引用连接 本文主要的思路和代码,来自于对以下连接的学习和实现: 组合模式 1. 引言 1.1 什么是组合模式? 组合模式的定义组合模式的作用 组合模式是一种行为型设计模式,它将对象组合成树形结构以…...

华为云Stack的学习(九)
十、华为云Stack灾备服务介绍 1.云硬盘备份VBS 云硬盘备份服务(VBS,Volume Backup Service)可为云硬盘(EVS,Elastic Volume Service)创建备份,利用备份数据恢复云硬盘,最大限度保障…...
Flink中jobmanager、taskmanager、slot、task、subtask、Parallelism的概念
场景 一个工厂有三个车间每个车间两条生产线 生产流程如下 原料->加工->过滤->分类->美化->包装->下线 JobManager:工厂 在上述场景中,工厂就是jobManager,负责协调、调度和监控整个生产过程 TaskManager:车间…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...

windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
boost::filesystem::path文件路径使用详解和示例
boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类,封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解,包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...

边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...