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

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 判断子序列

题意理解&#xff1a; 给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;例如&#xff0c;"ace"是"abcde&quo…...

基于微信小程序的校园跑腿系统的研究与实现,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

VTK Python PyQt 监听键盘 控制 Actor 移动 变色

KeyPressInteractorStyle 在vtk 中有时我们需要监听 键盘或鼠标做一些事&#xff1b; 1. 创建 Actor&#xff1b; Sphere vtk.vtkSphereSource() Sphere.SetRadius(10)mapper vtk.vtkPolyDataMapper() mapper.SetInputConnection(Sphere.GetOutputPort()) actor vtk.vtkAc…...

力扣 第 124 场双周赛 解题报告 | 珂学家 | 非常规区间合并

前言 整体评价 T4的dp解法没想到&#xff0c;走了一条"不归路", 这个区间合并解很特殊&#xff0c;它是带状态的&#xff0c;而且最终的正解也是基于WA的case&#xff0c;慢慢理清的。 真心不容易&#xff0c;太难了。 T1. 相同分数的最大操作数目 I 思路: 模拟 c…...

2024年华为OD机试真题-生成哈夫曼树-Java-OD统一考试(C卷)

题目描述: 给定长度为n的无序的数字数组,每个数字代表二叉树的叶子节点的权值,数字数组的值均大于等于1。请完成一个函数,根据输入的数字数组,生成哈夫曼树,并将哈夫曼树按照中序遍历输出。 为了保证输出的二叉树中序遍历结果统一,增加以下限制:二叉树节点中,左节点权…...

【实战】二、Jest难点进阶(二) —— 前端要学的测试课 从Jest入门到TDD BDD双实战(六)

文章目录 一、Jest 前端自动化测试框架基础入门二、Jest难点进阶2.mock 深入学习 学习内容来源&#xff1a;Jest入门到TDD/BDD双实战_前端要学的测试课 相对原教程&#xff0c;我在学习开始时&#xff08;2023.08&#xff09;采用的是当前最新版本&#xff1a; 项版本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磁贴案例 &#x1f4cd;基于STM32F103C8T6 LL库驱动版本&#xff1a;https://gitee.com/chcsx/platform-test/tree/master/MDK-ARM&#x1f3ac;视频演示&#xff1a; WouoUI移植磁贴案例&#xff0c;新增确认弹窗 &#x1f…...

手机如何改自己的ip地址

在现如今的数码时代&#xff0c;手机已经成为人们生活中不可或缺的一部分。然而&#xff0c;有时候我们可能需要改变手机的IP地址来实现一些特定的需求。本文将向大家介绍如何改变手机的IP地址&#xff0c;帮助大家更好地应对各种网络问题。 更改手机IP地址的原因&#xff1a;…...

ajax函数库axios基本使用

ajax函数库Axios基本使用 简介&#xff1a;Axios 对原生的Ajax进行了封装&#xff0c;简化书写&#xff0c;快速开发。 官网&#xff1a;https://www.axios-http.cn/ Axios使用步骤 引入Axios的js文件(参考官网)使用Axios发送请求,获取相应结果 <script src"https:…...

【nginx实践连载-4】彻底卸载Nginx(Ubuntu)

步骤1&#xff1a;停止Nginx服务 打开终端&#xff08;Terminal&#xff09;。停止Nginx服务&#xff1a;sudo systemctl stop nginx步骤2&#xff1a;卸载Nginx软件包 运行以下命令卸载Nginx软件包&#xff1a;sudo apt purge nginx nginx-common nginx-core步骤3&#xff1…...

究极小白如何自己搭建一个自动发卡网站-独角数卡

首页 | 十画IOSID​shihuaid.cn/​编辑 如果你也是跟我一样,什么都不懂,也想要搭建一个自己的自动发卡网站,可以参考一下我的步骤,不难,主要就是细心,一步步来一定成功!! 独角数卡: 举个例子:独角数卡就是一个店面,而且里面帮你装修好了,而你要做的就是把开店之…...

Java_方法(重载方法签名等详解)

在之前我们学习C语言时&#xff0c;当我们想要重复使用某段代码的功能时&#xff0c;我们会将这段代码定义为一个函数&#xff0c;而在java中我们把这段重复使用的代码叫做方法。 方法的定义 类体的内容分为变量的声明和方法的定义&#xff0c;方法的定义包括两部分&#xff1…...

VQ35 评论替换和去除(char_length()和replace函数的使用)

代码 select id ,replace(comment,&#xff0c;,) as comment from comment_detail where char_length(comment)>3知识点 要注意替换的是中文逗号 由于题目说的是汉字长度大于3&#xff0c;所以这里就要使用char_length()而不是length() char_length()&#xff1a;单位为字…...

【MySQL】学习多表查询和笛卡尔积

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-N8PeTKG6uLu4bJuM {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…...

RabbitMQ实现延迟消息的方式-死信队列、延迟队列和惰性队列

当一条消息因为一些原因无法被成功消费&#xff0c;那么这这条消息就叫做死信&#xff0c;如果包含死信的队列配置了dead-letter-exchange属性指定了一个交换机&#xff0c;队列中的死信都会投递到这个交换机内&#xff0c;这个交换机就叫死信交换机&#xff0c;死信交换机再绑…...

【运维测试】测试理论+工具总结笔记第1篇:测试理论的主要内容(已分享,附代码)

本系列文章md笔记&#xff08;已分享&#xff09;主要讨论测试理论测试工具相关知识。Python测试理论的主要内容&#xff0c;掌握软件测试的基本流程&#xff0c;知道软件测试的V和W模型的优缺点&#xff0c;掌握测试用例设计的要素&#xff0c;掌握等价类划分法、边界值法、因…...

【C语言】实现队列

目录 &#xff08;一&#xff09;队列 &#xff08;二&#xff09;头文件 &#xff08;三&#xff09; 功能实现 &#xff08;1&#xff09;初始化 &#xff08;2&#xff09; 销毁队列 &#xff08;3&#xff09; 入队 &#xff08;4&#xff09;出队 &#xff08;5&a…...

【友塔笔试面试复盘】八边形取反问题

问题&#xff1a;一个八边形每条边都是0&#xff0c;现在有取反操作&#xff0c;选择一条边取反会同时把当前边和2个邻边取反&#xff08;如果是0变为1&#xff0c;如果是1变为0&#xff09; 现在问你怎么取反能使得八条边都变为1. 当时陷入了暴力递归漩涡&#xff0c;给出一个…...

GB 18585-2023 壁纸中有害物质限量

壁纸/墙布因其色彩多样&#xff0c;图案丰富&#xff0c;施工方便&#xff0c;价格便宜等多种优势&#xff0c;广泛应用于室内装修材料&#xff0c;在国内&#xff0c;日本&#xff0c;欧美等地区非常普及。 GB 18585-2023壁纸中有害物质限量测试项目&#xff1a; 测试项目 测…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...