day58 动态规划part15

392. 判断子序列

简单
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

进阶:

如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

难点:这题不就是要求最长公共子序列是否等于s的长度吗?

// 这是我自己写的解法,没用dp,感觉似乎有点傻,其实是一种双指针的思路
class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() > t.length()) return false;

        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if (start >= t.length()) return false;
            for (int j = start; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    start = j + 1;
                    break;
                }
                if (j == t.length() - 1) return false;
            }
        }
        return true;
    }
}
// 动规方法
// 递推公式:可以发现和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的,区别就是 本题 如果删元素一定是字符串t,而 1143.最长公共子序列 是两个字符串都可以删元素。
class Solution {
    public boolean isSubsequence(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();
        if (lenS > lenT) return false;

        int[][] dp = new int[lenT + 1][lenS + 1]; // dp[i][j] 表示分别以i 和 j结尾的字符串相同子序列的长度

        for (int i = 1; i <= lenT; i++) {
            for (int j = 1; j <= lenS; j++) {
                if (t.charAt(i - 1) == s.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]);
                }
            }
        }

        return dp[lenT][lenS] == lenS;
    }
}

115. 不同的子序列

困难

给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 109 + 7 取模。
在这里插入图片描述

在这里插入图片描述

class Solution {
    public int numDistinct(String s, String t) {
        int [][] dp = new int[s.length() + 1][t.length() + 1]; // dp[i][j] 代表 T 前 i 字符串可以由 S j 字符串组成最多个数.
        for (int i = 0; i <= s.length(); i++) {
            dp[i][0] = 1; // 目标字符t为空字符,只要把s全删了就可以组成,所以为1
        }

        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)) { // 如果取出的这个字符相等,那么就等于去掉这两个相等的字符(为了得到前面相等的数量)加上去掉s的一个字符,再和t比较。本质来说,就是取或者不取s.charAt(i - 1)
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else { // 如果取出的这个字符不相等
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

通天星CMSV6 车载定位监控平台 任意文件上传漏洞复现(XVE-2023-23454)

0x01 产品简介 通天星CMSV6车载定位监控平台拥有以位置服务、无线3G/4G视频传输、云存储服务为核心的研发团队,专注于为定位、无线视频终端产品提供平台服务,通天星CMSV6产品覆盖车载录像机、单兵录像机、网络监控摄像机、行驶记录仪等产品的视频综合平台。 0x02 漏洞概述 …

汇编语言第四版-王爽第2章 寄存器

二进制左移四位&#xff0c;相当于四进制左移一位。 debug命令实操&#xff0c;win11不能启动&#xff0c;需要配置文件 Windows64位系统进入debug模式_window10系统64位怎么使用debugger-CSDN博客

DeepL Pro3.1 下载地址及安装教程

DeepL Pro是DeepL公司推出的专业翻译服务。DeepL是一家专注于机器翻译和自然语言处理技术的公司&#xff0c;其翻译引擎被认为在质量和准确性方面表现优秀.DeepL Pro提供了一系列高级功能和服务&#xff0c;以满足专业用户的翻译需求。其中包括&#xff1a; 高质量翻译&#xf…

vue3 视频播放功能整体复盘梳理

回顾工作中对视频的处理&#xff0c;让工作中处理的问题的经验固化成成果&#xff0c;不仅仅是完成任务&#xff0c;还能解答任务的知识点。 遇到的问题 1、如何隐藏下载按钮&#xff1f; video 标签中的controlslist属性是可以用来控制播放器上空间的显示&#xff0c;在原来默…

MySQL数据库高阶语句②

目录 一.子查询与多表查询 1.子查询 2.update子查询 3.多表查询 4.delete子查询 5.exists关键字也用于子查询 6.结果集 二.MySQL视图 1.定义 2.作用场景 3.视图与表的区别与联系 &#xff08;1&#xff09;区别 ①视图是已经编译好的sql语句。而表不是 ②视图没有…

unity 打包安卓错误汇集

Failed to find target with hash string "android-34’ in: D:Pr 他说找不到sdk34level的我用as打开后卸载又重装&#xff0c;最后解决了 我放到Plugins/Android/下面的Java代码没有被编译 这个不知道为什么。我故意把代码写的有问题&#xff0c;会报错那种&#xff…

linux自定义命令

文章目录 1、自定义命令介绍2、自定义命令步骤 (centos7)2.1 新建隐藏目录存放自定义命令脚本文件2.2 将新建的目录配置环境变量2.3 取别名的方式简化已有命令2.4 编写自定义命令脚本 1、自定义命令介绍 不管是linux系统还是windows系统都支持自定义命令&#xff0c;windows端…

MIPI CSI-2 Low Level Protocol解读

一、Low Level Protocol介绍 LLP 是一种面向字节的基于数据包的协议&#xff0c;支持使用短数据包和长数据包格式传输任意数据。为简单起见&#xff0c;本节中的所有示例均为单通道配置。 LLP特性&#xff1a; 传输任意数据&#xff08;与有效载荷无关&#xff09; 8 位字大…

代码随想录第二十五天 | 回溯算法P2 | ● 216● 17

216.组合总和III 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次&#xff0c;组合可以以任何顺序返回。 示例 1: 输入: k 3, n 7 输出…

解决AD使用交互式BOM插件时,插入make点导致显示异常的问题

记得上次写了一篇关于使用这个插件时出现这个问题的解决方法&#xff0c;具体可查看&#xff1a;AD使用交互式BOM插件时应该注意到的一个问题_ad的bom插件-CSDN博客 当时的解决办法就是删除后再运行脚本生成&#xff0c;这些天经过多次实验&#xff0c;发现是当时那个封装有问…

健身房预约管理系统(源码+文档)

健身房预约管理系统&#xff08;小程序、ios、安卓都可部署&#xff09; 文件包含内容程序简要说明含有功能&#xff1a;项目截图客户端首页我的预约登录教练预约时间我的注册页个人资料课程预约课程预约 管理端订单管理团课管理教练管理分类管理用户管理 文件包含内容 1、搭建…

vulnhub靶场之driftingblues-4

一.环境搭建 1.靶场描述 get flags difficulty: easy about vm: tested and exported from virtualbox. dhcp and nested vtx/amdv enabled. you can contact me by email for troubleshooting or questions. This works better with VirtualBox rather than VMware. 2.靶场…

Segger Embedded Studio IDE使用体验——默认的Section和Linker的设置

Segger Embedded Studio IDE使用体验之一——默认的Section和Linker的设置 一、简介二、操作2.1 编译后代码分析2.1.1 符号浏览器2.1.2 读取elf文件和map文件 2.2 调试2.2.1 查看变量2.2.2 设置供电 2.3 运行环境设置2.3.1 编译器2.3.2 汇编器2.3.3 包含其他文件2.3.4 .bss和.d…

【MATLAB源码-第24期】基于matlab的水声通信中海洋噪声的建模仿真,对比不同风速的影响。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 水声通信&#xff1a; 水声通信是一种利用水中传播声波的方式进行信息传递的技术。它在水下环境中被广泛应用&#xff0c;特别是在海洋科学研究、海洋资源勘探、水下军事通信等领域。 1. **传输媒介**&#xff1a;水声通信利…

Postgresql导出数据和结构后再去另外一个Postgresql数据库中导入失败

参考教程&#xff1a; postgresql 在导入建表sql时 遇到错误 &#xff1a;https://blog.csdn.net/weixin_37706944/article/details/132321731 是因为原表定义了自增字段&#xff0c;解决办法&#xff1a; 解决方法&#xff1a; 执行如下sql后再新建表&#xff0c;就可以了 DR…

ngrok 内网穿透使用

title: ngrok 内网穿透使用 search: 2024-02-29 文章目录 背景Windows安装ngrok指令授权ngrok个人用户Authtoken穿透 http 或 https 服务ngrok的代理http指令ngrok获得静态域名指令ngrok的代理ssh指令 背景 这次寒假回家&#xff0c;很无奈&#xff0c;很多东西放在项目组服务…

[Windows]防火墙,出入站规则失效。

场景&#xff1a; 因为具体需要&#xff0c;在内网中&#xff0c;不想别人发现我们的nacos端口8848&#xff0c;因此我们设置了入站规则&#xff0c;特定的ip地址才能访问。但是实际测试中发现并不起作用。。。 经过一番排查得到一下结果。 为什么有些应用绕过了防火墙配置 有…

记录阿里云服务器VNC登录一直显示Login Incorrect的问题

想要尝试通过VNC实例登录&#xff0c;结果一直提示Login Incorrect 怀疑自己忘记密码后&#xff0c;重置了几次密码还是登录不上去 解决&#xff1a; 发现阿里云把我小键盘的 ""识别为了 “” 号 但是主键盘区域的 键就没有错位 等就是等 加就是加 而小键盘区…

【Linux实验室】配置yum源为ftp服务器

配置yum源为ftp服务器 实验原理 文件传输协议&#xff08;File Transfer Protocol&#xff0c;FTP&#xff09;是用于在网络上进行文件传输的一套标准协议&#xff0c;它工作在 OSI 模型的第七层&#xff0c; TCP 模型的第四层&#xff0c; 即应用层&#xff0c; 使用 TCP 传…

专题【链表】刷题日记

2024.03.31 两数相加 题目 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例 1:…