day57 判断子序列 不同的子序列 两个字符串的删除操作 编辑距离

题目1  392 判读子序列

题目链接  392 判断子序列

题意

判断字符串s是否为字符串t的子序列  （子序列的相对位置在原字符串中不改变）

就是求最长公共子序列的长度与字符串s的长度是否相等

动态规划

1）确定dp数组及下标i的含义

dp[i][j] 表示以s[i-1]结尾的字符串与以t[j-1]结尾的字符串公共序列的最大长度

2）dp数组初始化

根据递推公式 dp[0][1] = 0   dp[1][0] = 0

3）递推公式

if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] +1;

else dp[i][j] = dp[i-1][j];  考虑1种情况  删除t字符串中该位置的元素(减1)，该位置元素对应不等

4）遍历顺序

根据递推公式 从前向后遍历 从左向右遍历

for(int i =1; i <= s.size(); i++){

     for(int j = 1; j <= t.size(); j++){

     }

}

5）打印dp数组

代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size() > t.size()) return false;
        int result = 0;
        //定义dp数组  初始化
        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];
                result = max(result, dp[i][j]);
            }
        }
        if(result == s.size()) return true;
    return false;
    }
};
  • 时间复杂度：O(n × m)
  • 空间复杂度：O(n × m)

题目2 115 不同的子序列

题目链接 115 不同的子序列

题意

统计字符串s的子序列中字符串t出现的次数  即字符串s里面删除t能否变成字符串t

动态规划

1）确定dp数组及下标i的含义

dp[i][j]   以s[i-1]为结尾的字符串s中有t[j-1]为结尾的字符串t的个数

2）dp数组初始化

根据递推公式  dp[i][0]=1   字符串s中有1个空字符串

dp[0][i] = 0  空字符串s中有0个字符串t

dp[0][0]  空字符串s中有1个空字符串t

3）递推公式

若两个元素相等，那么就不考虑这个位置的元素  个数取决于：

1）前面已有的个数  dp[i-1][j-1]    2）字符串s中相邻两元素相同，模拟删除第一个(减1)  dp[i-1][j]

if(s[i-1] == t[i-1])   dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

若不等，则模拟将元素从字符串s删除掉（减1）

else dp[i][j] = dp[i-1][j]     

4）遍历顺序

根据递推公式  从左向右遍历，从上到下遍历

for(int i = 1; i <= s.size(); i++){

   for(int j = 1; j <= t.size(); j++){

   }

}

5）打印dp数组

本题要求判断个数，所以要使用dp[s.size()][t.size()]求解最终的个数

如果再定义result与dp[i][j]比较了，会遇到这样的情况  s="eee"   t="eee"会得到错误的结果3

因为这里面的每个e都相同，在中间过程会重复计数，所以会产生错误

所以还是应该使用dp[s.size()][t.size()]表示以s.size()-1结尾的字符串s中有t.size()-1结尾的字符串t的个数，说明字符串s遍历到了末尾的位置，求解的是全部的个数

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        if(s.size() < t.size()) return 0;
        //定义并初始化dp数组
        vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
        //初始化dp数组
        for(int i = 0; i <= s.size(); i++){
            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];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
                // cout << "i=" << i << " " << "j=" << j << " " << dp[i][j] << endl; 
            }
        }
        return dp[s.size()][t.size()];
    }
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

题目3  583 两个字符串的删除操作

题目链接 583 两个字符串的删除操作

题意

返回使得单词word1和word2相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

动态规划

1）确定dp数组及下标i的含义

dp[i][j]  以word1[i-1]结尾的word1和以word2[j-1]结尾的word2相同的最小操作次数

2）dp数组初始化

根据递推公式 dp[0][j] = j        dp[i][0] = i

其它下标对应的dp[i][j]可初始化为任意值

3）递推公式

两个字符相同时，操作次数不受影响取决于前面的情况

