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

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查看权限&#xff0c;如果是白色的使…...

聚星文社和虹猫哪个好

聚星文社和虹猫是两个不同的公司&#xff0c;各有各的特点。下面是它们各自的优点&#xff1a; 聚星文社&#xff1a;Docshttps://docs.qq.com/doc/DRU1vcUZlanBKR2xy 聚星文社是一家传媒公司&#xff0c;专注于出版漫画、动画、小说等内容&#xff0c;拥有丰富的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&#xff1f;为什么需要 Vuex&#xff1f; Vuex 的核心概念stategettersmutationsactionsmodules Vuex 的安装和基本使用安装 Vuex创建 store在 Vue 应用中使用 store在组件中访问和修改状态 Vuex 的模块化模块化的好…...

无人机电子调速器详解!!!

电子调速器是无人机动力系统中的关键组件&#xff0c;主要负责将电池提供的直流电转换为交流电&#xff0c;并精确控制电机的转速&#xff0c;从而实现对无人机飞行状态的精确控制。以下是对无人机电子调速器的详细解析&#xff1a; 一、基本功能与原理 功能&#xff1a; 直…...

Clichouse数据导出导入(数据迁移)

背景&#xff1a;因为clickhouse数据持续增加&#xff0c;导致服务器磁盘不够使用&#xff0c;云服务器的系统盘不能扩容&#xff0c;所以只能进行迁移 连接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种蘑菇进行训练预测

该项目旨在利用卷积神经网络&#xff08;Convolutional Neural Networks, CNN&#xff09;实现蘑菇的自动识别。通过对蘑菇图片进行分类&#xff0c;可以有效地将不同类型的蘑菇进行辨别&#xff0c;对于蘑菇的研究、食用安全及自然保护等方面具有重要意义。本文将详细描述项目…...

[论文翻译]使用 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滚动轴承故障诊断系统

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

【论文分享】通过社交媒体图片和计算机视觉分析城市绿道的使用情况

城市街道为路面跑步提供了环境。本次给大家带来一篇SCI论文的全文翻译&#xff01;该论文提出了一种非参数方法&#xff0c;使用机器学习模型来预测路面跑步强度。该论文提供了关于路面跑步的实证证据&#xff0c;并突出了规划者、景观设计师和城市管理者在设计适于跑步的城市街…...

MySQL 在 Windows 和 Ubuntu 上的安装与远程连接配置简介

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

博达网站群管理平台 v6.0使用相关问题解决

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

C++—>STL中vector使用篇

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

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...