当前位置: 首页 > news >正文

[Algorithm][动态规划][两个数组的DP][正则表达式匹配][交错字符串][两个字符串的最小ASCII删除和][最长重复子数组]详细讲解

目录

  • 1.正则表达式匹配
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 2.交错字符串
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 3.两个字符串的最小ASCII删除和
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 4.最长重复子数组
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现


1.正则表达式匹配

1.题目链接

  • 正则表达式匹配

2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • dp[i]j]p[0, j]区间内的子串能否匹配s[0, i]区间内的子串
    • 推导状态转移方程:根据最后一个位置的情况,分情况讨论

      • 结论
        请添加图片描述

      • 推导过程
        请添加图片描述

      • 本题若直接按照如下的状态转移方程去写,时间复杂度会到 O ( N 3 ) O(N^3) O(N3)

      • 所以需要想办法优化

    • 优化

      • 方法一:数学推导
        请添加图片描述

      • 方法二:根据状态表示以及实际情况,优化状态转移方程 -> 抽象,难理解:(

        • 实际相当于保留了*,把状态传递给前面
          请添加图片描述
    • 初始化:

      • 多开一行及一列虚拟结点
        请添加图片描述
    • 确定填表顺序:从上往下,从左往右

    • 确定返回值:dp[n][m]


3.代码实现

bool isMatch(string s, string p) 
{int n = s.size(), m = p.size();s = " " + s, p = " " + p;vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));// Initdp[0][0] = true;for(int i = 2; i <= m; i += 2){if(p[i] == '*'){dp[0][i] = true;}else{break;}}// DPfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(p[j] == '*'){dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];}else{dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];}}}return dp[n][m];
}

2.交错字符串

1.题目链接

  • 交错字符串

2.算法原理详解

  • 预处理s1 = " " + s1, s2 = " " + s2, s3 = " " + s3

    • 目的:此时可以很简便的用s1s2的下标就计算到s3的的下标
      请添加图片描述
  • 思路

    • 确定状态表示 -> dp[i][j]的含义

      • dp[i]j]s1[1, i]区间内的字符串以及s2[1, j]区间内的字符串,能否拼接凑成s3[1, i + j]区间内的字符串
    • 推导状态转移方程:根据最后一个位置的情况,分情况讨论
      请添加图片描述

    • 初始化:

      • 多开一行及一列虚拟结点
        请添加图片描述
    • 确定填表顺序:从上往下,从左往右

    • 确定返回值:dp[n][m]


3.代码实现

bool isInterleave(string s1, string s2, string s3) 
{int n = s1.size(), m = s2.size();if(n + m != s3.size()) return false;s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));// Initdp[0][0] = true;for(int i = 1; i <= m; i++) // 第一行{if(s2[i] == s3[i]){dp[0][i] = true;}else{break;}}for(int i = 1; i <= n; i++) // 第一列{if(s1[i] == s3[i]){dp[i][0] = true;}else{break;}}// DPfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j])|| (s2[j] == s3[i + j] && dp[i][j - 1]);}}return dp[n][m];
}

3.两个字符串的最小ASCII删除和

1.题目链接

  • 两个字符串的最小ASCII删除和

2.算法原理详解

  • 问题转化:删除后,公共子序列中,ASCII和最大的 —> 正难则反
  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • dp[i]j]s1[0, i]区间以及s2[0, j]区间内的所有的子序列里,公共子序列ASCII最大和
    • 推导状态转移方程:根据最后一个位置的情况,分情况讨论
      请添加图片描述

    • 初始化:vector<vector<int>> dp(n + 1, vector<int>(m + 1))

    • 确定填表顺序:从上往下,从左往右

    • 确定返回值:

      • 统计2个字符串的ASCII和sum
      • sum - dp[n][m] * 2

3.代码实现

int minimumDeleteSum(string s1, string s2) 
{int n = s1.size(), m = s2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);if(s1[i - 1] == s2[j - 1]){dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);}}}int ret = 0;for(auto& ch : s1){ret += ch;}for(auto& ch : s2){ret += ch;}return ret - dp[n][m] * 2;
}

4.最长重复子数组

1.题目链接

  • 最长重复子数组

