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

力扣72-编辑距离

题目链接

记忆化搜索:
解题关键:每次仅考虑两字符串word1、word2分别从0 - i修改成0-j下标的完全匹配(下标表示
临界条件:当 i 或 j 小于0时,表示该字符串为空,编辑距离确定为 y+1 或 x+1

int dp[501][501]={0};
class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size(),n=word2.size();for(int i=0;i<m;i++)for(int j=0;j<n;j++)dp[i][j]=INT_MAX;return dfs(m-1,n-1,word1,word2);}int dfs(int x,int y,string word1,string word2){if(x<0)return y+1;if(y<0)return x+1;if(dp[x][y]!=INT_MAX)return dp[x][y];if(word1[x]==word2[y])return dfs(x-1,y-1,word1,word2);int ans= min(min(dfs(x-1,y,word1,word2),dfs(x,y-1,word1,word2)),dfs(x-1,y-1,word1,word2))+1;dp[x][y]=ans;return ans;}
};

动态规划(区间dp)
由状态转移方程直接推得,自底向上
转移方程dp[i][j] = dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] + 1 此处 i / j 表示剩余待匹配长度

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size();int m = word2.size();//dp[i][j] = dp[i-1][j-1] or dp[i][j-1]/dp[i-1][j] + 1vector<vector<int>>dp(n+1, vector<int>(m+1, INT_MAX));//dp[i][0] = i  and dp[0][j] = jfor(int i=0;i<=n;i++){dp[i][0] = i;}for(int j=0;j<=m;j++){dp[0][j] = j;}for(int i=1;i<=n;i++){for(int j=1;j<=m;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], min(dp[i-1][j], dp[i-1][j-1])) + 1;}}}return dp[n][m];}
};

相关文章:

力扣72-编辑距离

题目链接 记忆化搜索&#xff1a; 解题关键&#xff1a;每次仅考虑两字符串word1、word2分别从0 - i修改成0-j下标的完全匹配(下标表示&#xff09; 临界条件&#xff1a;当 i 或 j 小于0时&#xff0c;表示该字符串为空&#xff0c;编辑距离确定为 y1 或 x1 int dp[501][501…...

K8S 删除pod的正确步骤

在日常的k8s运维过程中&#xff0c;避免不了会对某些pod进行剔除&#xff0c;那么如何才能正确的剔除不需要的pod呢&#xff1f; 首先&#xff0c;需要查出想要删除的pod # 可通过任意方式进行查询 kubectl get pods -A |grep <podname> kubectl get pods -n <names…...

羊大师分析,羊奶健康生活的营养源泉

羊大师分析&#xff0c;羊奶健康生活的营养源泉 羊奶&#xff0c;作为一种古老的饮品&#xff0c;近年来因其独特的营养价值和健康益处而备受关注。今天&#xff0c;羊大师就来探讨一下羊奶与健康之间的紧密联系。 羊奶富含蛋白质、脂肪、维生素和矿物质等多种营养成分。羊奶…...

刷屏一天GPT-4o,发现GPT4用的都还不熟练?戳这儿

以ChatGPT、LLaMA、Gemini、DALLE、Midjourney、Stable Diffusion、星火大模型、文心一言、千问为代表AI大语言模型带来了新一波人工智能浪潮&#xff0c;可以面向科研选题、思维导图、数据清洗、统计分析、高级编程、代码调试、算法学习、论文检索、写作、翻译、润色、文献辅助…...

力扣HOT100 - 139. 单词拆分

解题思路&#xff1a; 动态规划 class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordDictSet new HashSet(wordDict);boolean[] dp new boolean[s.length() 1];dp[0] true;for (int i 1; i < s.length(); i) {…...

rush 功能特性梳理

Rush 可以让 JavaScript 开发者更轻松地同时构建、发布多个 NPM 包&#xff0c;即将多个包或项目放到一个大仓库下管理。 仅需一次 NPM 安装 仅需一步&#xff0c;Rush 便可以将你项目的所有依赖安装到一个公共文件夹下&#xff0c;该文件夹并不像 “package.json” 一样位于项…...

算法分析与设计复习__递归方程与分治

总结自&#xff1a;【算法设计与分析】期末考试突击课_哔哩哔哩_bilibili 1.递归&#xff0c;递归方程 1.1递归条件: 1.一个问题的解可以分解为几个子问题的解&#xff1b; 2.这个问题与分解之后的子问题&#xff0c;除了数据规模不同&#xff0c;求解思路完全一样; 3.存在…...

apk-parse包信息解析

最近公司做项目&#xff0c;需要解析apk包的基本信息&#xff0c;上网找了好多资料&#xff0c;最终决定使用apk-parse。 .yml文件 引入jar包 <dependency> <groupId>net.dongliu</groupId> <artifactId>apk-parser</artifactId> <version&…...

AI绘画进阶工具ComfyUI 傻瓜整合包安装教程!模型共享,一键安装!

