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,即顺序表。…...

(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
文件上传漏洞防御全攻略
要全面防范文件上传漏洞,需构建多层防御体系,结合技术验证、存储隔离与权限控制: 🔒 一、基础防护层 前端校验(仅辅助) 通过JavaScript限制文件后缀名(白名单)和大小,提…...