代码随想录 动态规划 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)...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