if(word[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];

两个字符不相同时，那么就要删除一个字符(操作次数+1)  或是 删除两个字符(操作次数+2)

else dp[i][j] = min(dp[i-1][j]+1，dp[i][j-1]+1，dp[i-1][j-1]+2)

4）遍历顺序

根据递推公式，从前向后遍历，从左向右遍历

for(int i = 1; i <= word1.size(); i++){

        for(int j = 1; j < word2.size(); j++){

        }

}

5）打印dp数组

代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        //定义dp数组
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 2, 0));
        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] + 2, min(dp[i-1][j] + 1, dp[i][j-1] + 1));  
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)
法2：使用最长公共子序列进行求解

word1.size() + word2.size() - 2 * coseqlen;

动态规划

1）确定dp数组及下标i的含义

dp[i][j]  以word1[i-1]结尾的word1和以word2[j-1]结尾的word2最长公共子序列的长度

2）dp数组初始化

根据递推公式 dp[0][j] = 0       dp[i][0] = 0

其它下标对应的dp[i][j]可初始化为任意值

3）递推公式

两个字符相同时，操作次数不受影响取决于前面的情况

if(word[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;

两个字符不相同时，那么就要删除一个字符(操作次数+1)  或是 删除两个字符(操作次数+2)

else dp[i][j] = max(dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1])

4）遍历顺序

根据递推公式，从前向后遍历，从左向右遍历

for(int i = 1; i <= word1.size(); i++){

        for(int j = 1; j < word2.size(); j++){

        }

}

代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        //定义dp数组
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for(int i = 0; i <= word1.size(); i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j <= word2.size(); j++){
            dp[0][j] = 0;
        }
        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-1], max(dp[i-1][j], dp[i][j-1]));
                }
            }
        }
        return word1.size() + word2.size() - 2 * dp[word1.size()][word2.size()];
    }
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

题目4  72 编辑距离

题目链接 72 编辑距离

题意

返回将word1转换为word2的最小次数（可以插入\删除\替换一个字符）

添加元素和删除元素是一个等价的操作（在word1中添加元素等价于在word2中删除元素）而替换操作是一个新的动作，需要另外考虑

动态规划

1）确定dp数组及下标i的含义

dp[i][j] 以word1[i-1]结尾的word1和以word2[j-1]结尾的word2相同的最小操作次数

2）dp数组初始化

根据递推公式 dp[i][0] = i   dp[0][j] = j  其他下标对应的dp[i][j]可以初始化为任意值。

3）递推公式

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，dp[i][j-1]+1，dp[i-1][j-1]+1);

注意本题多了一个操作就是替换的操作  而添加操作与删除操作是等价的

4）遍历顺序

根据递推公式 从上到下遍历，从左往右遍历

for(int i = 1; i <= word1.size(); i++){

        for(int j = 1; j <= word2.size(); j++){

        }

]

5）打印dp数组

代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        //定义dp数组
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        //dp数组初始化
        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] + 1, min(dp[i-1][j] + 1, dp[i][j-1] + 1));
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

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

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

相关文章

二十款好用的屏幕录制，绿色绿色好用软件工具，云盘下载

二十款好用的屏幕录制，绿色绿色好用软件工具，云盘下载

本人收藏多年的屏幕录制工具&#xff0c;绿色的&#xff0c;你懂得的。。。。 二十款好用的屏幕录制&#xff0c;绿色绿色好用软件工具&#xff0c;值得收藏 下载地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1RPTlFfeap4TGMnDPgCEo-w?pwdmaky 提取码&#xff1…
阅读更多...
C#简单工厂模式的实现

C#简单工厂模式的实现

