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

算法刷题:300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组、1143. 最长公共子序列

300. 最长递增子序列

1.dp定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2.递推公式:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值

 3.初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}
};

674. 最长连续递增序列

1.dp定义:dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]

2.递推公式:如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。

即:dp[i] = dp[i - 1] + 1;

因为本题要求连续递增子序列,所以就只要比较nums[i]与nums[i - 1],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)。

 3.dp[i]应该初始1;        

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};

718. 最长重复子数组

1.dp定义:以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。

2.递推公式:当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;

根据递推公式可以看出,遍历i 和 j 要从1开始!

3.初始化:根据dp[i][j]的定义,dp[i][0] 和dp[0][j]其实都是没有意义的!

但dp[i][0] 和dp[0][j]要初始值,因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;

所以dp[i][0] 和dp[0][j]初始化为0。

举个例子A[0]如果和B[0]相同的话,dp[1][1] = dp[0][0] + 1,只有dp[0][0]初始为0,正好符合递推公式逐步累加起来。

注:如果dp数组以i,j为结尾,那么初始化时,应该为dp[i] = dp[j]时初始化为1

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

1143. 最长公共子序列

和上一题的区别是不要求是连续的了,但要有相对顺序

1.dp含义:dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

2.递推公式:如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[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 dp[text1.size()][text2.size()];}
};

相关文章:

算法刷题:300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组、1143. 最长公共子序列

300. 最长递增子序列 1.dp定义&#xff1a;dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 2.递推公式&#xff1a;if (nums[i] > nums[j]) dp[i] max(dp[i], dp[j] 1); 注意这里不是要dp[i] 与 dp[j] 1进行比较&#xff0c;而是我们要取dp[j] 1的最大值…...

go 笔记

数据结构与 方法&#xff08;增删改查&#xff09; 安装goland,注意版本是2024.1.1&#xff0c;不是2024.2.1&#xff0c;软件下载地址也在链接中提供了 ‘go’ 不是内部或外部命令&#xff0c;也不是可运行的程序 或批处理文件。 在 Windows 搜索栏中输入“环境变量”&#…...

路由等保测评

1.身份鉴别 应对登录的用户进行身份标识和鉴别&#xff0c; 身份标识具有唯一性&#xff0c;身份鉴别信息具有复杂度要求并定期更换。 可以使用“ service password-encryption"命令对存储在配置文件中的所有口令和类似数据进行加密&#xff0c; 以避免攻击者通过读取配…...

C# 反射之动态生成dll/exe

这个可能应该属于反射的高级使用范围了&#xff0c;平常在项目中使用的人估计也不是很多。由于使用反射的话会降低性能&#xff0c;比如之前用到的GetValue、SetValue等之类&#xff0c;但是使用这种方式会大大提高效率&#xff0c;在这里我只想说&#xff0c;都直接写IL指令了…...

Rust 所有权 Slices

文章目录 发现宝藏1. Slice 的基础知识1.1 什么是 Slice&#xff1f;1.2 如何创建 Slice&#xff1f; 2. 处理字符串 Slice2.1 字符串的 Slice2.2 字符串的 Unicode 和切片 3. 在函数中使用 Slice3.1 传递 Slice 给函数3.2 可变 Slice 的函数 4. 复杂示例4.1 处理多维数组的 Sl…...

windows 安全与网络管理问题

问题&#xff1a;当编写的脚本或程序运行的时候&#xff0c;可能被windows阻止访问网络甚至被删除 避免被删除 wini 进入设置界面 -> 选择更新与安全 -> 选择windwos defender -> 点击添加排除项&#xff0c;将指定的文件或目录排除&#xff0c;避免被软件删除 允许…...

基于Python实现一个庆祝国庆节的小程序

功能&#xff1a; 添加互动功能&#xff1a;允许用户选择不同的祝福语或者查询不同的国庆节信息。动态背景音乐&#xff1a;播放国庆节相关的背景音乐。增加节日小测验&#xff1a;提供一些关于国庆节的趣味小测验&#xff0c;让用户参与。增强图形用户界面 (GUI)&#xff1a;…...

Anaconda 安装与使用教程

Anaconda 安装与使用教程 介绍 Anaconda 是一个用于科学计算的 Python 和 R 的发行版&#xff0c;它包含了众多流行的科学计算、数据分析、机器学习等领域的库。本教程旨在帮助初学者快速上手 Anaconda&#xff0c;并学会如何使用其管理环境以及安装包。 第一步&#xff1a;…...

