算法刷题: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定义: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的最大值…...
go 笔记
数据结构与 方法(增删改查) 安装goland,注意版本是2024.1.1,不是2024.2.1,软件下载地址也在链接中提供了 ‘go’ 不是内部或外部命令,也不是可运行的程序 或批处理文件。 在 Windows 搜索栏中输入“环境变量”&#…...
路由等保测评
1.身份鉴别 应对登录的用户进行身份标识和鉴别, 身份标识具有唯一性,身份鉴别信息具有复杂度要求并定期更换。 可以使用“ service password-encryption"命令对存储在配置文件中的所有口令和类似数据进行加密, 以避免攻击者通过读取配…...
C# 反射之动态生成dll/exe
这个可能应该属于反射的高级使用范围了,平常在项目中使用的人估计也不是很多。由于使用反射的话会降低性能,比如之前用到的GetValue、SetValue等之类,但是使用这种方式会大大提高效率,在这里我只想说,都直接写IL指令了…...
Rust 所有权 Slices
文章目录 发现宝藏1. Slice 的基础知识1.1 什么是 Slice?1.2 如何创建 Slice? 2. 处理字符串 Slice2.1 字符串的 Slice2.2 字符串的 Unicode 和切片 3. 在函数中使用 Slice3.1 传递 Slice 给函数3.2 可变 Slice 的函数 4. 复杂示例4.1 处理多维数组的 Sl…...
windows 安全与网络管理问题
问题:当编写的脚本或程序运行的时候,可能被windows阻止访问网络甚至被删除 避免被删除 wini 进入设置界面 -> 选择更新与安全 -> 选择windwos defender -> 点击添加排除项,将指定的文件或目录排除,避免被软件删除 允许…...
基于Python实现一个庆祝国庆节的小程序
功能: 添加互动功能:允许用户选择不同的祝福语或者查询不同的国庆节信息。动态背景音乐:播放国庆节相关的背景音乐。增加节日小测验:提供一些关于国庆节的趣味小测验,让用户参与。增强图形用户界面 (GUI):…...
Anaconda 安装与使用教程
Anaconda 安装与使用教程 介绍 Anaconda 是一个用于科学计算的 Python 和 R 的发行版,它包含了众多流行的科学计算、数据分析、机器学习等领域的库。本教程旨在帮助初学者快速上手 Anaconda,并学会如何使用其管理环境以及安装包。 第一步:…...
时序预测SARIMAX模型
1. 项目背景 本文基于kaggle平台相关竞赛项目,具体连接如下: Time Series Forecasting With SARIMAX 基本信息如内容说明、数据集、已提交代码、当前得分排名以及比赛规则等,如图【1】所示,可以认真阅读。 图 1 2. 数据读取 …...
gin集成jaeger中间件实现链路追踪
1. 背景 新业务线带来新项目启动,需要改进原有项目的基础框架和组件能力,以提升后续开发和维护效率。项目搭建主要包括技术选型、框架搭建、基础服务搭建等。这其中就涉及到链路追踪的内容,结合其中的踩坑情况,用一篇文章来说明完…...
前端层面----监控与埋点
前言: 站在产品的视角,经常会问如下几个问题: 产品有没有用户使用 用户用得怎么样 系统会不会经常出现异常 如何更好地满足用户需求服务用户 当站在技术视角时,经常会问如下几个问题: 系统出现异常的频率如何 异常…...
linux Command
linux Command 1. 系统监控命令 1.1 top top [param] top -H -p pid,查看进程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 多模一体化的浅析
在当今多元化的业务生态中,各行各业对数据库系统的需求各有侧重。举例来说,金融风控领域对数据库的高效事务处理(TP)和分析处理(AP)能力有着严格要求;游戏行业则更加注重文档数据库的灵活性和性…...
快速git
下载 sudo apt install git配置 $ git config --global user.name "John Doe" $ git config --global user.email johndoeexample.com没有空格可以不加双引号如果~/.ssh没有先创建(下一步用) ssh方式制作密钥 github解释 #以邮箱作为标签…...
欺诈文本分类检测(十四):GPTQ量化模型
1. 引言 量化的本质:通过将模型参数从高精度(例如32位)降低到低精度(例如8位),来缩小模型体积。 本文将采用一种训练后量化方法GPTQ,对前文已经训练并合并过的模型文件进行量化,通…...
2024.9.14(RC和RS)
一、replicationcontroller (RC) 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,我们尝试找到并展示 s 在 t 中的所有出现(occurrence)。 #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 序列化详解:存储、反序列化与对比 文章目录 Python Pickle 与 JSON 序列化详解:存储、反序列化与对比一 功能总览二 Pickle1 应用2 序列化3 反序列化4 系统资源对象1)不能被序列化的系统资源对象2)强行序列…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