using System.Diagnostics.Metrics; using System.Runtime.InteropServices; using static 手写工厂模式.Program;namespace 手写工厂模式 {internal class Program{public interface eats {void eat();}//定义了一个接口public class rice : eats{public void eat() {Console.…
阅读更多...
【Next】动态路由、加载 UI 和流式传输

【Next】动态路由、加载 UI 和流式传输

动态路由 动态段作为 params 属性传递给 layout、page、route 和 generateMetadata 函数。 /app/blog/[slug]/page.tsx export default function Page({params}: {params:{slug:string}}) {return <h1>Slug Page -- {params.slug}</h1> };/app/shop/[...slug]/pa…
阅读更多...
【C++成长记】C++入门 | 类和对象（上） |类的作用域、类的实例化、类的对象大小的计算、类成员函数的this指针

【C++成长记】C++入门 | 类和对象（上） |类的作用域、类的实例化、类的对象大小的计算、类成员函数的this指针

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;C❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、类的作用域 二、类的实例化 三、类对象模型 四、this指针 1、this指针的引出 2 this指针的特…
阅读更多...
4.8-4.12算法刷题笔记

4.8-4.12算法刷题笔记

刷题 堆1. 堆排序2. 模拟堆 哈希表3. 模拟散列表4. 字符串哈希 DFS5. 排列数字6. n-皇后问题 2. BFS&#xff08;队列&#xff09;7. 字母迷宫8. 滑动谜题 3. 树与图的dfs9. 树的重心 4. 树与图的bfs(最短路)10. 图中点的层次( 无权最短路 ) 5. 拓扑排序11. 课程表 6. 朴素dijk…
阅读更多...
C++系列-C++前言

C++系列-C++前言

什么是C C语言是结构化和模块化的语言&#xff0c;适合处理较小规模的程序&#xff0c;对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要高度的抽象和建模时&#xff0c;C语言则不合适&#xff0c;为了解决软件危机&#xff0c;20世纪80年代&#xff0c;计算机界提出…
阅读更多...
iterations迭代列表

iterations迭代列表

今天总结一下这个列表的迭代 情况1&#xff0c;两个列表的迭代 import itertoolsfor x1,x2 in itertools.product([1, 5, 8], [0.5, 4]):print((x1,x2))结果如下 情况2&#xff08;一个列表的迭代&#xff09; import itertools# for x1,x2 in itertools.product([1, 5, 8…
阅读更多...
大数据产品有哪些分类？各类里知名大数据产品都有哪些？

大数据产品有哪些分类？各类里知名大数据产品都有哪些？

随着互联网技术的持续进步和全球数字化转型的推进&#xff0c;我们正处于一个数据爆炸的时代。在这样的大背景下&#xff0c;大数据已经逐渐崭露头角&#xff0c;成为了推动各行各业发展的关键因素和核心资源。大数据不仅仅是指数据的规模巨大&#xff0c;更重要的是它蕴含的价…
阅读更多...
人员聚集监测识别摄像机

人员聚集监测识别摄像机

随着科技的不断发展&#xff0c;人员聚集监测识别摄像机已经成为了现代社会安全管理的重要工具。这种摄像机能够对人员聚集的情况进行实时监测和识别&#xff0c;帮助相关部门及时发现和处理潜在的安全风险。 人员聚集监测识别摄像机可以通过高清晰度的摄像头和先进的人脸识别技…
阅读更多...
Java实现短信发送并校验，华为云短信配合Redis实现发送与校验

Java实现短信发送并校验，华为云短信配合Redis实现发送与校验

Java实现短信发送并校验&#xff0c;华为云短信配合Redis实现发送与校验 安装sms4j和redis <dependency><groupId>org.dromara.sms4j</groupId><artifactId>sms4j-spring-boot-starter</artifactId><version>3.2.1</version> <…
阅读更多...
【自研网关系列】请求服务模块和客户端模块实现

【自研网关系列】请求服务模块和客户端模块实现

&#x1f308;Yu-Gateway&#xff1a;&#xff1a;基于 Netty 构建的自研 API 网关&#xff0c;采用 Java 原生实现&#xff0c;整合 Nacos 作为注册配置中心。其设计目标是为微服务架构提供高性能、可扩展的统一入口和基础设施&#xff0c;承载请求路由、安全控制、流量治理等…
阅读更多...
【python图形界面问题解决】wxPython创建图形界面程序，在代码编译器中正常运行，但是打包后却不能运行解决办法

【python图形界面问题解决】wxPython创建图形界面程序，在代码编译器中正常运行，但是打包后却不能运行解决办法

一、问题 使用wxPython创建一个图形界面&#xff0c;在VSCODE中正常运行&#xff0c;但是打包后&#xff0c;却不能运行&#xff0c;只出现一个一闪而过的窗口&#xff0c;这时最需要看看这窗口到底显示了什么内容。这里可以使用录屏软件录制屏幕&#xff0c;这里使用LICEcap小…
阅读更多...
嵌入式单片机补光灯项目操作实现

嵌入式单片机补光灯项目操作实现

1.【实验目的】 用于直播效果的补光 2.【实验原理】 原理框架图2.各部分原理及主要功能 1.充电和供电：采用5V2A tepy_c接口充电，3.7V锂电池供电， 2.功能：产品主要是用于直播或拍照时的补光。分为三个模式：白光/暧光&#x
阅读更多...
【web网页制作】html+css网页制作学校网站主题校园网页（5页面）【附源码】

【web网页制作】html+css网页制作学校网站主题校园网页（5页面）【附源码】

学校网页制作目录 涉及知识写在前面一、网页主题二、网页效果Page1、简介Page2、校园风光Page3、学术研究Page4、校训阐述Page5、留言 三、网页架构与技术3.1 脑海构思3.2 整体布局3.3 技术说明书 四、网页源码4.1 主页模块源码4.2 源码获取方式 作者寄语 涉及知识 学校网站主…
阅读更多...
鉴权设计（一）———— 登录验证

鉴权设计（一）———— 登录验证

1、概述 网站系统出于安全性的考虑会对用户进行两个层面的校验&#xff1a;身份认证以及权限认证。这两个认证可以保证只有特定的用户才能访问特定的数据的需求。 本文先实现一个基于jwt拦截器redis注解实现的简单登录验证功能。 2、设计思路 jwt用于签发token。 拦截器用于拦…
阅读更多...
第十二届蓝桥杯真题做题笔记

第十二届蓝桥杯真题做题笔记

2、卡片 笔记&#xff1a; 直接巧用排列组合求解即可&#xff1a; 我们通过对样例说明进行分析可知&#xff1a;想要分给n个小孩&#xff0c;那么我们就需要满足C(K, 2) K > n才能满足。 #include<bits/stdc.h> using namespace std;int com(int up, int down){i…
阅读更多...
ERROR 1052 (23000): Column ‘deptno‘ in field list is ambiguous

ERROR 1052 (23000): Column ‘deptno‘ in field list is ambiguous

错误原因&#xff1a; 这个错误通常是在多表查询中&#xff0c;因为你的SQL查询中包含了多个表&#xff0c;并且这些表中都有一个名为deptno的列。这会导致数据库无法确定你要引用哪个表中的 deptno列&#xff0c;从而产生歧义。 解决方法&#xff1a; 为了解决这个问…
阅读更多...
实验：基于Red Hat Enterprise Linux系统建立RAID磁盘阵列

实验：基于Red Hat Enterprise Linux系统建立RAID磁盘阵列

目录 一. 实验目的 二. 实验内容 三. 实验设计描述及实验结果 什么是磁盘阵列&#xff08;RAID&#xff09; 1. 为虚拟机添加4块大小为20G的硬盘nvme0n【2-5】&#xff0c;将nvme0n【2、3、4】三块硬盘 建立为raid5并永久挂载&#xff0c;将RAID盘全部空间制作逻辑卷&#…
阅读更多...
又是大佬开源的一款自动预约i茅台的系统

又是大佬开源的一款自动预约i茅台的系统

又是大佬开源的一款自动预约i茅台APP的系统 话不多说直接上系统 Campus-imaotai,i茅台app自动预约&#xff0c;每日自动预约&#xff0c;支持docker一键部署.现在github上已有1.6kstar,就不谈有多少用户现在真正在使用这个系统了,操作方便,配置简单即可快速上手 github地址:ht…
阅读更多...
【bugku】变量1

【bugku】变量1

1.打开靶场&#xff0c;进入主机 2.根据源码发出get请求&#xff0c;GLOBALS这种全局变量用于在 PHP 脚本中的任意位置访问全局变量 3.得到flag值
阅读更多...
最新文章

Copyright @ 2022~2023