代码随想录训练营Day 58|力扣392.判断子序列、115不同的子序列、583两个字符串的删除操作、72编辑距离

2024-06-13 18:04
文章标签 序列 随想录 day 58 力扣 392 115 583 72 训练营 字符串 删除 代码 编辑 距离 判断 操作 不同 两个

本文主要是介绍代码随想录训练营Day 58|力扣392.判断子序列、115不同的子序列、583两个字符串的删除操作、72编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.判断子序列

代码随想录

代码：

class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size() + 1,vector<int>(t.size() + 1,0));// 判断s和t的公共最长子序列的长度是否和s的长度相等// dp[i][j]表示下标为0~i-1的s的子数组和下标为0~j-1的子数组的最长公共子序列的长度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] = max(dp[i - 1][j],dp[i][j - 1]);}}}if(dp[s.size()][t.size()] == s.size()){return true;}else{return false;}}
};

 思路：

        这题就是判断两个字符串的最长公共子序列是不是s。其实套路都一样。下面的都是copy昨天的。

        dp数组的含义：dp[i][j]表示下标为0~i-1和0~j-1字符串的最长公共子序列的长度。注意到了吗，只是求这两个字符串的最长公共子序列，没有要求一定要以什么东西结尾。所以最后一个元素就是dp数组中最大的那个元素。

        dp数组的初始化：dp[0][j]和dp[i][0]都没有实际意义，而且为了能够推出符合实际意义的dp[1][1]应该把这些元素初始化为0

        dp数组的递推公式：如果此时的i-1和j-1下标对应的元素都相等，那就可以在dp[i - 1][j - 1]的基础上加一了。如果不相等，就说明这两元素有互斥的关系，两个元素不可能同时被选到最长公共子序列中。所以我们可以分两种情况：dp[i - 1][j]或dp[i][j - 1]，取两个的最大值。

        dp数组的遍历顺序：正序遍历。

2.不同的子序列

代码随想录 (programmercarl.com)

代码：

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1,vector<uint64_t>(t.size() + 1,0));// dp[i][j]表示s中下标为0~i-1的字串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法// 根据定义进行初始化// dp[0][j]表示在空串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法// 很明显没有for(int i = 0; i <= s.size(); i++){// dp[i][0]表示s中下标为0~i-1的字串有多少种删除元素后可以变成空串的方法// 很明显是一种，就是删除所有元素 dp[0][0]也满足dp[i][0] = 1;}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数组的含义是方法数！！！// 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。// 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。}else{dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()];}
};

 思路：

        dp数组的含义： dp[i][j]表示s中下标为0~i-1的字串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法

        dp数组的初始化：dp[0][j]表示在空串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法，很明显没有；dp[i][0]表示s中下标为0~i-1的字串有多少种删除元素后可以变成空串的方法很明显是一种，就是删除所有元素。（dp[0][0]也满足）

        dp数组的递推公式：注意这里dp数组的含义是方法数！！！
                    一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
                    一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

        dp数组的遍历顺序：正序遍历

uint64_t 是 C/C++ 语言中的整数数据类型，它表示无符号的 64 位整数。在标准头文件 <cstdint> 中定义，并且可用于确保在不同平台上具有相同大小的无符号 64 位整数。uint64_t 类型通常用于需要大范围整数值的情况，例如处理大量数据或需要确保数值不为负的情况。

3.两个字符串的删除操作

 代码随想录 (programmercarl.com)

代码： (正面思考。去模拟删除过程)

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1,0));// dp[i][j] dp[i][j]表示s中下标为0~i-1的字串 和 t中下标为0~j-1的子串 相同的最小步数for(int i = 0; i <= word1.size(); i++){dp[i][0] = i;}for(int j = 0; j <= word2.size(); j++){dp[0][j] = j;}// 递推for(int i = 1; i <= word1.size();i++){for(int j = 1; j <= word2.size(); j++){if(word1[i - 1] == word2[j - 1]){dp[i][j] = dp[i - 1][j - 1]; // 新加的两个元素本来就相同，不需要做任何操作}else{dp[i][j] = min(dp[i - 1][j] + 1,min(dp[i][j - 1] + 1,dp[i - 1][j - 1] + 2));// 新加进来的元素不同，要不删掉其中一个，要不两个都删了}}}return dp[word1.size()][word2.size()];}
};

思路： 

        dp数组的含义：dp[i][j] dp[i][j]表示s中下标为0~i-1的字串 和 t中下标为0~j-1的子串 相同的最小步数

        dp数组的递推公式：新加的两个元素本来就相同，不需要做任何操作 dp[i][j] = dp[i - 1][j - 1];新加的两个两个元素不同，要不删掉其中一个，要不两个都删了。dp[i][j] = min(dp[i - 1][j] + 1,min(dp[i][j - 1] + 1,dp[i - 1][j - 1] + 2))

        dp数组的初始化：按照定义初始化就好了。

        dp数组的遍历顺序：正序遍历

代码：（反面来思考。用最少的操作剩下的子序列，不就是最长公共子序列吗？只要做一下减法就好了）

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1,0));// dp[i][j]表示dp[i][j]表示下标为0~i-1和0~j-1字符串的最长公共子序列的长度。for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i - 1] == word2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}}}return word1.size() + word2.size() - 2 * dp[word1.size()][word2.size()];}
};

4.编辑距离

代码随想录 (programmercarl.com)

