LeetCode 热题100(十五)【动态规划】(3)

15.7最长递增子序列(中等)

题目描述:leetcode链接 300. 最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的

子序列

。 

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

思路:

1.dp[i]表示以nums[i]结尾的最长递增子序列的长度,其长度最小为1,因此对dp全部初始化为1

2.当nums[i] > nums[j]时,dp[i] = dp[j] + 1

当nums[i] <= nums[j]时,dp[i]则不变

因此,对于j∈[0 , i )遍历,dp[i] = max (dp[i] , dp[j] + 1)

3.返回dp中最大的值

举例说明:

代码:

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();int ans = 1;vector<int> dp(n, 1);for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if(dp[i] > ans) ans = dp[i];}return ans;}
};

15.8乘积最大子数组(中等)

题目描述:leetcode链接 152. 乘积最大子数组

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路:

1.由于nums中存在负数,因此用两个vector存储以nums[i]结尾的乘积的最大值和最小值

2.初始化f_max[0] = f_min[0] = nums[0]

3.状态转移方程

f_max[i] = max(max(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i])
f_min[i] = min(min(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i])

4.返回f_max的最大值即可

举例说明:

代码:

class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> f_min(n), f_max(n);f_max[0] = f_min[0] = nums[0];int ans = f_max[0];for (int i = 1; i < n; i++) {f_max[i] = max(max(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i]);f_min[i] = min(min(f_max[i - 1] * nums[i], f_min[i - 1] * nums[i]), nums[i]);ans = max(f_max[i], ans);}return ans;}
};

15.9 分割等和子集(中等)

题目描述:leetcode链接 416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

思路:

1.nums中的所有元素相加为sum,若sum为奇数,则直接返回false

2.令target=sum/2,dp[j]表示nums的子集中的元素之和是否可以等于j

vector<bool> dp(target + 1, false)
初始化dp[0] = true

3.对于nums[i]

dp[j] = dp[j] || dp[j - nums[i]],其中j∈[ nums[i], target ]

4.返回dp[target]

举例说明:

代码:

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i];}if(sum % 2 == 1) return false;int target = sum / 2;vector<bool> dp(target + 1, false);dp[0] = true;for(int i = 0; i < nums.size(); i++){for(int j = target; j >= nums[i]; j--){dp[j] = dp[j] || dp[j - nums[i]];}}return dp[target];}
};

15.10最长有效括号(困难)

题目描述:leetcode链接 32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"

示例 2:

输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

示例 3:

输入:s = ""
输出:0

思路:

1.dp[i]表示以s[i]结尾的最长有效括号数量

2.当s[i]==')',s[i - 1]=='('时,dp[i]=dp[i - 2] + 2;
当s[i]==')',s[i - 1]==')'时,如果s[i - 1 - dp[i - 1]]=='(',dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]

3.返回dp中的最大值

举例说明:

代码:

class Solution {
public:int longestValidParentheses(string s) {//1.当s[i]==')',s[i - 1]=='('时//dp[i]=dp[i - 2] + 2;//2.当s[i]==')',s[i - 1]==')'时//如果s[i - 1 - dp[i - 1]]=='('//dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]int ans = 0;int n = s.size();vector<int> dp(n, 0);for (int i = 1; i < n; i++) {if (s[i] == ')') {if (s[i - 1] == '(') dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;else if (i - dp[i - 1] > 0 && s[i - 1 - dp[i - 1]]=='(') {dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] >= 2) ? dp[i - 2 - dp[i - 1]] : 0);}}ans = max(ans, dp[i]);}return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/34977.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

springboot如何集成工作流审批流,流程设计器集成,业务表单和工作流绑定,详细步骤和实际案例参考(源码)

前言 activiti工作流引擎项目&#xff0c;企业erp、oa、hr、crm等企事业办公系统轻松落地&#xff0c;一套完整并且实际运用在多套项目中的案例&#xff0c;满足日常业务流程审批需求。 一、项目形式 springbootvueactiviti集成了activiti在线编辑器&#xff0c;流行的前后端…

02_Node.js模块化

02_Node.js模块化 知识点自测 以下代码运行的结果是多少&#xff1f; const arr [10, 20, 30] const result arr.map(val > val 1).reduce((sum, val) > sum val, 0) console.log(result) A&#xff1a;60 B&#xff1a;63 <details><summary>答案</…

vulnhub kioptirx1.2 超详细wp

探测 nmap --min-rate 10000 -p- 192.168.128.134 最小速率10000 nmap -sT -sV -sC -O 192.168.128.134 web打点 无弱口令 暴露cms寻找exp searchsploit LotusCMS -m 16982 [输入id号和参数m可以直接把东西复制到当前目录] 查看txt里面发现 都是xss没有rce github搜索到一个…

vulnhub靶场之【grotesque】三

前言 靶机&#xff1a;grotesque-3 192.168.1.44 攻击 &#xff1a;kali 192.168.1.16 都是虚拟机环境&#xff0c;桥接模式 主机发现 使用arp-scan -l或者netdiscover -r 192.168.1.1/24搜索 信息收集 使用nmap扫描 防止有遗漏&#xff0c;再扫描全端口 网站信息收集 …

大规模模型部署、推理的工具:Xinference

有没有 Xinference之前&#xff0c;如果想要部署应用一个开源模型&#xff0c;可能会面临以下一些情况和挑战&#xff1a; 自行开发推理框架&#xff1a; 需要投入大量的时间和精力来构建一个可靠且高效的推理框架&#xff0c;包括处理模型加载、资源管理、请求调度等复杂的任务…

C语言选择法排序

C语言编程&#xff0c;用选择法对数组中4个整数按由大到小排序 1、代码如下&#xff1a; #include<stdio.h> #include<math.h> #include<string.h>int main() {void sort(int array[],int n);printf("测试开始\n");int nums[] {2,3,4,1};sort(n…

SpringBoot的validation参数校验

文章目录 前言一、引入validation 依赖二、validation中的注解说明 &#xff08;1&#xff09;Validated&#xff08;2&#xff09;Valid&#xff08;3&#xff09;NotNull&#xff08;4&#xff09;NotBlank&#xff08;5&#xff09;NotEmpty&#xff08;6&#xff09;Patte…

Go的Gin比java的Springboot更加的开箱即用?

前言 隔壁组的云计算零零后女同事&#xff0c;后文简称 云女士 &#xff0c;非说 Go 的 Gin 框架比 Springboot 更加的开箱即用&#xff0c;我心想在 Java 里面 Springboot 已经打遍天下无敌手&#xff0c;这份底蕴岂是 Gin 能比。 但是云女士突出一个执拗&#xff0c;非我要…

docker学习笔记(四)--DockerFile

文章目录 一、什么是Dockerfile二、docker build命令三、dockerfile指令3.1 FROM3.2 ENV3.3 WORKDIR3.4 RUN3.5 CMD3.6 ENTRYPOINT3.7 EXPOSE3.8 ARG3.9 ADD3.10 COPY3.11 VOLUME 四、dockerfile示例 一、什么是Dockerfile Dockerfile 是用于构建 Docker 镜像的脚本文件&#…

撰写技术文档的关键步骤和核心要点

编写项目的技术文档是一个重要且细致的任务&#xff0c;它不仅有助于项目的当前开发团队理解系统的结构和工作原理&#xff0c;还为未来的维护和扩展提供了宝贵的参考资料。以下是撰写技术文档时应遵循的几个关键步骤和组成部分&#xff1a; 1. 概述 项目简介&#xff1a;简要…

Ant-Design-Vue 全屏下拉日期框无法显示,能显示后小屏又位置错乱

问题1&#xff1a;在全屏后 日期选择器的下拉框无法显示。 解决&#xff1a;在Ant-Design-Vue的文档中&#xff0c;很多含下拉框的组件都有一个属性 getPopupContainer可以用来指定弹出层的挂载节点。 在该组件上加上 getPopupContainer 属性,给挂载到最外层盒子上。 <temp…

【前端学习路线】(超详细版本)

先附上学习路线图&#xff1a;前端学习路线 第一阶段&#xff1a;前端入门&#xff08;htmlcss&#xff09; 前端最基本的知识&#xff0c;需要先将这些内容融汇贯通&#xff0c;学习后面内容才会不吃力。学习完可以做几个静态页练习一下。 推荐视频学习链接&#xff1a; 黑马程…

Vue生成类似于打卡页面

数据表格 <el-table :data"tableData" border height"calc(100vh - 240px)" :cell-style"cellFun"><el-table-column label"姓名" show-overflow-tooltip prop"name" align"center"/><el-table-co…

JVM学习《垃圾回收算法和垃圾回收器》

目录 1.垃圾回收算法 1.1 标记-清除算法 1.2 复制算法 1.3 标记-整理算法 1.4 分代收集算法 2.垃圾回收器 2.1 熟悉一下垃圾回收的一些名词 2.2 垃圾回收器有哪些&#xff1f; 2.3 Serial收集器 2.4 Parallel Scavenge收集器 2.5 ParNew收集器 2.6 CMS收集器 1.垃圾…

波特图方法

在电路设计中&#xff0c;波特图为最常用的稳定性余量判断方法&#xff0c;波特图的根源是如何来的&#xff0c;却鲜有人知。 本章节串联了奈奎斯特和波特图的渊源&#xff0c;给出了其对应关系和波特图相应的稳定性余量。 理论贯通&#xff0c;不在于精确绘…

【Java】2、集合框架 JCF

目录 CollectionListArrayList扩容机制System.arraycopy() 和 Arrays.copyOf()方法 LinkedList Set MapHashMap *重点&#xff1a; 底层机制&#xff08;源码&#xff09;应用场景 好处&#xff1a; 数组&#xff08;长度不可改&#xff0c;同一类型&#xff0c;增删不便&#…

P5461 赦免战俘

P5461 赦免战俘 #include <iostream> using namespace std; #include <algorithm> #include <vector> #include <cmath> void pardon(auto & matrix,int x,int y,int size){if(size 1) return;int half size / 2;for(int i x;i < x half;i …

GoTrackIt应用指南:共享单车时空轨迹可视化

GoTrackIt平台集成了对 Kepler.gl 可视化工具的部分功能进行了封装&#xff0c;通过引入 KeplerVis 类&#xff0c;显著简化了地理空间数据分析与展示的过程。利用这一类&#xff0c;开发者和数据分析师能够在网页端快速实现复杂地理数据的动态可视化&#xff0c;而无需深入掌握…

LeetCode 力扣 热题 100道(十五)搜索插入位置(C++)

给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 代码如下所示&#xff1a; class Solution { public:int searchIns…

JS中递归函数的理解及展开运算符在递归种的运用理解

<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>递归函数</title> </head> <body> <script>const list ["你好", "吃饭了吗",["好",[[&qu…