代码随想录 动态规划 13
300. 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
思路:由题意得知,子序列是可以删除数组中的元素的,即一段长为s的序列的最长子序列,可能与若干个元素都无关,因此 长度为s的序列的最长子序列的状态依赖于在这之前的所有长度为1,2,3,。。。s-1的状态。转移方程,由于要求的是最长严格递增子序列,那么不难想到,如果当前的元素比遍历到的元素的元素大,那么就可以将其放到该元素的后面,形成一个严格递增子序列。既然如此,dp数组的定义就定义为,dp[i] 为 以 nums[i]结尾的最长子序列,转移方程为 if nums[i] > nums[j], dp[i] = max(dp[i], dp[j] + 1),初始化为1. 使用result来记录dp数组中的最大值。
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:dp = [1 for _ in range(len(nums))]result = 1for i in range(1, len(dp)):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)result = max(dp[i], result)return result
674. 最长连续递增序列
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
思路:与上一题类似,dp[i]的定义为 以nums[i]为结尾的连续递增子序列长度,转移方程为,当nums[i] > nums[i-1], dp[i] = dp[j] + 1, 以result记录dp数组最大值
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:dp = [1 for _ in range(len(nums))]result = 1for i in range(1, len(dp)):if nums[i] > nums[i-1]:dp[i] = dp[i-1] + 1result = max(dp[i], result)return result
718. 最长重复子数组
给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。
思路:设置dp[i][j] 为 nums1 前i -1个元素 和 nums2 前 j -1个元素 的公共最长重复子数组,那么转移方程为 if nums1[i-1] == nums2[j-1] , dp[i][j] = dp[i-1][j-1], 由于dp数组的设置,遍历时由1开始,len(nums1)+1 结束 (左闭右开)
二维dp
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]result = 0for i in range(1, len(nums1) + 1):for j in range(1, len(nums2) + 1):if nums1[i-1] == nums2[j-1]:dp[i][j] = dp[i-1][j-1] + 1result = max(result, dp[i][j])return result
一维dp
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:dp = [0] * (len(nums2) + 1)result = 0# 遍历数组 nums1for i in range(1, len(nums1) + 1):# 倒序遍历数组 nums2for j in range(len(nums2), 0, -1):if nums1[i-1] == nums2[j-1]:dp[j] = dp[j-1] + 1result = max(dp[j], result)else:dp[j] = 0return result
相关文章:
代码随想录 动态规划 13
300. 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子…...
lv6 嵌入式开发-Flappy bird项目
目录 1 项目功能总结 2 知识储备: 3 项目框图 4 Ncurses库介绍 做Flappy bird项目有什么用? 1. 复习、巩固c语言知识 2. 培养做项目的逻辑思维能力 3. 具备开发简单小游戏的能力 学会了Flappy bird项目,贪吃蛇和推房子两款小游戏也可…...
【Java】方法重写
概述 子类中出现了和父类一模一样的方法 当子类需要父类的功能,而功能主体中,子类有自己独特的内容,就可以通过重写父类中的方法,这样即延续了父类的功能,又定义了自己的特有内容 Override 是一个注解,可以…...
艺术表现形式
abstract expressionism 抽象表现主义 20世纪中期的一种艺术运动,包括多种风格和技巧,特别强调艺术家通过非传统和通常非具象的手段表达态度和情感的自由。 抽象表现主义用有力的笔触和滴落的颜料来表达情感和自发性。 简单地结合“abstract expression…...
PHP 反序列化漏洞:手写序列化文本
文章目录 参考环境序列化文本Scalar Type整数浮点数布尔值字符串 Compound Type数组数据结构序列化文本 对象数据结构序列化文本 Special TypeNULL数据结构序列化文本 手写序列化文本过程中的注意事项个数描述须于现实相符序列化文本前缀的大小写变化符号公共属性 参考 项目描…...
react.js在visual code 下的hello World
想学习reacr.js ,就开始做一个hello world。 我的环境是visual code ,所以我找这个环境下的例子。参照: https://code.visualstudio.com/docs/nodejs/reactjs-tutorial 要学习react.js ,还得先安装node.js,我在visual …...
CocosCreator3.8研究笔记(二十四)CocosCreator 动画系统-动画编辑器实操-关键帧实现动态水印动画效果
上一篇,我们介绍了动画编辑器相关功能面板说明,感兴趣的朋友可以前往阅读: CocosCreator3.8研究笔记(二十三)CocosCreator 动画系统-动画编辑器相关功能面板说明。 熟悉了动画编辑器的基础操作,那么再使用动…...
第1篇 目标检测概述 —(3)YOLO系列算法
前言:Hello大家好,我是小哥谈。YOLO(You Only Look Once)系列算法是一种目标检测算法,主要用于实时物体检测。相较于传统的目标检测算法,YOLO具有更快的检测速度和更高的准确率。YOLO系列算法的核心思想是将…...
SpringBoot整合数据库连接
JDBC 1、SQL准备 DROP TABLE IF EXISTS t_book;CREATE TABLE t_book (book_id int(11) NOT NULL,book_name varchar(255) DEFAULT NULL,price int(11) DEFAULT NULL,stock int(11) DEFAULT NULL ) ENGINEInnoDB DEFAULT CHARSETutf8mb4;/*Data for the table t_book */insert…...
uni-app:canvas-绘制图形4(获取画布宽高,根据画布宽高进行图形绘制)
效果 代码 var width ; var height ; const query uni.createSelectorQuery(); //获取宽度 query.select(#firstCanvas).fields({ size: true }, (res) > { width res.width; height res.height; }).exec(); console.log(宽度width); console.log(高…...
EM@坐标@函数@图象的对称和翻折变换
文章目录 abstract翻折变换关于坐标轴翻折 f ( − x ) , f ( x ) f(-x),f(x) f(−x),f(x) − f ( x ) , f ( x ) -f(x),f(x) −f(x),f(x) 偶函数奇函数小结 其他翻折变换关于 y x y\pm x yx对称的直角坐标 关于 x u 对称 关于xu对称 关于xu对称的函数关于 y v yv yv对称的两…...
Python之json模块
JSON (JavaScript Object Notation),由 RFC 7159 (它取代了 RFC 4627) 和 ECMA-404 指定,是一个受 JavaScript 的对象字面值句法启发的轻量级数据交换格式。JSON独立于编程语言的文本格式来存储和表示数据,现在大部分的数据传输基本使用的都是…...
机器学习---BP算法
1. 多级网络 层号确定层的高低:层号较小者,层次较低,层号较大者,层次较高。 输入层:被记作第0层。该层负责接收来自网络外部的信息。 第j层:第j-1层的直接后继层(j>0)ÿ…...
继苹果、联发科后,传高通下一代5G芯片将由台积电以3纳米代工
台积电3纳米又有重量级客户加入。市场传出,继苹果、联发科之后,手机芯片大厂高通下一代5G旗舰芯片也将交由台积电以3纳米生产,最快将于10月下旬发表,成为台积电3纳米第三家客户。 针对相关传闻,至昨日(25日…...
【自定义类型】--- 位段、枚举、联合
💓博客主页:江池俊的博客⏩收录专栏:C语言进阶之路👉专栏推荐:✅C语言初阶之路 ✅数据结构探索💻代码仓库:江池俊的代码仓库🎉欢迎大家点赞👍评论📝收藏⭐ 文…...
区块链(9):java区块链项目的Web服务实现之实现web服务
1 引入pom依赖 <dependency><groupId>org.eclipse.jetty</groupId><artifactId>jetty-server</artifactId><version>9.4.8.v20171121</version></dependency><dependency><groupId>org.eclipse.jetty</groupId…...
【CV】各种库安装报错及解决办法
目录 1.Error:Cannot unpack file… 1.Error:Cannot unpack file… 使用命令pip install -i https://pypi.tuna.tsinghua.edu.cn/simple --trusted-host pypi.tuna.tsinghua.edu.cn 包名安装 参考:解决Python使用pip安装库文件出现“Error&a…...
【算法系列篇】哈希表
文章目录 前言1. 两数之和1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 判断是否为字符重排2.1 题目要求2.2 做题思路2.3 Java代码实现 3. 存在重复元素3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 存在重复元素II4.2 题目要求4.2 做题思路4.3 Java代码实现 5. 字母异位词分…...
计算机视觉——飞桨深度学习实战-起始篇
后面我会直接跳到实战项目,将计算机视觉的主要任务和目标都实现一遍,但是需要大家下去自己多理解和学习一下。例如,什么是深度学习,什么是计算机视觉,什么是自然语言处理,计算机视觉的主要任务有哪些&#…...
vscode中运行脚手架项目报表
必选在cmd页面里面安装脚手架离谱啊,不然无法执行npm命令啊 vscode运行vue项目_小何不秃头06的博客-CSDN博客 finereport激活成功 - 帆软 (fanruan.com)...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
