day45-dynamic programming-part12-8.16
tasks for today:
1. 115.不同的子序列
2. 583.两个字符串选的删除操作
3. 72.编辑距离
4. 总结编辑两个序列关系的问题
-------------------------------------------------------------------
1. 115.不同的子序列
In this practice, it is necessary to compare with the practice 392, the essense of practice 392 is finding the length of longest common string, while in this practice, the dp reocrd the times that t[0:j] appears in s[:i];
the essence is the recursive equation and the initialization.
recursive equation: discerned by if s[i-1] == t[j-1], when true, the dp[i][j] actually consist of two parts, the dp[i-1][j-1] is easy to understand, the dp[i-1][j] is a thinker, this actually include all the nums of condition where t[:j] appears in s section which is shorter thans[s:i].
The initialization's key point is the dp[i][0] = 1 and dp[0][j] = 0, void string t="" is counted as a child string, that is why the dp[i][0] is initialized as 1.
class Solution:def numDistinct(self, s: str, t: str) -> int:if len(s) < len(t): return 0if len(s) >= len(t):if len(t) == 1 and t[0] not in s: return 0dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]for i in range(len(s)):dp[i][0] = 1for i in range(1, len(s)+1):for j in range(1, len(t)+1):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[-1][-1]
2. 583.两个字符串选的删除操作
In this practice, the key difference are also lied in the recursive equation and the initialization.
It is intuitive to define the dp[i][j] as the min actions to make word1[:i] and word2[:j] equal.
the essence of the recursive equation is when the word1[i-1] != word2[j-1], the state of dp[i][j] can be derived from the dp[i-1][j] or dp[i][j-1] or dp[i-1][j-1]
class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(1, len(word1)+1):dp[i][0] = ifor j in range(1, len(word2)+1):dp[0][j] = jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+1):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, dp[i-1][j]+1, dp[i][j-1]+1)return dp[-1][-1]
3. 72.编辑距离
This practice is an extension of practice 583, which allows for more operations other than deleting.
The essense of the recursive equation also lies in the operation of condition "word1[i-1] != word2[j-1]". Be noted that the deleting of word1 is equal to addition on word2, since this practice count the least number of operation, instead of options of operation, so it is ok only choose one apprah.
class Solution:def minDistance(self, word1: str, word2: str) -> int:dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]for i in range(1, len(word1)+1):dp[i][0] = ifor j in range(1, len(word2)+1):dp[0][j] = jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+1):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-1][j], dp[i][j-1]) + 1return dp[-1][-1]
4. a summary of practice 392/115/583/72
these 4 practices are related to the relationship / edition of two strings or sequence,
(1) from the configuration:
practice 392/115 discuss the relationship, which 392 concentrated on true/false of containing, while practice 115 focuses on the times of containing.
practice 583/72 dicuss the edition of two lists for making them to achieve a specific requirement such as being same, which 583 concentrates on only using deleting, while 72 allows for more operations such as replacement or addition.
(2) from the code-dp:
392's dp records the max length of common string, while 115 records the times of containing;
583's dp records the delete times, while the 72 records the times of operaaation
(3) from the code-initialization:
all of them need to initialize the dp[i][0] and dp[0][j]
392 update them as 1
115 of update dp[i][0] as 1
583/72 update dp[i][0] as i, while dp[0][j] as j
相关文章:
day45-dynamic programming-part12-8.16
tasks for today: 1. 115.不同的子序列 2. 583.两个字符串选的删除操作 3. 72.编辑距离 4. 总结编辑两个序列关系的问题 ------------------------------------------------------------------- 1. 115.不同的子序列 In this practice, it is necessary to compare with t…...
C# String的方法
目录 #region 知识点九 字符串切割 #region 知识点一 字符串指定位置获取 #region 知识点二 字符串拼接 #region 知识点三 正向查找字符位置 #region 知识点四 反向查找指定字符串位置 #region 知识点五 移除指定位置后的字符 #region 知识点六 替换指定字符串 #region 知识点七…...
Oracle RAC vs Clusterware vs ASM
Oracle RAC vs Clusterware vs ASM Oracle RACCache FusionRAC后台进程自动负载管理DBA管理工具Oracle ClusterwareCRS组件HAS组件管理工具Oracle ASMASM实例ASM磁盘组镜像和故障组ASM磁盘ASM文件Oracle RAC RAC即Real Application Clusters,是一种Oracle高可用部署架构。Orac…...
“华为杯”第十五届中国研究生数学建模竞赛-F题:机场新增卫星厅对中转旅客影响的研究
目录 摘 要: 一、 问题重述 1.1 研究背景 1.2 已知信息 1.3 需要解决的问题 二、 模型假设 三、 符号说明 四、 问题一模型的建立与求解 4.1 问题描述与分析 4.2 模型的求解 4.3 求解结果与分析 五、 问题二模型的建立与求解 5.1 问题描述与分析 5.2 模型的求解 5.3 求解结果与…...

