LeetCode1143最长公共子序列

题目描述

  给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解析

  建立两个长度的动态规划数组,如果对应的字符相等,那么当前位置的最大值等于它斜上方的值加一,否则就是上方和左边的最大值。

class Solution {public int longestCommonSubsequence(String text1, String text2) {int len1 = text1.length();int len2 = text2.length();int[][] maxLen = new int[len1][len2];boolean equal = text1.charAt(0) == text2.charAt(0);// 初始化第一行for(int i = 0; i < len2; i++) {if(equal) {maxLen[0][i] = 1;}else {if(text1.charAt(0) == text2.charAt(i)) {equal = true;maxLen[0][i] = 1;}}}// 初始化第一列equal = text1.charAt(0) == text2.charAt(0);for(int i = 0; i < len1; i++) {if(equal) {maxLen[i][0] = 1;}else {if(text1.charAt(i) == text2.charAt(0)) {equal = true;maxLen[i][0] = 1;}}}for(int i = 1; i < len1; i++) {for(int j = 1; j < len2; j++) {int curMax = maxLen[i][j - 1];int preMax = text1.charAt(i) == text2.charAt(j) ? maxLen[i - 1][j - 1] + 1: maxLen[i - 1][j];int Max = Math.max(curMax, preMax);maxLen[i][j] = Math.min(Math.min(i + 1, j + 1), Max);}}return maxLen[len1 - 1][len2 - 1];}
}