2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • dp[i]:选取[0, i]一段区间内的所有子数组 ×
        • 因为此时无法知道最长子数组在哪儿,可能在中间,此时无法正确表示状态
      • dp[i][j]nums1[i]中以i位置元素为结尾的所有的子数组以及nums2中以j位置元素为结尾的所有的子数组中,最长重复子数组的长度
    • 推导状态转移方程:根据最后一个位置的情况,分情况讨论
      请添加图片描述

    • 初始化:vector<vector<int>> dp(n + 1, vector<int>(m + 1))

    • 确定填表顺序:从上往下

    • 确定返回值:dp表里面的最大值


3.代码实现

int findLength(vector<int>& nums1, vector<int>& nums2) 
{int n = nums1.size(), m = nums2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));int ret = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(nums1[i - 1] == nums2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;ret = max(ret, dp[i][j]);}}}return ret;
}

相关文章:

[Algorithm][动态规划][两个数组的DP][正则表达式匹配][交错字符串][两个字符串的最小ASCII删除和][最长重复子数组]详细讲解

目录 1.正则表达式匹配1.题目链接2.算法原理详解3.代码实现 2.交错字符串1.题目链接2.算法原理详解3.代码实现 3.两个字符串的最小ASCII删除和1.题目链接2.算法原理详解3.代码实现 4.最长重复子数组1.题目链接2.算法原理详解3.代码实现 1.正则表达式匹配 1.题目链接 正则表达…...

Ffmpeg安装和简单使用