正点原子linux开发板 qt程序交叉编译执行
1.开发板光盘 A-基础资料->5、开发工具->1、交叉编译器->fsl-imx-x11-glibc-x86_64-meta-toolchain-qt5-cortexa7hf-neon-toolchain-4.1.15-2.1.0.sh 拷贝到 Ubuntu 虚拟机 用文件传输系统或者共享文件夹传输到linux虚拟机 用ls -l查看权限,如果是白色的使…...

聚星文社和虹猫哪个好
聚星文社和虹猫是两个不同的公司,各有各的特点。下面是它们各自的优点: 聚星文社:Docshttps://docs.qq.com/doc/DRU1vcUZlanBKR2xy 聚星文社是一家传媒公司,专注于出版漫画、动画、小说等内容,拥有丰富的IP资源和创作…...

三十八、【人工智能】【机器学习】【监督贝叶斯网络(Bayesian Networks)学习】- 算法模型
系列文章目录 第一章 【机器学习】初识机器学习 第二章 【机器学习】【监督学习】- 逻辑回归算法 (Logistic Regression) 第三章 【机器学习】【监督学习】- 支持向量机 (SVM) 第四章【机器学习】【监督学习】- K-近邻算法 (K-NN) 第五章【机器学习】【监督学习】- 决策树…...

[书生大模型实战营][L0][Task1] Linux 远程连接 InternStudio
[书生大模型实战营][Task1] Linux 远程连接 InterStudio 1. 申请 InterStudio 账号 https://studio.intern-ai.org.cn/console/dashboard 2. ssh 生成公匙与密匙 使用 ssh-gen 生成公匙与密匙 # 1. ssh-gen ssh-gen# 2. 查看生成的文件 ls ~/.ssh# 3. 打开生成的公匙&#…...

【vue教程】六. Vue 的状态管理
目录 往期列表本章涵盖知识点回顾Vuex 的基本概念什么是 Vuex?为什么需要 Vuex? Vuex 的核心概念stategettersmutationsactionsmodules Vuex 的安装和基本使用安装 Vuex创建 store在 Vue 应用中使用 store在组件中访问和修改状态 Vuex 的模块化模块化的好…...

