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

【算法-动态规划】最长公共子序列

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

        • 1.题目
        • 2.示例
        • 3.题解

1.题目

给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 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 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙

img

相关文章:

【算法-动态规划】最长公共子序列

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…...

区块链游戏的开发流程

链游&#xff08;Blockchain Games&#xff09;的开发流程与传统游戏开发有许多相似之处&#xff0c;但它涉及到区块链技术的集成和智能合约的开发。以下是链游的一般开发流程&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&…...

目标检测网络系列——YOLO V2

文章目录 YOLO9000better,更准batch Normalization高分辨率的训练使用anchor锚框尺寸的选择——聚类锚框集成改进——直接预测bounding box细粒度的特征图——passthrough layer多尺度训练数据集比对实验VOC 2007VOC 2012COCOFaster,更快网络模型——Darknet19训练方法Strong…...

15. Java反射和注解

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

pdf处理工具 Enfocus PitStop Pro 2022 中文 for mac

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

微信小程序入门开发教程

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《微信小程序开发实战》。&#x1f3af;&#x1f3a…...

php函数

1. strstr() 返回a在b中的第一个位置 2.substr() 截取字符串 3.PHP字符串函数parse_str(将字符串解析成多个变量)-CSDN博客 4.explode() 字符串分割为数组 5.trim&#xff08;&#xff09; 1.去除字符串两边的 空白字符 2.去除指定字符 6.extract()函数从数组里…...

3.3 封装性

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

Redis魔法:点燃分布式锁的奇妙实现

分布式锁是一种用于在分布式系统中控制对共享资源的访问的锁。它与传统的单机锁不同&#xff0c;因为它需要在多个节点之间协调以确保互斥访问。 本文将介绍什么是分布式锁&#xff0c;以及使用Redis实现分布式锁的几种方案。 一、前言 了解分布式锁之前&#xff0c;需要先了…...

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曲线划分 一般来说&#xff0c;实轴处的截获表示体电阻(Rb)&#xff0c;它反映了电解质&#xff0c;隔膜和电极的电导率。高频区的半圆对应于…...

Sprint framework Day07:注解结合 xml 配置

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

LiveGBS流媒体平台GB/T28181功能-国标流媒体服务同时兼容内网收流外网收流多网段设备收流

LiveGBS流媒体平台GB/T28181功能-国标流媒体服务同时兼容内网收流外网收流多网段设备收流 1、背景2、设备接入播放2.1、查看通道2.2、直播播放 3、默认收流地址配置4、其它网络设备收流配置5、搭建GB28181视频直播平台 1、背景 服务器部署的时候&#xff0c;可能有多个网卡多个…...

js题解(四)

文章目录 批量改变对象的属性判断是否包含数字判断是否符合指定格式 批量改变对象的属性 给定一个构造函数 constructor&#xff0c;请完成 alterObjects 方法&#xff0c;将 constructor 的所有实例的 greeting 属性指向给定的 greeting 变量。 function alterObjects(const…...

如何进行大数运算和高精度计算?

大数运算和高精度计算是在计算机编程中常见的需求&#xff0c;尤其是当处理大整数、分数、复数、浮点数等需要更多位数的数据时。在C语言中&#xff0c;由于原生的数据类型有限&#xff0c;您需要使用自定义的数据结构和算法来执行大数运算和高精度计算。在本文中&#xff0c;我…...

身份证读卡器跟OCR有何区别?哪个好?

二代身份证读卡器&#xff08;以下简称读卡器&#xff09;和OCR&#xff08;光学字符识别&#xff09;是两种常见的身份证信息获取技术&#xff0c;它们在原理、功能和应用方面存在一些区别。下面将详细介绍二者的区别并探讨哪个更好。 1. 原理&#xff1a; - 读卡器&#xff…...

华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 网络监控神器 bmon

华为云云耀云服务器L实例评测 &#xff5c; 实例评测使用之硬件参数评测&#xff1a;华为云云耀云服务器下的 Linux 网络监控神器 bmon 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什…...

C++ 设计模式 —— 组合模式

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

华为云Stack的学习(九)

十、华为云Stack灾备服务介绍 1.云硬盘备份VBS 云硬盘备份服务&#xff08;VBS&#xff0c;Volume Backup Service&#xff09;可为云硬盘&#xff08;EVS&#xff0c;Elastic Volume Service&#xff09;创建备份&#xff0c;利用备份数据恢复云硬盘&#xff0c;最大限度保障…...

Flink中jobmanager、taskmanager、slot、task、subtask、Parallelism的概念

场景 一个工厂有三个车间每个车间两条生产线 生产流程如下 原料->加工->过滤->分类->美化->包装->下线 JobManager&#xff1a;工厂 在上述场景中&#xff0c;工厂就是jobManager&#xff0c;负责协调、调度和监控整个生产过程 TaskManager&#xff1a;车间…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多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评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

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