代码随想录算法训练营第五十四天 | LeetCode 392. 判断子序列、115. 不同的子序列

简介: 代码随想录算法训练营第五十四天 | LeetCode 392. 判断子序列、115. 不同的子序列

代码随想录算法训练营第五十四天 | LeetCode 392. 判断子序列、115. 不同的子序列

文章链接:判断子序列不同的子序列

视频链接:判断子序列不同的子序列

1. LeetCode 392. 判断子序列

1.1 思路

  1. 本题是给两个字符串让我们判断字符串 s 是不是字符串 t 的子序列。子序列要求不能改变数组顺序,不要求连续,其实这题和1143. 最长公共子序列是一样的,本题中如果两个字符串的最长公共子序列长度是字符串 s 的长度的话,那么字符串 s 就应该是字符串 t 的子序列了。本题也算是编辑距离的入门题
  2. dp 数组及其下标的含义:用一个二维数组就可以表示出两个字符串里每一个元素它的是否相同的情况,dp[i][j]:以 i-1 为结尾的字符串 s 和以 j-1 为结尾的字符串 t 的相同子序列的长度为 dp[i][j],如果这个长度就是字符串 s 的长度,那字符串 s 就是字符串 t 的子序列。这里定义 i-1 和 j-1 是为了避免对第一行和列进行复杂的初始化,定义为 i 和 j 也行,就是麻烦些
  3. 递推公式:有两个情况,判断的就是两个元素是否相同。if(s[i-1]==t[j-1])为什么判断的是 i-1 和 j-1,因为我们 dp 数组就是这么定义的。如果相等 dp[i][j]=dp[i-1][j-1]+1,含义就是这两个元素相等了,就在前面的基础上加 1。如果不相等 else 只能在 t 中删除元素,即如果 s 的 i-1 位置和 t 的 j-1 位置不相等了,就把 t 的 j-1 位置删除掉了,考虑的就是 t 的 j-2 前面的字符串和 s 的 i-1 前面的字符串的相同子序列长度了,也就是 dp[i][j-1],dp[i][j]=dp[i][j-1],其实可以理解为继承的意思

  4. dp 数组的初始化:根据递推公式可以看出推导方向,根据这个推导方向,就需要初始化第一行 dp[0][j] 和第一列 dp[i][0],根据 dp 数组的含义,这里是 0 的话是需要以 -1 为结尾的相同子序列也就是空串的相同子序列长度,也就是 0 了,因此 dp[i][0]=dp[0][j]=0,其余下标根据递推公式会被覆盖的,因此可以不管,默认为 0 即可
  5. 遍历顺序:根据推导方向,一定要从左到右从上到下,避免赋的是空值 for(int i=1;i<=s.length();i++)for(int j=1;j<=t.length();j++)为什么从 1 开始,因为 0 已经初始化了。为什么要取等于号,因为 dp 数组是从 i-1 和 j-1 开始,不取等于号会漏了最后一个状态,而我们最初定义 dp 数组会是 [s.length()+1][t.length()+1]。最终结果是在 dp[s.length()][t.length()],如果和 s.length()相等就是 true,反之 false
  6. 打印 dp 数组:用于 debug

1.2 代码

class Solution {
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
            return true;
        }else{
            return false;
        }
    }
}

2. LeetCode 115. 不同的子序列

2.1 思路

  1. 本题求的是子序列,不要求连续,问的是 s 有多少个 t 这样的子序列,其实就是相当于问 s 可以有多少种删除元素的方式。
  2. dp 数组及其下标的含义:对于两个字符串比较里面的元素是否相同的情况是定义二维数组,dp[i][j]:以 i-1 为结尾的 s 中有以 j-1 为结尾的 t 的个数为 dp[i][j]。为什么定义 i-1 和 j-1 上面解释过了
  3. 递推公式:if(s[i-1]==t[j-1])为什么判断的是 i-1 和 j-1,看看 dp 数组的含义,如果相等就不需要考虑这两个字母,而是 i-2 和 j-2 为结尾的个数即 dp[i-1][j-1],那也可以考虑不使用 s[i-1],为什么呢?举例:s=bagg,t=bag,如果不使用 s[3] 此时前面的也可以等于 t,这种情况不使用它就相当于把 s[i-1] 删除掉了,此时的情况就是 dp[i-1][j]。而我们这里不求 t 有多少个 s,因此不能不考虑 t[j-1]。那因此 dp[i][j] 就应该是考虑 s[i-1] 和不考虑 s[i-1] 的情况相加,dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。如果 s[i-1]!=t[j-1] 就是把 s[i-1] 删除的情况,就是不考虑它了,就 dp[i][j]=dp[i-1][j]。

  4. dp 数组的初始化:根据递推公式可以看出推导方向,因此最上方的第一行和第一列一定要初始化,dp[0][j] 第一行这种情况就是以-1 为结尾的空字符串 s 有以 j-1 为结尾的 t 的个数,空字符串肯定没有 t,因此初始化为 0;dp[i][0] 第一列这种情况就是以 i-1 为结尾的 s 有以-1 为结尾的空字符串 t 的个数,那就应该是 1 了,s 肯定有一个空字符串,因此初始化为 1,而 dp[0][0] 也就是这种情况了,也初始化为 1
  5. 遍历顺序:根据推导方向从左到右从上到下,因此 for(int i=1;i<=s.length();i++)for(int j=1;j<=t.length();j++),为什么取 1 以及为什么要等于号上面解释过了。最终结果是在 dp[s.length()][t.length()]
  6. 打印 dp 数组:用于 debug

2.2 代码

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 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()];
    }
}
目录
打赏
0
0
1
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
67 3
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等