无人机电子调速器详解!!!
电子调速器是无人机动力系统中的关键组件,主要负责将电池提供的直流电转换为交流电,并精确控制电机的转速,从而实现对无人机飞行状态的精确控制。以下是对无人机电子调速器的详细解析: 一、基本功能与原理 功能: 直…...
Clichouse数据导出导入(数据迁移)
背景:因为clickhouse数据持续增加,导致服务器磁盘不够使用,云服务器的系统盘不能扩容,所以只能进行迁移 连接clickhouse查看要迁移那些数据库 rootjcdata:~/buckup/clickhouse# clickhouse-client -udefault --password 123456…...
Java基础——IService.class 中查询数据方法list() 源码剖析及使用
下面详细介绍Mybatis-plus 的默认服务IService.class 中的查询数据的方法及使用。 方法定义及其详细介绍 default List<T> list(Wrapper<T> queryWrapper) default List<T> list(Wrapper<T> queryWrapper) {return this.getBaseMapper().selectList(q…...

MySQL库表的基本操作
目录 1.库的操作1.1 创建数据库1.2字符集和校验规则①查看系统默认字符集以及校验规则②查看数据库支持的字符集③查看数据库支持的字符集校验规则④校验规则对数据库的影响 1.3操纵数据库①查看数据库②显示创建的数据库的语句③修改数据库④数据库删除⑤备份和恢复⑥还原注意…...

基于ResNeSt50神经网络模型的蘑菇分类设计与实现,使用注意力机制,分别对应8种蘑菇进行训练预测
该项目旨在利用卷积神经网络(Convolutional Neural Networks, CNN)实现蘑菇的自动识别。通过对蘑菇图片进行分类,可以有效地将不同类型的蘑菇进行辨别,对于蘑菇的研究、食用安全及自然保护等方面具有重要意义。本文将详细描述项目…...

[论文翻译]使用 BERT 检测安卓恶意软件
Android Malware Detection Using BERT Souani B, Khanfir A, Bartel A, et al. Android malware detection using bert[C]//International Conference on Applied Cryptography and Network Security. Cham: Springer International Publishing, 2022: 575-591. 摘要 在本文…...

LabVIEW滚动轴承故障诊断系统
滚动轴承是多种机械设备中的关键组件,其性能直接影响整个机械系统的稳定性和安全性。由于轴承在运行过程中可能会遇到多种复杂的工作条件和环境因素影响,这就需要一种高效、准确的故障诊断方法来确保机械系统的可靠运行。利用LabVIEW开发的故障诊断系统&…...

【论文分享】通过社交媒体图片和计算机视觉分析城市绿道的使用情况
城市街道为路面跑步提供了环境。本次给大家带来一篇SCI论文的全文翻译!该论文提出了一种非参数方法,使用机器学习模型来预测路面跑步强度。该论文提供了关于路面跑步的实证证据,并突出了规划者、景观设计师和城市管理者在设计适于跑步的城市街…...

MySQL 在 Windows 和 Ubuntu 上的安装与远程连接配置简介
MySQL 是一个广泛使用的开源关系型数据库管理系统,它提供了多用户、多线程的数据库服务。本文将介绍如何在 Windows 和 Ubuntu 操作系统上安装 MySQL,并配置远程连接。 Windows 上的 MySQL 安装 1. 下载 MySQL Installer 访问 MySQL 官方网站下载 Win…...

博达网站群管理平台 v6.0使用相关问题解决
1 介绍 最近受人所托,需要用博达网站群管理平台创建一个网站。该平台的内部版本为9.8.2。作为一个能直接从代码创建网站系统的人,初次使用本平台,刚开始感觉摸不着头脑。因为该平台存在的目的,就是让不懂代码的人能快速创建网站&…...

C++—>STL中vector使用篇
文章目录 🚩前言1、vector容器的概述2、vector构造函数的使用3、vector遍历方式4、vector中Capacity相关接口5、vector插入和删除的使用 🚩前言 前面描述了字符串string的相关知识,接下来描述第二个常用容器——vector,即顺序表。…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...

376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...

Python异步编程:深入理解协程的原理与实践指南
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 持续学习,不断…...
更新 Docker 容器中的某一个文件
🔄 如何更新 Docker 容器中的某一个文件 以下是几种在 Docker 中更新单个文件的常用方法,适用于不同场景。 ✅ 方法一:使用 docker cp 拷贝文件到容器中(最简单) 🧰 命令格式: docker cp <…...
生成对抗网络(GAN)损失函数解读
GAN损失函数的形式: 以下是对每个部分的解读: 1. , :这个部分表示生成器(Generator)G的目标是最小化损失函数。 :判别器(Discriminator)D的目标是最大化损失函数。 GAN的训…...
关于疲劳分析的各种方法
疲劳寿命预测方法很多。按疲劳裂纹形成寿命预测的基本假定和控制参数,可分为名义应力法、局部应力一应变法、能量法、场强法等。 1名义应力法 名义应力法是以结构的名义应力为试验和寿命估算的基础,采用雨流法取出一个个相互独立、互不相关的应力循环&…...