房屋装修在线设计网站,没有网站 可以做cpa,wordpress 文章标题,wordpress 嵌套评论#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 判断子序列不同的子序列总结… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 判断子序列不同的子序列总结 判断子序列
392. 判断子序列 - 力扣LeetCode
判断子序列这道题目和上一期的题解法几乎完全相同只是递推公式有一点差别但是要是完全用之前的代码也是可行的。
dp数组的含义dp【i】【j】代表以i-1和j-1为结尾的相同子序列的长度。之前我们讲过同时操作两个数组的时候通常都是设置二维数组。设置为i-1和j-1表示的原因是方便数组初始化。
递推公式当两个字符相等时候 ifs【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) {vectorvectorintdp(s.size()1,vectorint(t.size()1,0));for(int i1;is.size();i){for(int j1;jt.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】也就是我们要填写的位置的左上角它是匹配成功的时候所继承下来的含有个数两者一做和就能得到答案了所以递推公式是 ifs【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。
遍历顺序根据递推公式得到ij位置由它的上面位置和左上位置推导所以依旧是从上到下从左到右
class Solution {
public:int numDistinct(string s, string t) {vectorvectorunsigned long intdp(s.size()1,vectorunsigned long int(t.size()1,0));dp[0][0]1;for(int i1;is.size();i)dp[i][0]1;for(int j1;jt.size();j)dp[0][j]0;for(int i1;is.size();i){for(int j1;jt.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()];}
};总结
今天我们完成了判断子序列、不同的子序列两道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