Ffmpeg安装 下载并解压 进入官网 (https://ffmpeg.org/download.html)&#xff0c;选择 Window 然后再打开的页面中下滑找到 release builds&#xff0c;点击 zip 文件下载 环境变量配置 下载好之后解压&#xff0c;找到 bin 文件夹&#xff0c;里面有3个 .exe 文件 然后复制…...

29、matlab算数运算汇总2:加、减、乘、除、幂、四舍五入

1、乘法:times, .* 语法 C A.*B 通过将对应的元素相乘来将数组 A 和 B 相乘。 C times(A,B) 是执行 A.*B 的替代方法&#xff0c; 1)将两个向量相乘 代码及运算 A [1 0 3]; B [2 3 7]; C A.*BC 2 0 212&#xff09; 将两个数组相乘 代码及运算 A [1 0 3;…...

<Rust><iced>基于rust使用iced库构建GUI实例:动态改变主题色

前言 本专栏是Rust实例应用。 环境配置 平台&#xff1a;windows 软件&#xff1a;vscode 语言&#xff1a;rust 库&#xff1a;iced、iced_aw 概述 本篇构建了这样的一个实例&#xff0c;可以动态修改UI的主题&#xff0c;通过菜单栏来选择预设的自定义主题和官方主题&#…...

k8s——安全机制

一、安全机制说明 Kubernetes作为一个分布式集群的管理工具&#xff0c;保证集群的安全性是其一个重要的任务。API Server是集群内部各个组件通信的中介&#xff0c; 也是外部控制的入口。所以Kubernetes的安全机制基本就是围绕保护API Server来设计的。 比如 kubectl 如果想…...

Linux驱动应用编程(三)UART串口

本文目录 前述一、手册查看二、命令行调试串口1. 查看设备节点2. 使用stty命令设置串口3. 查看串口配置信息4. 调试串口 三、代码编写1. 常用API2. 例程线程优化 前述 在开始实验前&#xff0c;请一定要检查测试好所需硬件是否使用正常&#xff0c;不然调试过程中出现的问题&am…...

【设计模式深度剖析】【4】【行为型】【策略模式】

文章目录 策略模式定义英文原话直译 角色类图策略接口Strategy&#xff1a;具体策略类上下文类Context测试类 策略模式的应用策略模式的优点策略模式的缺点策略模式的使用场景 策略模式 策略模式&#xff08;Strategy Pattern&#xff09; Strategy策略也称作Policy政策。 想…...

opencv dnn模块 示例(26) 目标检测 object_detection 之 yolov10

文章目录 1、yolov10简要介绍1.1、双标签分配策略1.2、架构改进1.3、性能1.4、预训练模型1.5、网络有关层说明 2、测试2.1、官方测试2.2、opencv dnn2.2.1、仅运行到内部"NMS"步骤之前的层2.2.2、完整代码2.2.2、完整实现所有层 2.3、onnxruntime测试2.4、tensorrt 1…...

【python进阶】python图形化编程之美--tkinter模块初探

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

discuz点微同城源码34.7+全套插件+小程序前端

discuz点微同城源码34.7全套插件小程序前后端 模板挺好看的 带全套插件 自己耐心点配置一下插件 可以H5可以小程序...

ActiveMQ 介绍、下载、安装和控制台

ActiveMQ 介绍 Apache ActiveMQ 是一款非常成熟且功能全面的开源消息中间件&#xff0c;由Apache软件基金会维护。它遵循 Java Message Service (JMS) 规范&#xff0c;这意味着它提供了一组标准的 API&#xff0c;允许 Java 应用程序以一种标准化的方式发送和接收消息。 以下…...

MacOS M系列芯片一键配置多个不同版本的JDK

第一步&#xff1a;下载JDK。 官网下载地址&#xff1a;Java Archive | Oracle 选择自己想要下载的版本&#xff0c;一般来说下载一个jdk8和一个jdk11就够用了。 M系列芯片选择这两个&#xff0c;第一个是压缩包&#xff0c;第二个是dmg可以安装的。 第二步&#xff1a;编辑…...

源码文章上传无忧,论坛小程序支持

前言 在数字化时代&#xff0c;知识的分享与传播显得愈发重要。为了满足广大创作者和求知者的需求&#xff0c;我们推出了全新的论坛小程序&#xff0c;不仅支持文章、源码、链接等多样化内容的上传&#xff0c;还实现了付费观看功能&#xff0c;为创作者们提供了一个展示才华…...

Docker面试整理-如何优化Docker容器的性能?

优化Docker容器的性能可以从多个方面入手,以下是一些建议: 选择合适的基础镜像:使用轻量级的基础镜像,如基于Alpine Linux的镜像,可以减少镜像的大小和启动时间。避免使用过于庞大的操作系统镜像。优化Dockerfile:减少Dockerfile中的不必要指令和层,以最小化镜像的大小。…...

list(二)和_stack_queue

嗨喽大家好&#xff0c;时隔许久阿鑫又给大家带来了新的博客&#xff0c;list的模拟实现&#xff08;二&#xff09;以及_stack_queue&#xff0c;下面让我们开始今天的学习吧&#xff01; list(二)和_stack_queue 1.list的构造函数 2.设计模式之适配器和迭代器 3.新容器de…...

查询SQL02:寻找用户推荐人

问题描述 找出那些 没有被 id 2 的客户 推荐 的客户的姓名。 以 任意顺序 返回结果表。 结果格式如下所示。 题目分析&#xff1a; 这题主要是要看这null值会不会用&#xff0c;如果说Java玩多了&#xff0c;你去写SQL时就会有问题。在SQL中判断是不是null值用的是is null或…...

2、Tomcat 线程模型详解

2、Tomcat 线程模型详解 Tomcat I/O模型详解Linux I/O模型详解I/O要解决什么问题Linux的I/O模型分类 Tomcat支持的 I/O 模型Tomcat I/O 模型如何选型 网络编程模型Reactor线程模型单 Reactor 单线程单 Reactor 多线程主从 Reactor 多线程 Tomcat NIO实现Tomcat 异步IO实现 Tomc…...

对硬盘的设想:纸存、执行存

固态硬盘出现后&#xff0c;发现它的擦写次数受限&#xff0c;越是便宜的固态硬盘&#xff0c;擦写次数越少。于是&#xff0c;有了“纸存”的设想&#xff0c;即硬盘上的单元只能改写一次&#xff0c;就像拿钢笔在纸上写字一样。这时&#xff0c;文件系统、数据库该怎么设计&a…...

最新付会进群多群同时变现社群系统V3.5.3版本 详细教程+源码下载

市面1888最新付费进群多群同时变现系统V3.5.3版本 详细教程源码下载介绍&#xff1a; 续男粉变现&#xff0c;相亲群变现后 演化出来的最新多群同时变现系统 可同时进行40个群同时变现 可设置地域群&#xff0c;相亲&#xff0c;男粉变现等多种群 购买后包括详细的 域名服…...

python tk实现标签切换页面

import tkinter as tk from tkinter import ttk# 初始化主窗口 root tk.Tk() root.title("标签页示例")# 设置窗口大小 root.geometry("400x300")# 创建 Notebook 小部件 notebook ttk.Notebook(root) notebook.pack(expandTrue, fill"both")#…...

巴旦木脱青皮的设计【solidworks三维、cad图纸、论文、答辩稿】

巴旦木脱青皮设计是农产品加工领域的关键环节&#xff0c;其核心作用在于通过机械结构与工艺参数的协同优化&#xff0c;实现青皮与果仁的高效分离&#xff0c;同时避免果仁损伤。该设计需综合考虑物料特性、动力传递效率及设备稳定性&#xff0c;通过三维建模与二维图纸的精准…...

别再死记硬背了!用FPGA和Verilog HDL手把手带你玩转数字电路设计(附避坑指南)

用FPGA和Verilog HDL玩转数字电路设计&#xff1a;从理论到实战的避坑指南 数字电路设计常常让初学者感到抽象和枯燥——真值表、状态机、时序约束这些概念看似冰冷&#xff0c;但当你亲手用FPGA开发板点亮第一个LED时&#xff0c;一切都会变得生动起来。本文将带你用Xilinx Ar…...

手把手教你用n8n和Gemini 2.5 Flash搭建英语作文批改机器人(附完整工作流JSON)

从零构建AI英语作文批改系统&#xff1a;基于n8n与Gemini的自动化实践 在数字化教育浪潮中&#xff0c;教师面临的最大挑战之一是如何高效处理大量学生作业。英语作文批改尤其耗时——需要逐字阅读、语法检查、内容评估&#xff0c;最后还要给出建设性反馈。传统方式下&#xf…...

手把手教你用Matlab把PLL相噪曲线算成Jitter(附三种方法源码)

从PLL相噪曲线到Jitter计算的Matlab实战指南 在射频系统设计中&#xff0c;锁相环(PLL)的相位噪声性能直接影响通信质量与系统稳定性。频谱分析仪虽能捕捉相噪曲线&#xff0c;但工程师常需将其转换为更直观的时间抖动(Jitter)指标。本文将系统介绍三种Matlab实现方案&#xff…...

基于python开发的送货上门系统

目录同行可拿货,招校园代理 ,本人源头供货商功能模块划分技术实现要点扩展功能建议部署与维护项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作同行可拿货,招校园代理 ,本人源头供货商 功能模块划分 用户管理模块 用户注册与登录…...

Awesome-Awesome终极指南:如何快速找到任何技术领域的最佳资源

Awesome-Awesome终极指南&#xff1a;如何快速找到任何技术领域的最佳资源 【免费下载链接】awesome-awesome A curated list of awesome curated lists of many topics. 项目地址: https://gitcode.com/gh_mirrors/aw/awesome-awesome 在技术学习和开发过程中&#xff…...

ollama部署本地大模型|embeddinggemma-300m嵌入质量评估方法论

ollama部署本地大模型&#xff5c;embeddinggemma-300m嵌入质量评估方法论 1. 引言&#xff1a;为什么需要本地嵌入模型&#xff1f; 想象一下&#xff0c;你正在开发一个智能搜索系统&#xff0c;需要快速理解用户查询的语义含义&#xff0c;并在海量文档中找到最相关的内容…...

5个步骤搞定苹果设备Windows连接:从无法识别到无缝协作

5个步骤搞定苹果设备Windows连接&#xff1a;从无法识别到无缝协作 【免费下载链接】Apple-Mobile-Drivers-Installer Powershell script to easily install Apple USB and Mobile Device Ethernet (USB Tethering) drivers on Windows! 项目地址: https://gitcode.com/gh_mi…...

矿井排水系统直接关系到煤矿安全生产,今天咱们掰开揉碎了聊聊西门子S7-200 PLC控制三台水泵的实战经验。老规矩,先上干货再说原理

基于西门子PLC的煤矿排水系统控制&#xff0c;内容包括 [1]S7-200 PLC程序[2]MCGS6.2组态画面[3]电气图纸精品文档 共有3台水泵进行矿井排水&#xff0c;分别为1号水泵&#xff0c;2号水泵&#xff0c;3号水泵 其中1号&#xff0c;2号水泵是工作水泵&#xff0c;3号水泵是备用水…...

Phi-3-mini-4k-instruct-gguf步骤详解:supervisor服务管理与错误日志定位方法

Phi-3-mini-4k-instruct-gguf步骤详解&#xff1a;supervisor服务管理与错误日志定位方法 1. 模型概述 Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本&#xff0c;特别适合问答、文本改写、摘要整理和简短创作等场景。这个开箱即用的解决方案已…...