当前位置: 首页 > 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;车间…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 public class VariableDemo {publi…...

【JavaEE】万字详解HTTP协议

HTTP是什么&#xff1f;-----互联网的“快递小哥” 想象我们正在网上购物&#xff1a;打开淘宝APP&#xff0c;搜索“蓝牙耳机”&#xff0c;点击商品图片&#xff0c;然后下单付款。这一系列操作背后&#xff0c;其实有一个看不见的“快递小哥”在帮我们传递信息&#xff0c;…...