【算法练习Day46】判断子序列不同的子序列

news/2025/1/25 2:10:45/

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:练题
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 判断子序列
  • 不同的子序列
  • 总结:

判断子序列

392. 判断子序列 - 力扣(LeetCode)

判断子序列这道题目,和上一期的题解法几乎完全相同,只是递推公式有一点差别,但是要是完全用之前的代码也是可行的。

dp数组的含义:dp【i】【j】代表以i-1和j-1为结尾的相同子序列的长度。之前我们讲过,同时操作两个数组的时候,通常都是设置二维数组。设置为i-1和j-1表示的原因是,方便数组初始化。

递推公式:当两个字符相等时候

if(s【i-1】==t【j-1】)dp【i】【j】=dp【i-1】【j-1】+1;

因为dp数组含义的缘故,我们在判断时候对应的也是它的字符串的i-1位置和j-1位置,然后如果两字符此时对应相等,那么就是之前最大的相同子序列的长度+1。

else dp【i】【j】=dp【i】【j-1】;

如果两字符不相等,那么就让此时的对应的do等于 dp【i】【j-1】,这是因为我们是判断s是否为t的子序列,是删除t中某些元素看看能否构成s,已知此时两对应字符一定不相等,那此时dp就等于不考虑当前这个不等的字符时,所对应的最长相同子序列长度,这样做也相当于变相删除该多余字符。细心的读者也许已经发现了,与之前那期递推公式不同的是没有dp【i-1】【j】这一项了,之前的递推公式是它们两个取最大值,那是因为上一道题两个字符都可以删除若干数据,而最终保证结果是最长的公共部分就可以了,不一定给的哪个字符串更长,所以删哪一个也就不一定了,需要取最大值,而这道题我们是明确的判断s是否是t的子序列,那就是t长要删除某元素后看是否构成s。至于为什么我说用和之前一样的代码也能通过呢?因为我们不需要删除s的元素,也就是说加上它也不会影响代码的运行逻辑,但是建议还是要根据题目的需求写逻辑,而不是这类题都用一种固定的递推公式来写,这样多思考更有利于理解题的本质。

dp数组初始化:dp数组初始化就是全都是0没什么说的,由于dp定义的缘故,和递推公式的推理,都使得,应该被初始化为0。

遍历顺序:还是正常的从左到右从上到下。

class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=dp[i][j-1];}}if(dp[s.size()][t.size()]==s.size())return true;return false;}
};

题整体来看如果,上一期的题目可以完全理解,那这道题就还是相对好做一些。

不同的子序列

115. 不同的子序列 - 力扣(LeetCode)

与上一道题的相比,这道题显得难了不少。也是困扰了我一段时间的题,感觉递推公式不是很好理解。

dp数组含义:这道题是判断在s里t出现的次数有多少次,这道题并不是说直观的就能看出s字符串里有几个t,不要曲解题目意思,它是说有多少种删除元素的方法,使得字符串由s转化为t,应该这样去理解。所以应该将数组含义定义为以i-1结尾的字符串s中包含有以j-1为结尾的t多少个。这个dp数组定义非常重要,要好好理解,才能够理解下面的递推公式。

递推公式:递推公式由两部分组成,和上一题一样,一个是要匹配的字符匹配,另一个字符不匹配,要模拟删除,而不同的是这道题里能够相匹配的字符递推公式,也分成两部分。

经过了一段时间的理解,我觉得这样想是能够帮助理解递推式的。

如果两字符不匹配,那么dp【i】【j】=dp【i-1】【j】因为我们上面说过dp数组的含义,表示的是前一个位置,当前一个位置不匹配字符,那么说明此时应该和同一列的上一行所代表的个数相等,为什么是这样呢?画dp数组推到图也就是打印,我们可以知道,s表示行t表示列时候,此时s对应的字符和t不等,那么就应该此处的数值继承下来上一次匹配成功的值,虽然它的同列上一行也可能不匹配,但是它的上一处也是继承的匹配成功的那个个数。我们是拿着s的字符一点点找t的字符去匹配,如果还是不明白,画一次会帮助理解。

那如果两字符相匹配呢?我们不仅仅要保留之前的匹配不成功的所继承下来的个数,还要加上此次匹配成功时候应该加上的个数,而上一次怕匹配成功是哪一个位置?是dp【i-1】【j-1】也就是我们要填写的位置的左上角,,它是匹配成功的时候所继承下来的含有个数,两者一做和就能得到答案了,所以递推公式是:

if(s【i-1】==t【j-1】)dp【i】【j】=dp【i-1】【j-1】+dp【i-1】【j】
else dp【i】【j】=dp【i-1】【j】

一开始怎么也想不明白为什么,要这么写,后来换一种思维去想,就能想得明白了。