哈喽大家好&#xff0c;今天给大家分享一下AI绘画工具Stable Diffusion的另一种UI界面&#xff0c;常见的有&#xff1a; 窗口式界面的WebUI 节点式工作流的ComfyUI ComfyUI更加进阶一些&#xff0c;是一个节点式工作流的AI绘画界面&#xff0c;它高度可定制、自定义编辑Ai生…...

无人机摄影测量数据处理、三维建模及在土方量计算

原文链接&#xff1a;无人机摄影测量数据处理、三维建模及在土方量计算https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247603776&idx2&snd96440e116900a46a71c45ff77316896&chksmfa8217a7cdf59eb15da39dd6366378b98ca39b9c836b76a473ff292b67ee37a6ff6…...

大模型平台后端开发(xiaomi)

文章目录 算法题 算法题 1 三数之和 &#xff08;注意去重的边界条件&#xff0c;过几天再刷几次&#xff09; 2 长度最小的子数组 (代码随想录题目&#xff0c;滑动窗口) 3 用链表实现栈 package mainimport ("errors""fmt" )// Node 定义链表节点 type…...

性能测试工具—jmeter的基础使用

1.Jmeter三个重要组件 1.1线程组的介绍&#xff1a; 特点&#xff1a; 模拟用户&#xff0c;支持多用户操作多个线程组可以串行执行&#xff0c;也可以并行执行 线程组的分类&#xff1a; setup线程组&#xff1a;前置处理&#xff0c;初始化普通线程组&#xff1a;编写…...

前端 JS 经典:CommonJs 规范

1. Node 环境介绍 CommonJs 简称 CMJ&#xff0c;CMJ 的模块标准&#xff0c;必须在 node 的环境中才支持。在浏览器中用&#xff0c;是不行的。 查看电脑是否安装 node&#xff0c;通过打开终端&#xff0c;运行 node -v 查看是否返回 node 版本。返回则已安装。 CMJ 在 no…...

三分钟速览量化交易系统:揭秘QMT与Ptrade(内附免费提供渠道)

在当今金融市场的快速发展中&#xff0c;量化交易系统以其独特的优势&#xff0c;逐渐成为投资者们追求稳定收益的重要工具。其中&#xff0c;QMT和Ptrade作为两大知名的量化交易平台&#xff0c;受到了广泛关注。本文将带您在三分钟内快速了解量化交易系统&#xff0c;并深入揭…...

处理QTcpSocket接收到数据的槽函数

这段代码是一个典型的用于处理QTcpSocket接收到数据的槽函数 onReadyRead()。它尝试从发出信号的QTcpSocket读取数据&#xff0c;并将这些数据添加到一个成员变量 recvList&#xff08;假设这是一个 QList<QString> 类型&#xff09;。整体上&#xff0c;这段代码逻辑是合…...

回归的无分布预测推理

摘要 我们利用保形推理&#xff0c;开发了回归中无分布预测推理的一般框架。所提出的方法允许使用回归函数的任何估计量构建响应变量的预测带。所得的预测带在标准假设下保留了原始估计量的一致性&#xff0c;同时保证了有限样本边际覆盖&#xff0c;即使这些假设不成立。我们…...

有限域中的一些概念

一、单位元&#xff1a; 在自然数中&#xff0c;任意数加上0等于本身&#xff0c;0则为加法的单位元&#xff0c;任意数乘以1等于本身&#xff0c;1则为乘法单位元。 有限域中单位元用e表示&#xff0c;即乘法&#xff0c;加法的单位元都用e表示&#xff0c;不过这两者的e不一样…...

使用css的box-reflect属性制作倒影效果

box-reflect 是一个在 CSS 中创建元素倒影效果的非标准属性。尽管它在过去的一些 WebKit 浏览器中&#xff08;如旧版的 Safari 和 Chrome&#xff09;得到了支持&#xff0c;但由于它并未成为 CSS 标准的一部分&#xff0c;因此在现代浏览器中的兼容性较差。以下是对 box-refl…...

ChatGPT 4o 使用案例之一

2024年GPT迎来重大更新&#xff0c;OpenAI发布GPT-4o GPT-4o&#xff08;“o”代表“全能”&#xff09; 它可以接受任意组合的文本、音频和图像作为输入&#xff0c;并生成任意组合的文本、音频和图像输出。它可以在 232 毫秒内响应音频输入&#xff0c;平均为 320 毫秒&…...

【免费Web系列】大家好 ,今天是Web课程的第一天点赞收藏关注,持续更新作品 !

开干,开干!!! 1. 前端开发介绍 我们介绍Web网站工作流程的时候提到&#xff0c;前端开发&#xff0c;主要的职责就是将数据以好看的样式呈现出来。说白了&#xff0c;就是开发网页程序&#xff0c;如下图所示&#xff1a; 那在讲解web前端开发之前&#xff0c;我们先需要对we…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...