Leetcode 392 判断子序列
题意理解:
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,
"ace"是"abcde"的一个子序列,而"aec"不是)。即判断s和t是否存在一个最长公共子序列,且该最长公共子序列==s
这里采用一个动态规划的思路求解最长公共子序列,其长度==s.size
解题思路:
(1) 定义dp数组
定义二维dp数组,dp[i][j]表示s第i个元素前,t第j个元素前最长公共子序列。
i,j指示的是元素之间的位置
其i属于[0,s.size+1], j属于[0,t.size+1]
(2)初始化
dp[0][j]和dp[i][0]表示第一行第一列,其都是用一个空数组和一个非空数组求其最长公共给子序列,所以全部初始化为0.
其余元素初始化为0,后续操作会被覆盖掉。
(3)递推公式
if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1
else dp[i][j]=max(dp[i][j-1],dp[i-1][j])
(4)返回
if(dp[s.size-1][t.size-1]==s.size) return true;
else return false;
1.动态规划
public boolean isSubsequence(String s, String t) {int[][] dp=new int[s.length()+1][t.length()+1];for(int i=0;i<s.length();i++){Arrays.fill(dp[i],0);}for(int i=1;i<=s.length();i++){for(int j=1;j<=t.length();j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}if(dp[s.length()][t.length()]==s.length()) return true;return false;}
2.分析
时间复杂度:O(n^2)
空间复杂度:O(n^2)
相关文章:
Leetcode 392 判断子序列
题意理解: 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde&quo…...
基于微信小程序的校园跑腿系统的研究与实现,附源码
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
VTK Python PyQt 监听键盘 控制 Actor 移动 变色
KeyPressInteractorStyle 在vtk 中有时我们需要监听 键盘或鼠标做一些事; 1. 创建 Actor; Sphere vtk.vtkSphereSource() Sphere.SetRadius(10)mapper vtk.vtkPolyDataMapper() mapper.SetInputConnection(Sphere.GetOutputPort()) actor vtk.vtkAc…...
力扣 第 124 场双周赛 解题报告 | 珂学家 | 非常规区间合并
前言 整体评价 T4的dp解法没想到,走了一条"不归路", 这个区间合并解很特殊,它是带状态的,而且最终的正解也是基于WA的case,慢慢理清的。 真心不容易,太难了。 T1. 相同分数的最大操作数目 I 思路: 模拟 c…...
2024年华为OD机试真题-生成哈夫曼树-Java-OD统一考试(C卷)
题目描述: 给定长度为n的无序的数字数组,每个数字代表二叉树的叶子节点的权值,数字数组的值均大于等于1。请完成一个函数,根据输入的数字数组,生成哈夫曼树,并将哈夫曼树按照中序遍历输出。 为了保证输出的二叉树中序遍历结果统一,增加以下限制:二叉树节点中,左节点权…...
【实战】二、Jest难点进阶(二) —— 前端要学的测试课 从Jest入门到TDD BDD双实战(六)
文章目录 一、Jest 前端自动化测试框架基础入门二、Jest难点进阶2.mock 深入学习 学习内容来源:Jest入门到TDD/BDD双实战_前端要学的测试课 相对原教程,我在学习开始时(2023.08)采用的是当前最新版本: 项版本babel/co…...
(一)【Jmeter】JDK及Jmeter的安装部署及简单配置
JDK的安装和环境变量配置 对于Linux、Mac和Windows系统,JDK的安装和环境变量配置方法略有不同。以下是针对这三种系统的详细步骤: 对于Linux系统: 下载适合Linux系统的JDK安装包,可以选择32位或64位的版本。 将JDK的安装包放置在服务器下,创建一个新的文件夹来存储JDK,…...
HAL/LL/STD STM32 U8g2库 +I2C SSD1306/sh1106 WouoUI磁贴案例
HAL/LL/STD STM32 U8g2库 I2C SSD1306/sh1106 WouoUI磁贴案例 📍基于STM32F103C8T6 LL库驱动版本:https://gitee.com/chcsx/platform-test/tree/master/MDK-ARM🎬视频演示: WouoUI移植磁贴案例,新增确认弹窗 …...
手机如何改自己的ip地址
在现如今的数码时代,手机已经成为人们生活中不可或缺的一部分。然而,有时候我们可能需要改变手机的IP地址来实现一些特定的需求。本文将向大家介绍如何改变手机的IP地址,帮助大家更好地应对各种网络问题。 更改手机IP地址的原因:…...
ajax函数库axios基本使用
ajax函数库Axios基本使用 简介:Axios 对原生的Ajax进行了封装,简化书写,快速开发。 官网:https://www.axios-http.cn/ Axios使用步骤 引入Axios的js文件(参考官网)使用Axios发送请求,获取相应结果 <script src"https:…...
【nginx实践连载-4】彻底卸载Nginx(Ubuntu)
步骤1:停止Nginx服务 打开终端(Terminal)。停止Nginx服务:sudo systemctl stop nginx步骤2:卸载Nginx软件包 运行以下命令卸载Nginx软件包:sudo apt purge nginx nginx-common nginx-core步骤3࿱…...
究极小白如何自己搭建一个自动发卡网站-独角数卡
首页 | 十画IOSIDshihuaid.cn/编辑 如果你也是跟我一样,什么都不懂,也想要搭建一个自己的自动发卡网站,可以参考一下我的步骤,不难,主要就是细心,一步步来一定成功!! 独角数卡: 举个例子:独角数卡就是一个店面,而且里面帮你装修好了,而你要做的就是把开店之…...
Java_方法(重载方法签名等详解)
在之前我们学习C语言时,当我们想要重复使用某段代码的功能时,我们会将这段代码定义为一个函数,而在java中我们把这段重复使用的代码叫做方法。 方法的定义 类体的内容分为变量的声明和方法的定义,方法的定义包括两部分࿱…...
VQ35 评论替换和去除(char_length()和replace函数的使用)
代码 select id ,replace(comment,,,) as comment from comment_detail where char_length(comment)>3知识点 要注意替换的是中文逗号 由于题目说的是汉字长度大于3,所以这里就要使用char_length()而不是length() char_length():单位为字…...
【MySQL】学习多表查询和笛卡尔积
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-N8PeTKG6uLu4bJuM {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…...
RabbitMQ实现延迟消息的方式-死信队列、延迟队列和惰性队列
当一条消息因为一些原因无法被成功消费,那么这这条消息就叫做死信,如果包含死信的队列配置了dead-letter-exchange属性指定了一个交换机,队列中的死信都会投递到这个交换机内,这个交换机就叫死信交换机,死信交换机再绑…...
【运维测试】测试理论+工具总结笔记第1篇:测试理论的主要内容(已分享,附代码)
本系列文章md笔记(已分享)主要讨论测试理论测试工具相关知识。Python测试理论的主要内容,掌握软件测试的基本流程,知道软件测试的V和W模型的优缺点,掌握测试用例设计的要素,掌握等价类划分法、边界值法、因…...
【C语言】实现队列
目录 (一)队列 (二)头文件 (三) 功能实现 (1)初始化 (2) 销毁队列 (3) 入队 (4)出队 (5&a…...
【友塔笔试面试复盘】八边形取反问题
问题:一个八边形每条边都是0,现在有取反操作,选择一条边取反会同时把当前边和2个邻边取反(如果是0变为1,如果是1变为0) 现在问你怎么取反能使得八条边都变为1. 当时陷入了暴力递归漩涡,给出一个…...
GB 18585-2023 壁纸中有害物质限量
壁纸/墙布因其色彩多样,图案丰富,施工方便,价格便宜等多种优势,广泛应用于室内装修材料,在国内,日本,欧美等地区非常普及。 GB 18585-2023壁纸中有害物质限量测试项目: 测试项目 测…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
goreplay
1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具,可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长,测试它所需的工作量也会呈指数级增长。GoRepl…...