代码： 

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1,0));// dp[i][j] dp[i][j]表示s中下标为0~i-1的字串 和 t中下标为0~j-1的子串 相同的最小操作数// 这道题和上一道的区别就是替换用到操作数其实是会变少的。// 添加和删除元素的所用的操作数都是一样的。for(int i = 0; i <= word1.size(); i++){dp[i][0] = i;}for(int j = 0; j <= word2.size(); j++){dp[0][j] = j;}for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i - 1] == word2[j - 1]){dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = min(dp[i][j - 1] + 1,min(dp[i - 1][j] + 1,dp[i - 1][j - 1] + 1));// 区别就在这里 dp[i - 1][j - 1] + 1就表示替换 上一题我们这里是加2，因为只能用删除}}}return dp[word1.size()][word2.size()];}
};

思路：

因为添加和删除，其实相对的操作次数是相同的。

这一道题和上一题唯一的区别就是 这里的替换表达式是dp[i - 1][j - 1] + 1 ；而上一题我们只能用删除，所以这里是dp[i - 1][j - 1] + 2。替换所用的操作数少了1.。

这篇关于代码随想录训练营Day 58|力扣392.判断子序列、115不同的子序列、583两个字符串的删除操作、72编辑距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1058029。

相关文章

随想录 Day 69 并查集 107. 寻找存在的路径

随想录 Day 69 并查集 107. 寻找存在的路径

随想录 Day 69 并查集 107. 寻找存在的路径 理论基础 int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
阅读更多...
RedHat运维-Linux文本操作基础-AWK进阶

RedHat运维-Linux文本操作基础-AWK进阶

你不用整理，跟着敲一遍，有个印象，然后把它保存到本地，以后要用再去看，如果有了新东西，你自个再添加。这是我参考牛客上的shell编程专项题，只不过换成了问答的方式而已。不用背，就算是我自己亲自敲，我现在好多也记不住。 1. 输出nowcoder.txt文件第5行的内容 2. 输出nowcoder.txt文件第6行的内容 3. 输出nowcoder.txt文件第7行的内容 4. 输出nowcode
阅读更多...
uniapp接入微信小程序原生代码配置方案（优化版）

uniapp接入微信小程序原生代码配置方案（优化版）

uniapp项目需要把微信小程序原生语法的功能代码嵌套过来，无需把原生代码转换为uniapp，可以配置拷贝的方式集成过来 1、拷贝代码包到src目录 2、vue.config.js中配置原生代码包直接拷贝到编译目录中 3、pages.json中配置分包目录，原生入口组件的路径 4、manifest.json中配置分包，使用原生组件 5、需要把原生代码包里的页面修改成组件的方
阅读更多...
Java面试八股之怎么通过Java程序判断JVM是32位还是64位

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

怎么通过Java程序判断JVM是32位还是64位 可以通过Java程序内部检查系统属性来判断当前运行的JVM是32位还是64位。以下是一个简单的方法： public class JvmBitCheck {public static void main(String[] args) {String arch = System.getProperty("os.arch");String dataM
阅读更多...
电脑不小心删除的文件怎么恢复？4个必备恢复方法！

电脑不小心删除的文件怎么恢复？4个必备恢复方法！

“刚刚在对电脑里的某些垃圾文件进行清理时，我一不小心误删了比较重要的数据。这些误删的数据还有机会恢复吗？希望大家帮帮我，非常感谢！” 在这个数字化飞速发展的时代，电脑早已成为我们日常生活和工作中不可或缺的一部分。然而，就像生活中的小插曲一样，有时我们可能会在不经意间犯下一些小错误，比如不小心删除了重要的文件。 当那份文件消失在眼前，仿佛被时间吞噬，我们不禁会心生焦虑。但别担心，就像每个问题
阅读更多...
公共筛选组件（二次封装antd）支持代码提示

公共筛选组件（二次封装antd）支持代码提示

如果项目是基于antd组件库为基础搭建，可使用此公共筛选组件 使用到的库 npm i antdnpm i lodash-esnpm i @types/lodash-es -D /components/CommonSearch index.tsx import React from 'react';import { Button, Card, Form } from 'antd'
阅读更多...
17.用300行代码手写初体验Spring V1.0版本

17.用300行代码手写初体验Spring V1.0版本

1.1.课程目标 1、了解看源码最有效的方式，先猜测后验证，不要一开始就去调试代码。 2、浓缩就是精华，用 300行最简洁的代码 提炼Spring的基本设计思想。 3、掌握Spring框架的基本脉络。 1.2.内容定位 1、 具有1年以上的SpringMVC使用经验。 2、 希望深入了解Spring源码的人群，对 Spring有一个整体的宏观感受。 3、 全程手写实现SpringM
阅读更多...
2390.从字符串中移除星号

2390.从字符串中移除星号

给你一个包含若干星号 * 的字符串 s 。 在一步操作中，你可以： 选中 s 中的一个星号。 移除星号左侧最近的那个非星号字符，并移除该星号自身。 返回移除 所有 星号之后的字符串。 注意： 生成的输入保证总是可以执行题面中描述的操作。 可以证明结果字符串是唯一的。 示例 1： 输入：s = “leet**cod*e” 输出：“lecoe” 解释：从左到右执行移除操作： 距离第 1 个
阅读更多...
Python 字符串占位

Python 字符串占位

在Python中，可以使用字符串的格式化方法来实现字符串的占位。常见的方法有百分号操作符 % 以及 str.format() 方法 百分号操作符 % name = "张三"age = 20message = "我叫%s，今年%d岁。" % (name, age)print(message) # 我叫张三，今年20岁。 str.format() 方法 name = "张三"age
阅读更多...
时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测 目录 时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测基本介绍程序设计参考资料 基本介绍 MATLAB实现LSTM时间序列未来多步预测-递归预测。LSTM是一种含有LSTM区块（blocks）或其他的一种类神经网络，文献或其他资料中LSTM区块可能被描述成智能网络单元，因为
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2