  还可以进行优化,可以将数组的长度多建立一个,就不用初始化了,另外字符数组比直接使用string会快一点。

public int longestCommonSubsequence(String text1, String text2) {char[] t1 = text1.toCharArray();char[] t2 = text2.toCharArray();int length1 = t1.length;int length2 = t2.length;int[][] dp = new int[length1+1][length2+1];for (int i = 1; i < length1 +1; i++) {for (int j = 1; j < length2 +1; j++) {if (t1[i-1] == t2[j-1]){dp[i][j] = 1+ dp[i-1][j-1];}else {dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[length1][length2];}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/346194.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

redis windos修复版本

遇到的问题: Django的channel插件连接安装在windows上的redis报错: unknown command BZPOPMIN, channels-redis版本和redis不兼容导致.解决方案: 更新Redis版本. 微软官方维护的 Redishttps://github.com/microsoftarchive/redis/releases 2016年后就不更新了, 版本停留在了3.x…

学生信息管理(C语言)

学生信息管理 (1)问题描述 学生信息包括:学号,姓名,年龄,性别,出生年月,地址,电话,E-mail等。试设计一学生信息管理系统,使之能提供以下功能: 系统以菜单方式工作学生信息录入功能(学生信息用文件保存)---输入学生信息浏览功能---输出查询、排序功能---算法1、…

前后端实现文件上传进度条-实时进度

后端接口代码&#xff1a; PostMapping("/upload")public ResponseEntity<String> handleFileUpload(RequestParam("file") MultipartFile file) {try {// 获取文件名String fileName file.getOriginalFilename();// 创建上传目标路径Path targetPa…

CentOS7 MySQL5.7.35主从 不停机搭建 以及配置

如需安装MySQL&#xff0c;参照MySQL 5.7.35 安装教程 https://blog.csdn.net/CsethCRM/article/details/119418841一、主&从 环境信息准备 1.1.查看硬盘信息&#xff0c;确保磁盘够用&#xff08;主&从&#xff09; df -h1.2.查看内存信息 &#xff08;主&从&am…

C++ 贪心算法——跳跃游戏、划分字母区间

一&#xff1a;跳跃游戏 55. 跳跃游戏 题目描述&#xff1a;给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1…

解决阿里云的端口添加安全组仍然无法扫描到

发现用线上的网站扫不到这个端口&#xff0c;这个端口关了&#xff0c;但是没有更详细信息了 我用nmap扫了一下我的这个端口&#xff0c;发现主机是活跃的&#xff0c;但是有防火墙&#xff0c;我们列出云服务器上面的这个防火墙list&#xff0c;发现确实没有5566端口 参考&a…

Mac环境下,简单反编译APK

一、下载jadx包 https://github.com/skylot/jadx/releases/tag/v1.4.7 下载里面的这个&#xff1a;下载后&#xff0c;找个干净的目录解压&#xff0c;我是放在Downloads下面 二、安装及启动 下载和解压 jadx&#xff1a; 下载 jadx-1.4.7.zip 压缩包。将其解压到你希望的目…

内网安全--隧道技术代理技术

注:本文仅做技术交流,请勿非法破坏... 目录 项目: 1-Ngrok 用法 2-Frp 用法 3-Nps 用法 4-Spp 用法 工具: windows下: Proxifier(推荐~) Sockscap ccproxy Linux下: Proxychains 用法 http://t.csdnimg.cn/88Ew7 隧道技术&#xff1a;解决不出网协议上线的问…

**《Linux/Unix系统编程手册》读书笔记24章**

D 24章 进程的创建 425 24.1 fork()、exit()、wait()以及execve()的简介 425 . 系统调用fork()允许父进程创建子进程 . 库函数exit(status)终止进程&#xff0c;将进程占用的所有资源归还内核&#xff0c;交其进行再次分配。库函数exit()位于系统调用_exit()之上。在调用fo…

“RabbitMQ入门指南:从入门到起飞,这一篇就够!打造高效消息通信系统的第一步“。

1.前言 RabbitMQ是一个开源的消息代理软件&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;的标准&#xff0c;并用Erlang语言编写。作为消息代理&#xff0c;RabbitMQ接收、存储和转发消息&#xff0c;帮助应用程序之间实现异步通信。它提供了一个强大而灵活…

Qt开发技术:Q3D图表开发笔记(四):Q3DSurface三维曲面图颜色样式详解、Demo以及代码详解

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/139424086 各位读者&#xff0c;知识无穷而人力有穷&#xff0c;要么改需求&#xff0c;要么找专业人士&#xff0c;要么自己研究 红胖子网络科技博…

PawSQL优化 | 分页查询太慢?别忘了投影下推

​在进行数据库应用开发中&#xff0c;分页查询是一项非常常见而又至关重要的任务。但你是否曾因为需要获取总记录数的性能而感到头疼&#xff1f;现在&#xff0c;让PawSQL的投影下推优化来帮你轻松解决这一问题&#xff01;本文以TPCH的Q12为案例进行验证&#xff0c;经过Paw…

Redisson分布式锁原理解析

前言 首先Redis执行命令是单线程的&#xff0c;所以可以利用Redis实现分布式锁&#xff0c;而对于Redis单线程的问题&#xff0c;是其线程模型的问题&#xff0c;本篇重点是对目前流行的工具Redisson怎么去实现的分布式锁进行深入理解&#xff1b;开始之前&#xff0c;我们可以…

Vmess协议是什么意思? VLESS与VMess有什么区别?

VMess 是一个基于 TCP 的加密传输协议&#xff0c;所有数据使用 TCP 传输&#xff0c;是由 V2Ray 原创并使用于 V2Ray 的加密传输协议&#xff0c;它分为入站和出站两部分&#xff0c;其作用是帮助客户端跟服务器之间建立通信。在 V2Ray 上客户端与服务器的通信主要是通过 VMes…

ThinkPHP发邮件配置教程?群发功能安全吗?

ThinkPHP发邮件的注意事项&#xff1f;如何优化邮件发送的性能&#xff1f; 无论是用户注册、密码重置还是消息提醒&#xff0c;发送邮件都是一个常见的需求。AokSend将详细介绍如何在ThinkPHP框架中配置和发送邮件&#xff0c;帮助开发者轻松实现邮件功能。 ThinkPHP发邮件&…

43【PS 作图】颜色速途

1 通过PS让画面细节模糊&#xff0c;避免被过多的颜色干扰 2 分析画面的颜色 3 作图 参考网站&#xff1a; 色感不好要怎么提升呢&#xff1f;分享一下我是怎么练习色感的&#xff01;_哔哩哔哩_bilibili https://www.bilibili.com/video/BV1h1421Z76p/?spm_id_from333.1007.…

【Python教程】3-控制流、循环结构与简单字符串操作

在整理自己的笔记的时候发现了当年学习python时候整理的笔记&#xff0c;稍微整理一下&#xff0c;分享出来&#xff0c;方便记录和查看吧。个人觉得如果想简单了解一名语言或者技术&#xff0c;最简单的方式就是通过菜鸟教程去学习一下。今后会从python开始重新更新&#xff0…

MySQL之查询性能优化(七)

查询性能优化 排序优化 无论如何排序都是一个成本很高的操作&#xff0c;所以从性能角度考虑&#xff0c;应尽可能避免排序或者尽可能避免对大量数据进行排序。前面已经提到了&#xff0c;当不能使用索引生成排序结果的时候&#xff0c;MySQL需要自己进行排序&#xff0c;如果…

人脸考勤项目实训

第一章 Python-----Anaconda安装 文章目录 第一章 Python-----Anaconda安装前言一、Anaconda是什么&#xff1f;二、Anaconda的前世今生二、Windows安装步骤1.官网下载2.安装步骤安装虚拟环境 总结 前言 工欲善其事必先利其器&#xff0c;项目第一步&#xff0c;安装我们的环境…

【Unity UGUI】Screen.safeArea获取异形屏数据失败

Screen.safeArea获取不到异形屏的尺寸位置等数据 检查AndroidManifest.xml文件是否有设置&#xff1a;android:theme"style/UnityThemeSelector"&#xff0c;没有加上即可 android:theme"style/UnityThemeSelector"