时序预测SARIMAX模型

1. 项目背景 本文基于kaggle平台相关竞赛项目&#xff0c;具体连接如下&#xff1a; Time Series Forecasting With SARIMAX 基本信息如内容说明、数据集、已提交代码、当前得分排名以及比赛规则等&#xff0c;如图【1】所示&#xff0c;可以认真阅读。 图 1 2. 数据读取 …...

gin集成jaeger中间件实现链路追踪

1. 背景 新业务线带来新项目启动&#xff0c;需要改进原有项目的基础框架和组件能力&#xff0c;以提升后续开发和维护效率。项目搭建主要包括技术选型、框架搭建、基础服务搭建等。这其中就涉及到链路追踪的内容&#xff0c;结合其中的踩坑情况&#xff0c;用一篇文章来说明完…...

前端层面----监控与埋点

前言&#xff1a; 站在产品的视角&#xff0c;经常会问如下几个问题&#xff1a; 产品有没有用户使用 用户用得怎么样 系统会不会经常出现异常 如何更好地满足用户需求服务用户 当站在技术视角时&#xff0c;经常会问如下几个问题&#xff1a; 系统出现异常的频率如何 异常…...

linux Command

linux Command 1. 系统监控命令 1.1 top top [param] top -H -p pid&#xff0c;查看进程pid下面的子线程。-b以处理模式操作-c显示完整的命令行而不只是显示命令名。-d 屏幕刷新间隔时间。-l 忽略失效过程。-s 保密模式。-S 累积模式。-u 【用户名】 指定用户名。-p 【进程…...

uniapp登录页面( 适配:pc、小程序、h5)

<!-- 简洁登录页面 --> <template><view class"login-bg"><image class"img-a" src"https://zhoukaiwen.com/img/loginImg/2.png"></image><image class"img-b" src"https://zhoukaiwen.com/im…...

关于OceanBase 多模一体化的浅析

在当今多元化的业务生态中&#xff0c;各行各业对数据库系统的需求各有侧重。举例来说&#xff0c;金融风控领域对数据库的高效事务处理&#xff08;TP&#xff09;和分析处理&#xff08;AP&#xff09;能力有着严格要求&#xff1b;游戏行业则更加注重文档数据库的灵活性和性…...

快速git

下载 sudo apt install git配置 $ git config --global user.name "John Doe" $ git config --global user.email johndoeexample.com没有空格可以不加双引号如果~/.ssh没有先创建&#xff08;下一步用&#xff09; ssh方式制作密钥 github解释 #以邮箱作为标签…...

欺诈文本分类检测(十四):GPTQ量化模型

1. 引言 量化的本质&#xff1a;通过将模型参数从高精度&#xff08;例如32位&#xff09;降低到低精度&#xff08;例如8位&#xff09;&#xff0c;来缩小模型体积。 本文将采用一种训练后量化方法GPTQ&#xff0c;对前文已经训练并合并过的模型文件进行量化&#xff0c;通…...

2024.9.14(RC和RS)

一、replicationcontroller &#xff08;RC&#xff09; 1、更改镜像站 [rootk8s-master ~]# vim /etc/docker/daemon.json {"registry-mirrors": ["https://do.nark.eu.org","https://dc.j8.work","https://docker.m.daocloud.io",&…...

【算法随想录04】KMP 字符串匹配算法

这是字符串模式匹配经典算法。 给定一个文本 t 和一个字符串 s&#xff0c;我们尝试找到并展示 s 在 t 中的所有出现&#xff08;occurrence&#xff09;。 #include<bits/stdc.h>using namespace std;vector<int> KMP(string s) {int n s.size();vector<int&g…...

TCP和MQTT通信协议

协议分层 网络分层 协议应用层 Co AP MQTT HTTP传输层 UDP TCP网络层 IP链路层 Enternet 网络分层中最…...

Python Pickle 与 JSON 序列化详解:存储、反序列化与对比

Python Pickle 与 JSON 序列化详解&#xff1a;存储、反序列化与对比 文章目录 Python Pickle 与 JSON 序列化详解&#xff1a;存储、反序列化与对比一 功能总览二 Pickle1 应用2 序列化3 反序列化4 系统资源对象1&#xff09;不能被序列化的系统资源对象2&#xff09;强行序列…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...