代码随想录算法训练营day50|动态规划12
不同的子序列
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。、
编辑距离中的删除元素,其实就是直接变数字,其只删除原来的较长的数组里的元素
递推模拟,使用s的最后一个元素匹配,或者删除最后一个元素看前面一个是否匹配
初始化,dp[i][0]=1表示s不为空,t为空,这样把s删到空就一定有一个,同理dp[0][i]=0,重叠部分dp[0][0]就等于空字符串匹配空字符串,为1
定义为int,出现了超时错误
所以可以用longlongint 的别名 uint64_t
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));for(int i=0;i<s.size();i++) dp[i][0]=1;for(int j=1;j<t.size();j++) dp[0][j]=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]+dp[i-1][j];}else{dp[i][j]=dp[i-1][j];}}}return dp[s.size()][t.size()];}
};
两个字符串的删除操作
其实就是两个字符串都可以删除了
递推公式如下
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+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,dp[i][j-1]+1);}}return dp[word1.size()][word2.size()];}
};
思路二是,先求出公共子序列的长度,再用两个字符串的总长度减去公共子序列的长度
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 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], dp[i][j-1]);}}return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;}
};
编辑距离(动规经典问题)
=为什么这道题不能采用上一题的思路二,先求出公共子序列的长度,再用两个字符串的总长度减去公共子序列的长度,因为很可能长度一样,但可以只替换一次就完成,但思路2会要求按着顺序删除
相关文章:
代码随想录算法训练营day50|动态规划12
不同的子序列 给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。、 编辑距离中的删除元素,其实就是直接变数字,其只删除原来的较长的数组里的元素 递推模拟,使用s的最后一个元素匹配,或者删除…...
图像生成-扩散模型的经典之作DDPM
论文:https://arxiv.org/pdf/2006.11239 项目:https://github.com/hojonathanho/diffusion Denoising Diffusion Probabilistic Models (DDPM) 是一种生成模型,它通过一系列逐步添加噪声的过程将数据点映射到一个简单的先验分布(…...
知识拓展 ?. 连选链操作
?. 连选链操作 ?. 可选链操作符 ?. 是可选链操作符,常用于访问引用类型具有不确定性的内部数据时,比如要访问一个对象中的数组,不确定数组一定有数据就可以使用 ? 取读取它的 length 属性,如果对象没有这个属性也仅会返回 …...
API设计指南:详解HTTP状态码错误解析、HTTP方法及参数命名规则
目录 1、HTTP API规范1.1 原则1.2 协议1.3 版本1.4 路径1.5 HTTP 方法(Method)1.6 过滤信息1.7 参数命名1.8 HTTP 状态码(Response Code)1.9 鉴权 2、状态码2.1 API返回基础规范2.2 常见的 HTTP 状态码2.3 API错误信息应该放到响应…...
【D3.js in Action 3 精译_043】5.1 饼图和环形图的创建(三):圆弧的绘制
当前内容所在位置: 第五章 饼图布局与堆叠布局 ✔️ 5.1 饼图和环形图的创建 ✔️ 5.1.1 准备阶段(一)5.1.2 饼图布局生成器(二)5.1.3 圆弧的绘制(三) ✔️5.1.4 数据标签的添加(四&…...
7. 一分钟读懂“单例模式”
7.1 模式介绍 单例模式就像公司里的 打印机队列管理系统,无论有多少员工提交打印任务,大家的请求都汇总到唯一的打印管理中心,按顺序排队输出。这个中心必须全局唯一,避免多个队列出现资源冲突,保证打印任务井然有序。…...
如何让谷歌外链看起来更真实?
在SEO优化过程中,外链的自然性往往会被忽视,尤其是在一些急于见效的策略中,外链往往集中在高权重的少数几个网站上,导致外链结构单一且缺乏多样性。这样的外链网络容易让搜索引擎怀疑其真实性,进而影响网站排名。如何才…...
C标签和 EL表达式的在前端界面的应用
目录 前言 常用的c标签有: for循环 1 表示 普通的for循环的 2 常在集合中使用 表示 选择关系 1 简单的表示如果 2 表示如果。。否则。。 EL表达式 格式 : ${属性名/对象/ 集合} 前言 本篇博客介绍 c标签和el表达式的使用 使用C标签 要引入 …...
Luma 视频生成 API 对接说明
Luma 视频生成 API 对接说明 随着 AI 的应用变广,各类 AI 程序已逐渐普及。AI 已逐渐深入到人们的工作生活方方面面。而 AI 涉及的行业也越来越多,从最初的写作,到医疗教育,再到现在的视频。 Luma 是一个专业高质量的视频生成平…...
嵌入式基础:Linux C语言:Day7
重点: strlen()函数\strcpy()函数\strcat实现\strcmp()实现 数组的清空:bzero函数、memset函数 一、字符数组 <1> 概念 字符数组本质上就是一个数组,保存一个个字符,也一般用来保存字符串 字符串由多个字符组成的一个字符…...
阿里云盘permission denied
问题是执行 ./aliyunpan 时遇到了 Permission denied 的错误。这通常是因为文件没有执行权限。以下是解决问题的步骤: 检查文件权限 运行以下命令检查文件的权限: ls -l aliyunpan输出中会看到类似以下内容: -rw-r--r-- 1 user group 123…...
Flink学习连载文章12--FlinkSQL高级部分
eventTime 测试数据如下: {"username":"zs","price":20,"event_time":"2023-07-17 10:10:10"} {"username":"zs","price":15,"event_time":"2023-07-17 10:10:3…...
缓冲区溢出基础与实践
缓冲区溢出 缓冲区溢出是指当计算机向缓冲区内填充数据时超过了缓冲区本身的容量,溢出的数据覆盖在合法数据上。理想的情况是:程序检查数据长度并不允许输入超过缓冲区长度的字符,但是绝大多数程序都会假设数据长度总是与所分配的储存空间相匹…...
matlab figure函数 single 数据类型
1.matlab figure函数详细介绍 在MATLAB中,figure函数用于创建新的图形窗口或激活现有的图形窗口。以下是figure函数的详细介绍和用法: 基本用法 创建新图形窗口:不带任何参数调用figure会创建一个新的图形窗口,并将其设为当前活…...
量化交易系统开发-实时行情自动化交易-8.15.Ptrade/恒生平台
19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来会对于Ptrade/恒生平台介绍。 P…...
Vue03
目录 一、今日目标 1.生命周期 2.综合案例-小黑记账清单 3.工程化开发入门 4.综合案例-小兔仙首页 二、Vue生命周期 三、Vue生命周期钩子 四、生命周期钩子小案例 1.在created中发送数据 六、工程化开发模式和脚手架 1.开发Vue的两种方式 2.Vue CLI脚手架 基本介绍…...
【AI学习】Mamba学习(十九):关于S4-FouT
在前面《Mamba学习(十六):从S4到S5模型》一文中,提到了S4D-Lin,其具体状态矩阵A的初始化形式为: S4D-Lin对比S4D-Inv是一种更简单的形式,可以看作是对S4-FouT(S4的另外一种变体&am…...
YOLOv5-C3模块实现
YOLOv5-C3模块实现 🍨 本文为🔗365天深度学习训练营 中的学习记录博客 🍖 原作者:K同学啊 电脑系统:Windows11 显卡型号:NVIDIA Quadro P620 语言环境:python 3.9.7 编译器:jupyt…...
ubuntu下Qt5自动编译配置QtMqtt环境(10)
文章目录 [toc]1、概述2、下载QtMqtt源码3、编译4、验证5、参考6、视频 更多精彩内容👉内容导航 👈👉Qt网络编程 👈 1、概述 Qt默认是不包含mqtt库的,如果需要使用到mqtt库就只能自己编译配置; 网络所有的…...
切比雪夫不等式:方差约束下的概率估计
切比雪夫不等式:方差约束下的概率估计 背景 在概率分析中,切比雪夫不等式是一个常用的工具,它通过引入随机变量的 方差信息,给出了偏离均值的概率界限。这一不等式是对 马尔科夫不等式 的自然扩展,结合了更丰富的分布…...
SIP系列七:ICE框架(P2P通话)
我的音视频/流媒体开源项目(github) SIP系列目录 目录 一、NAT 1、NAT介绍 2、NAT类型 2.1、 完全圆锥型NAT 2.2、受限圆锥型NAT 2.3、端口受限圆锥型NAT 2.4、对称NAT 3、NAT打洞 3.1、不同一NAT下 3.2、同一NAT下 二、ICE 三、ICE中的SDP 至此&#x…...
小程序-基于java+SpringBoot+Vue的智慧校园管理系统设计与实现
项目运行 1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境:Tomcat 7.x,8.x,9.x版本均可 4.硬件环境:…...
Visual Studio 2022创建离线安装包
步骤1: 下载 Visual Studio 引导程序(最新版) 历史版本 步骤2 新建文件夹“E:\VS2022”,将下载的“vs_Professional.exe”拷贝到文件夹下在此文件夹窗口按住shift鼠标右键,选择“在此处打开powershell窗口” 步骤3 根据需要将代码复制到…...
Android 实现中英文切换
在开发海外项目的时候,需要实现app内部的中英文切换功能,所有的英文都是内置的,整体思路为: 创建一个sp对象,存储当前系统的语言类型,然后在BaseActivity中对语言进行判断; //公共Activitypubl…...
CmakeLists学习刨根问底
必要的两项内容 cmake_minimum_required(VERSION 2.5)project(mymuduo) 这行代码指定了构建项目所需的CMake最低版本为2.5。CMake是一个跨平台的自动化构建系统,它使用CMakeLists.txt文件来定义项目的构建过程。定义项目的名称为mymuduo。CMake将使用这个名称来生成…...
策略模式实战 - 猜拳游戏
**可以整体的替换一套算法,这就是策略模式。**这样对于同一个问题,可以有多种解决方案——算法实现的时候,可以通过策略模式来非常方便的进行算法的整体替换,而各种算法是独立封装好的,不用修改其内部逻辑。 具体的实…...
VoCo-LLaMA: Towards Vision Compression with Large Language Models
视觉语言模型在各种多模态任务上取得了显著的成功,但经常受到有限上下文窗口和处理高分辨率图像输入和视频的高计算成本的瓶颈。视觉压缩可以通过减少视觉令牌数量避免该问题。先前方法使用额外模块压缩视觉令牌并强制LLM理解压缩的令牌。然而,LLM对视觉…...
每日小知识
Kafka是一个分布式流平台,具有高性能、高可靠性和可扩展性的特点。它主要用于处理实时的数据流,将数据以高吞吐量的方式进行发布和订阅。以下是关于Kafka的几个基本概念和优势的介绍: 概念: 生产者(Producer…...
Linux其二设置端口号,静态ip以及命令
目录 1、VI编辑器 【linux版本的文本文件】 2) 补充的vi编辑器的其他内容(了解) 2、ln 连接的意思 link的缩写 3、文件的查看 【重点】 4、压缩与解压(重点) 5、find 查找命令 6、which & whereis 作用是一样的,表示某…...
吉林大学23级数据结构上机实验(第7周)
A 去火车站 寒假到了,小明准备坐火车回老家,现在他从学校出发去火车站,CC市去火车站有两种方式:轻轨和公交车。小明为了省钱,准备主要以乘坐公交为主。CC市还有一项优惠政策,持学生证可以免费乘坐一站轻轨&…...
SpringBoot(整合MyBatis + MyBatis-Plus + MyBatisX插件使用)
文章目录 1.整合MyBatis 1.需求分析2.数据库表设计3.数据库环境配置 1.新建maven项目2.pom.xml 引入依赖3.application.yml 配置数据源4.Application.java 编写启动类5.测试6.配置类切换druid数据源7.测试数据源是否成功切换 4.Mybatis基础配置 1.编写映射表的bean2.MonsterMap…...
【2024最新】基于Springboot+Vue的网上图书商城平台Lw+PPT
作者:计算机搬砖家 开发技术:SpringBoot、php、Python、小程序、SSM、Vue、MySQL、JSP、ElementUI等,“文末源码”。 专栏推荐:SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:Java精选实战项…...
JAVA-面向对象基础
文章目录 概要封装多态抽象类接口内部类为什么需要内部类 概要 面向对象是一种编程范式或设计哲学,它将软件系统设计为由多个对象组成,这些对象通过特定的方式相互作用 封装 将数据和操作数据的方法封装在一个类中,并通过访问修饰符控制对…...
Y3编辑器官方文档1:编辑器简介及菜单栏详解(文件、编辑、窗口、细节、调试)
文章目录 一、新建项目二、 编辑器主界面2.1 游戏场景2.2 导航栏/菜单栏2.3 功能栏三、菜单栏详细介绍3.1 文件3.1.1 版本管理3.1.2 项目管理(多关卡)3.1.2.1 多关卡功能说明3.1.2.2 关卡切换与关卡存档3.2 编辑3.2.1 通用设置3.2.2 键位设置3.3 窗口(日志)3.4 细节3.4.1 语言…...
力扣94题:二叉树的中序遍历
力扣94题:二叉树的中序遍历(C语言实现详解) 题目描述 给定一个二叉树的根节点 root ,返回它的中序遍历(Inorder Traversal)。 中序遍历的规则是: 先访问左子树;再访问根节点&…...
【数据结构】二叉树的性质和存储结构
性质 在二叉树的第i层上至多有2^{i-1}个结点,至少有1个结点 深度为k的二叉树至多有2^{k-1}个结点(k≥1),至少有k个结点 对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0n21 具有n个结点的完…...
【Spring项目】图书管理系统
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 一:项目实现准备 1:需求 (1)登录 2:准备…...
TCP编程案例
笔记:(本题可能需要的) TCP协议: TCP协议进行通信的两个应用进程:客户端、服务端。 使用TCP协议前,须先建立TCP连接,形成基于字节流的传输数据通道 传输前,采用“三次握手”方式…...
PyTorch 实现动态输入
使用 PyTorch 实现动态输入:支持训练和推理输入维度不一致的 CNN 和 LSTM/GRU 模型 在深度学习中,处理不同大小的输入数据是一个常见的挑战。许多实际应用需要模型能够灵活地处理可变长度的输入。本文将介绍如何使用 PyTorch 实现支持动态输入的 CNN 和…...
网络数据库
创建删除修改模式create schemadrop schema表create tabledrop tablealter table视图create view drop view索引create indexdrop index alter index 定义模式:create schema 《模式名》 authorization 《用户名》表定义语句 视图定义语句 授权定义语句//未指…...
【软考速通笔记】系统架构设计师⑲——专业英语
文章目录 一、前言二、常用名词三、架构风格四、非功能需求五、应用架构六、软件架构重用 一、前言 笔记目录大纲请查阅:【软考速通笔记】系统架构设计师——导读 二、常用名词 名词翻译architecture架构system系统design设计requirements需求components组件constr…...
Android APP自学笔记
摘抄于大学期间记录在QQ空间的一篇自学笔记,当前清理空间,本来想直接删除掉的,但是感觉有些舍不得,因此先搬移过来。 Android导入已有外部数据库 2015.06.26在QQ空间记录:在Android中不能直接打开res aw目录中的数据…...
Spring 事务和事务传播机制
Spring 事务和事务传播机制 一、Spring 事务的基本概念 事务是一组操作,被视为一个不可分割的工作单元,要么全部完成,要么全部失败回滚,以此来确保数据的一致性和完整性。Spring事务管理允许我们在应用程序中声明式地或编程式地…...
VSCode(四)CMake调试
1. 工具准备 1.1 C环境插件 1.2 CMake插件 2. Cmake工程 2.1 创建项目文件夹 ex:CMAKE_TEST 2.2 创建CMake工程 (shift ctl P), 选择"CMAKE: Quick Start": 2.3 填写project name: (ex: test_cmake) 2.4 选择”Executable“ 项目文件内会自动…...
创建存储过程
在student数据库中,创建一个名为ST_CHAXUN_01的存储过程,该存储过程返回计算机系学生的“姓名”、“性别”、“出生日期”信息。 操作步骤如下: ① 在“对象资源管理器”窗格中,展开“数据库”结点。 ② 单击相应的数据库&#…...
macOS 15.1.1 (24B2091) 系统中快捷键符号及其代表的按键的对照表
以下是 macOS 15.1.1 (24B2091) 系统中快捷键符号及其代表的按键的对照表: 符号按键名称描述⌘Command (Cmd)常用的功能键,用于执行大多数快捷操作。⌥Option (Alt)Option 键,常用于辅助操作和特殊字符输入。⇧ShiftShift 键,常用…...
ftp服务器搭建-安装、配置及验证
ftp服务器搭建-安装、配置及验证 #安装 sudo apt-get install vsftpd #配置文件 cat > /etc/vsftpd.conf << "EOF" listenNO listen_ipv6YES anonymous_enableNO local_enableYES write_enableYES dirmessage_enableYES use_localtimeYES xferlog_enable…...
windows ping 执行过程分析
控制台 PS C:\Users\Admin> ping mcs.zijieapi.com正在 Ping mcs.zijieapi.com [223.109.117.226] 具有 32 字节的数据: 来自 223.109.117.226 的回复: 字节32 时间31ms TTL49 来自 223.109.117.226 的回复: 字节32 时间30ms TTL49 来自 223.109.117.226 的回复: 字节32 时…...
强大的远程同步工具-rsync
rsync 强大的远程同步工具,也可用于本地目录和本地目录的同步,它最大的特点就是会自动判断进行增量同步; # “演示文档”后加了/,代表传输的是文件,建议destination也指定一个目录,该目录可以不存在&…...
蝉联第一 | IDC云系统软件市场报告2024H1,云轴科技ZStack独立云厂商第一
2024年12月,根据全球知名的IT市场研究和咨询公司IDC最新发布的《中国云系统软件市场跟踪报告2024H1》显示,2024年上半年中国云系统软件市场规模达到27.93亿元人民币,同比增长11.6%。在这一增长趋势中,云轴科技ZStack作为云系统软件…...
不判处贪官李鹏新死刑,我国吏治很难清朗
近日,陕西省宝鸡市中级人民法院一审开庭审理了新疆维吾尔自治区党委原副书记李鹏新受贿案,由于李鹏新曾经在内蒙古自治区担任党委组织部长一职,他的腐败恶行受到了内蒙古广大干部群众的极大关注。据检察机关指控,李鹏新在1999年至2023年的20多年时间里,受贿款物折合人民币…...
联合国前副秘书长霍克希尔德:贸易保护主义破坏全球经济稳定
新华社萨拉热窝1月14日电(记者殷晓圣)联合国前副秘书长法布里齐奥·霍克希尔德近日接受新华社记者专访时表示,如果美国新一任政府就职后提出新的保护主义关税政策,对中国、加拿大、墨西哥等贸易伙伴加征关税,将损害全球贸易、扰乱供应链、加重美国消费者负担,对…...
数据显示中国最低工资近年来增长停滞,增长率仅10年前的一半
自2015年起,各省最低工资调整趋于停滞,上调频率下降,增长率降低。一方面,调整最低工资标准的频率已由原来的至少两年一次,变为至少三年一次,甚至在疫情期间全面停滞。另一方面,最低工资的年均增长率也大幅下降,平均增长率由2013年的约14%左右降到2022年仅有5%左右。此外…...
喊吴京出动“战狼”,如此阴阳怪气有意思吗?
这两天不断有人在社交媒体上“问候”吴京,呼吁他出动“战狼团队”解救被电诈集团绑架到缅甸妙瓦底的中国人。他们大多阴阳怪气,但老胡也看到一个公司的老总说得正儿八经,声称吴京那样做最合适,会一呼百应,还说吴京如果去了拍出新《战…...
工信部:到2027年建设1万个5G工厂
记者12月30日获悉,工业和信息化部印发《打造“5G+工业互联网”512工程升级版实施方案》(下称《实施方案》),提出到2027年,“5G+工业互联网”广泛融入实体经济重点行业领域,网络设施、技术产品、融合应用、产业生态、公共服务五方面能…...
清除腐败存量、遏制腐败增量,应尽快实行“官员财产公示制”
2025年1月6日,二十届中央纪委四次全会强调:当前反腐败斗争形势仍然严峻复杂,腐败存量尚未清除,增量还在持续发生,铲除腐败滋生土壤和条件任务仍然艰巨繁重;反腐败斗争必须坚定不移,任何犹豫动摇、松懈手软或半途而废,都将犯颠覆性错误。笔者认为,无论是清除腐败存量、…...