dp数组初始化:初始化也是有一定讲究的,虽然我们是定义的i-1和j-1的位置,但此题并不意味着要全部初始化为0,因为我们是求得s里有几个t,当t是空字符串时候,每一个i-1下标都对应着一种方法得到t,那就是删除i-1之前的全部字符,得到一个空字符串。s是空字符串时候,无论怎么删都不可能得到一个t,而且其他的位置都会被递推公式所覆盖,所以除了第一行之外全都初始化为0就可以了,第一行初始化为1。

遍历顺序:根据递推公式得到,i,j位置由它的上面位置和左上位置推导,所以依旧是从上到下从左到右

class Solution {
public:int numDistinct(string s, string t) {vector<vector<unsigned long int>>dp(s.size()+1,vector<unsigned long int>(t.size()+1,0));dp[0][0]=1;for(int i=1;i<s.size();i++)dp[i][0]=1;for(int j=1;j<t.size();j++)dp[0][j]=0;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//可以理解为dp二维数组即使本次匹配字符未成功//它也至少是上一次匹配的个数,因为dp数组的定义就是s字符串i-1位置下,对应的有几个t//本次即使未匹配成功,也不应该影响之前匹配成功保留下来的次数。//而如果匹配成功,那么就是两个字符匹配的成功个数加上本来有的个数else dp[i][j]=dp[i-1][j];}}return dp[s.size()][t.size()];}
};

总结:

今天我们完成了判断子序列、不同的子序列两道题,相关的思想需要多复习回顾。接下来,我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

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

相关文章

OpenShift 4 - 对 OpenShift 的 etcd 数据库加密

《OpenShift / RHEL / DevSecOps 汇总目录》 说明&#xff1a;本文已经在 OpenShift 4.14 的环境中验证 文章目录 加密 etcd 数据库验证加密的 etcd 数据库解密 etcd 数据库 加密 etcd 数据库 OpenShift 对 etcd 数据库加密时只加密值&#xff0c;而不加密键。而资源类型、命…

Leetcode 2930. Number of Strings Which Can Be Rearranged to Contain Substring

Leetcode 2930. Number of Strings Which Can Be Rearranged to Contain Substring 1. 解题思路2. 代码实现 题目链接&#xff1a;2930. Number of Strings Which Can Be Rearranged to Contain Substring 1. 解题思路 这一题的话思路上就是利用容斥原理来直接求总数。 显然…

shell脚本实战案例---安全脚本

例题&#xff1a;自动化禁止恶意IP访问 应用场景&#xff1a;防止恶意IP尝试ssh登录。---暴力破解密码 脚本说明&#xff1a;将密码输入错误超过4次的IP地址通过iptables防火墙阻止访问。 目录 1.脚本分析&#xff1a; 【1】首先ssh登录之后&#xff0c;产生…

深入理解强化学习——多臂赌博机:知识总结

分类目录&#xff1a;《深入理解强化学习》总目录 我们在《深入理解强化学习——多臂赌博机》系列文章中介绍了几种平衡试探和开发的简单方法。 ϵ − \epsilon- ϵ−贪心方法在一小段时间内进行随机的动作选择&#xff0c;而UCB方法虽然采用确定的动作选择&#xff0c;却可以通…

NFS实验(总)

实验要求 架设一台NFS服务器&#xff0c;并按照以下要求配置 1、开放/nfs/shared目录&#xff0c;供所有用户查询资料 2、开放/nfs/upload目录&#xff0c;为192.168.17.0/24网段主机可以上传目录&#xff0c; 并将所有用户及所属的组映射为nfs-upload,其UID和GID均为210 3、将…

LeetCode【923】三数之和的多种可能性

题目&#xff1a; 思路&#xff1a; https://www.jianshu.com/p/544cbb422300 代码&#xff1a; int threeSumMulti(vector<int>& A, int target) {//Leetcode923:三数之和的多钟可能//initialize some constint kMod 1e9 7;int kMax 100;//calculate frequenc…

Flowable 外部表单

内置表单需要在每个节点中去配置&#xff0c;当如果多个节点使用同一套表单属性就要配置多次比较麻烦&#xff0c;修改的时候也要修改多次&#xff0c;外部表单可以定义一次&#xff0c;然后其它节点都去引用同一个表单属性。 外部表单需要定义一个.form后缀的文件。 外部表单…

C++自动注册的工厂与--whole-archive

上篇文章《静态库和链接选项--whole-archive》提到--whole-archive的一个应用场景&#xff1a;C自动注册的工厂&#xff0c;这篇文章来填坑。 预备知识 我们经常用工厂类或工厂方法统一管理资源&#xff0c;实现资源的创建和使用之间的解耦&#xff0c;调用者无需关心资源创建的…