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

力扣 hot100 -- 动态规划(下)

目录

💻最长递增子序列

AC  动态规划

AC  动态规划(贪心) + 二分

🏠乘积最大子数组

AC  动规

AC  用 0 分割

🐬分割等和子集

AC  二维DP

AC  一维DP

⚾最长有效括号

AC  栈 + 哨兵


💻最长递增子序列

300. 最长递增子序列 - 力扣(LeetCode)

子序列:不用连续

子串:要求连续

AC  动态规划

时间 O(n^2)

/*
dp[i] : 第 i 个元素结尾的最长子序列长度(下标0开始)
dp[i] = max(dp[i], dp[j] + 1)
初始化 : dp[i] = 1
*/
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1, 1);for (int i = 1; i < n; ++i)for (int j = 0; j < i; ++j) if (nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);int ans = 1;for (auto x : dp)ans = max(ans, x);return ans;}
};

AC  动态规划(贪心) + 二分

二分实现 O(logn) 查找,为了使用二分,我们需要让 dp[] 数组有序,所以需要改变 dp[] 数组的含义(状态)

贪心策略:tails 中存储的元素越小,上升的子序列越长 

举例解释

nums[] = {7, 8, 9, 1, 2, 3, 4, 5};

遍历完 7 8 9 后 tails[] = {7, 8, 9};

接着遍历到 1,那么二分查找 tails[],找到第一个比 tails 大的位置,即 7,替换后变成

tails[] = {1, 8, 9};

如果没有比当前 nums[] 值大的元素,直接加到后面

最后输出 tails[] 长度,就是最长上升子序列长度

时间 O(nlogn)

/*
tails[i] : 长度 i+1 子序列的尾部元素
1)nums[] 中当前元素 x > tails.back(), x 插入 tails 最后
2)否则, 二分查找 tails[] 中第一个 > x 的元素, 替换成 x
最后返回 tails[] 大小
*/
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> tails;tails.push_back(nums[0]);for (auto x : nums) {if (x > tails.back()) {tails.push_back(x);continue;}int l = 0, r = tails.size() - 1;while (l < r) {int mid = (l + r) >> 1;if (tails[mid] < x)l = mid + 1;elser = mid;}tails[l] = x;}return tails.size();}
};
// 检验二分边界
// tails[]: 1 3 5 -- x: 3/4
// tails[]: 1 3 5 7 -- x: 3/4/5

🏠乘积最大子数组

152. 乘积最大子数组 - 力扣(LeetCode)

注意是“连续子数组” 

AC  动规

1)滚动

本题,dp[i] 都是基于 dp[i -1] 得到的,所以可以将一维数组变成一个变量,即 “滚动数组” 

2)坑

遍历数组,更新 3 个 dp 变量时,maxDp 基于上一个 maxDp 没问题

但是 maxDp 更新后,minDp 还是基于上一个 maxDp

所以需要一个临时变量保存上一个 maxDp

然后 dp 可以直接基于新的 maxDp

3)坑2

题目保证 32 位,也就是 10^9,但是,样例里有一组 10^19 次方的....

所以,有 4 个地方要加 double,防止类型不匹配 或 heap flow(堆溢出)

时间 O(n)

/*
滚动数组,一维数组变变量
maxDp[i] : 第 i 个元素结尾的最大值
minDp[i] : 第 i 个元素结尾的最小值
dp[i] : 只选前 i 的元素的最大值
*/
class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();if (n == 1)return nums[0];double maxDp = nums[0], minDp = nums[0], dp = nums[0];for (int i = 1; i < n; ++i) {double t = maxDp; // 临时变量maxDp = max(max((double)nums[i], maxDp*nums[i]), minDp*nums[i]);minDp = min(min((double)nums[i], t*nums[i]), minDp*nums[i]);dp = max(dp, maxDp); // 上一个 dp 和 新的 maxDp 取较大值}return (double)dp;}
};

AC  用 0 分割

用 0 分割成多个连续的子数组,对每个子数组:

1)偶数个负数,直接相乘(负数数量 0, 2, 4, 6...)

2)奇数个负数:

        a. 左到右相乘,直到最后一个负数之前

        b. 右到左,直到最后一个负数之前

取 a. b. 的 max()

3)实际遍历中,先左到右遍历,后右到左遍历,单次遍历中,只需要动态更新最大值(包含了偶数,奇数个负数的两种情况)

时间 O(n)

class Solution {
public:int maxProduct(vector<int>& nums) {double ans = nums[0];double t = 1; // 临时变量保存乘积// 左到右for (int i = 0; i < nums.size(); ++i) {t *= nums[i];ans = max(ans, t);if (t == 0)t = 1; // 用 0 分割子数组}// 右到左t = 1;for (int i = nums.size() - 1; i >= 0; --i) {t *= nums[i];ans = max(ans, t);if (t == 0)t = 1;}return (int)ans;}
};

🐬分割等和子集

416. 分割等和子集 - 力扣(LeetCode)

AC  二维DP

01背包画表格类似这样

和为奇数,直接返回 false,否则打表会发现,出现了一些奇怪的错误

含义

dp[i][j] : 只从 [0, i] 区间里选,每个数最多选 1 次,和为 j

递推式

选第 i 个:dp[i - 1][j - nums[i]]

不选第 i 个:dp[i - 1][j]

第 i 个数 == 总和的一半

dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] == sum/2)

初始化

根据递推式,只需初始化第 0 行,即只从 [0, 0] 区间选,和为 nums[0] 的 == 1,其他为 0

输出

dp[n - 1][sum / 2]:表示从 [0, n - 1] 选, 和为总和一半, 即等和子集

O(n * sum/2)

// dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] == sum/2)
// 输出 dp[n - 1][sum / 2]
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0, n = nums.size();for (auto x : nums)sum += x;if (sum % 2 == 1)return false; // 和为奇数// n 行, 每一行就是 vector<int>(), 这一行表示总和 0 ~ sum/2, 初始化为 0vector<vector<int>> dp(n, vector<int>(sum / 2 + 1, 0));if (nums[0] <= sum/2)dp[0][nums[0]] = 1; // 从 [0, 0] 选, 和为nums[0]for (int i = 1; i < n; ++i)for (int j = 0; j <= sum/2; ++j) {dp[i][j] = dp[i - 1][j] || (nums[i] == sum/2);if (j >= nums[i]) // 防止越界dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];}return dp[n - 1][sum / 2];}
};

AC  一维DP

考虑到递推式 dp[i][j] 都是来源于 dp[i - 1][...],可以将二维变成一维,优化空间👇

那么为什么要逆序遍历子集的和 j 呢,因为,dp[j] 都是基于上一行的,旧的(未被修改的) dp[j] 和 dp[j - nums[i]]

如果顺序遍历,dp[j - nums[i]] 会被多次修改,也就是取了多个元素,而题目规定只能取一个

顺序遍历适合完全背包,而不是 01 背包

 

// dp[j] :和为 j
// dp[j] = dp[j - nums[i]] || dp[j] || (nums[i] == sum/2)
// 输出 dp[sum / 2]
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0, n = nums.size();for (auto x : nums)sum += x;if (sum % 2 == 1)return false; // 和为奇数// 和的一半 +1 个元素vector<int> dp(sum / 2 + 1, 0);if (nums[0] <= sum/2)dp[nums[0]] = 1; // 从 [0, 0] 选, 和为nums[0]for (int i = 1; i < n; ++i)for (int j = sum/2; j >= 0; --j) {dp[j] = dp[j] || (nums[i] == sum/2);if (j >= nums[i]) // 防止越界dp[j] = dp[j] || dp[j - nums[i]];}return dp[sum / 2];}
};

⚾最长有效括号

32. 最长有效括号 - 力扣(LeetCode)

AC  栈 + 哨兵

求连续的最长有效括号

如果不连续,栈就会被清空最后一个元素,再插入新的下标,即更新了栈顶的元素

初始插入 -1(哨兵),防止先遇到右括号,栈为空就 pop 导致的栈溢出

时间 O(n)

class Solution {
public:int longestValidParentheses(string s) {int ans = 0;if (s.size() == 0) return 0;stack<int> st;st.push(-1); // 防止溢出, 为后面的连续准备for (int i = 0; i < s.size(); ++i) {if (s[i] == '(') // 左括号st.push(i); else { // 右括号st.pop();if (st.empty())st.push(i);else ans = max(ans, i - st.top()); // 连续的长度}}return ans;}
};

相关文章:

力扣 hot100 -- 动态规划(下)

目录 &#x1f4bb;最长递增子序列 AC 动态规划 AC 动态规划(贪心) 二分 &#x1f3e0;乘积最大子数组 AC 动规 AC 用 0 分割 &#x1f42c;分割等和子集 AC 二维DP AC 一维DP ⚾最长有效括号 AC 栈 哨兵 &#x1f4bb;最长递增子序列 300. 最长递增子序列…...

【计算机毕业设计】018基于weixin小程序实习记录

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…...

力扣之有序链表去重

删除链表中的重复元素&#xff0c;重复元素保留一个 p1 p2 1 -> 1 -> 2 -> 3 -> 3 -> null p1.val p2.val 那么删除 p2&#xff0c;注意 p1 此时保持不变 p1 p2 1 -> 2 -> 3 -> 3 -> null p1.val ! p2.val 那么 p1&#xff0c;p2 向后移动 p1 …...

Apache配置与应用(优化apache)

Apache配置解析&#xff08;配置优化&#xff09; Apache链接保持 KeepAlive&#xff1a;决定是否打开连接保持功能&#xff0c;后面接 OFF 表示关闭&#xff0c;接 ON 表示打开 KeepAliveTimeout&#xff1a;表示一次连接多次请求之间的最大间隔时间&#xff0c;即两次请求之间…...

怎么将3张照片合并成一张?这几种拼接方法很实用!

怎么将3张照片合并成一张&#xff1f;在我们丰富多彩的日常生活里&#xff0c;是否总爱捕捉那些稍纵即逝的美好瞬间&#xff0c;将它们定格为一张张珍贵的图片&#xff1f;然而&#xff0c;随着时间的推移&#xff0c;这些满载回忆的宝藏却可能逐渐演变成一项管理挑战&#xff…...

YOLOv10改进 | 图像去雾 | MB-TaylorFormer改善YOLOv10高分辨率和图像去雾检测(ICCV,全网独家首发)

一、本文介绍 本文给大家带来的改进机制是图像去雾MB-TaylorFormer&#xff0c;其发布于2023年的国际计算机视觉会议&#xff08;ICCV&#xff09;上&#xff0c;可以算是一遍比较权威的图像去雾网络&#xff0c; MB-TaylorFormer是一种为图像去雾设计的多分支高效Transformer…...

spring boot读取yml配置注意点记录

问题1&#xff1a;yml中配置的值加载到代码后值变了。 现场yml配置如下&#xff1a; type-maps:infos:data_register: 0ns_xzdy: 010000ns_zldy: 020000ns_yl: 030000ns_jzjz: 040000ns_ggglyggfwjz: 050000ns_syffyjz: 060000ns_gyjz: 070000ns_ccywljz: 080000ns_qtjz: 090…...

电子电气架构 --- 关于DoIP的一些闲思 下

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...

Java getSuperclass和getGenericSuperclass

1.官方API对这两个方法的介绍 getSuperclass : 返回表示此 Class 所表示的实体&#xff08;类、接口、基本类型或 void&#xff09;的超类的 Class。如果此 Class 表示 Object 类、一个接口、一个基本类型或 void&#xff0c;则返回 null。如果此对象表示一个数组类&#xff…...

ARM功耗管理标准接口之ACPI

安全之安全(security)博客目录导读 思考&#xff1a;功耗管理有哪些标准接口&#xff1f;ACPI&PSCI&SCMI&#xff1f; Advanced Configuration and Power Interface Power State Coordination Interface System Control and Management Interface ACPI可以被理解为一…...

2024年网络监控软件排名|10大网络监控软件是哪些

网络安全&#xff0c;小到关系到企业的生死存亡&#xff0c;大到关系到国家的生死存亡。 因此网络安全刻不容缓&#xff0c;在这里推荐网络监控软件。 2024年这10款软件火爆监控市场。 1.安企神软件&#xff1a; 7天免费试用https://work.weixin.qq.com/ca/cawcde06a33907e6…...

通过Arcgis从逐月平均气温数据中提取并计算年平均气温

通过Arcgis快速将逐月平均气温数据生成年平均气温数据。本次用2020年逐月平均气温数据操作说明。 一、准备工作 &#xff08;1&#xff09;准备Arcmap桌面软件&#xff1b; &#xff08;2&#xff09;准备2020年逐月平均气温数据&#xff08;NC格式&#xff09;、范围图层数据&…...

每日一题~abc356(对于一串连续数字 找规律,开数值桶算贡献)

添加链接描述 题意&#xff1a;对于给定的n,m 。计算0~n 每一个数和m & 之后&#xff0c;得到的数 的二进制中 1的个数的和。 一位一位的算。最多是60位。 我们只需要计算 在 1-n这些数上&#xff0c;有多少个数 第i位 为1. 因为是连续的自然数&#xff0c;每一位上1 的…...

商业合作方案撰写指南:让你的提案脱颖而出的秘诀

作为一名策划人&#xff0c;撰写一份商业合作方案需要细致的规划和清晰的表达。 它是一个综合性的过程&#xff0c;需要策划人具备市场洞察力、分析能力和创意思维。 以下是能够帮助你撰写一份有效的商业合作方案的关键步骤和要点&#xff1a; 明确合作目标&#xff1a;设定…...

【MySQL】锁(黑马课程)

【MySQL】锁 0. 锁的考察点1. 概述1. 锁的分类1.1 属性分类1.2 粒度分类 2. 全局锁2.1 全局锁操作2.2.1 备份问题 3. 表级锁3.1 表锁3.2 语法3.3 表共享读锁&#xff08;读锁&#xff09;3.4 表独占写锁&#xff08;写锁&#xff09;3.5 元数据锁(meta data lock, MDL)3.6 意向…...

1.10编程基础之简单排序--02:奇数单增序列

OpenJudge - 02:奇数单增序列http://noi.openjudge.cn/ch0110/02/ 描述 给定一个长度为N(不大于500)的正整数序列,请将其中的所有奇数取出,并按升序输出。 输入 共2行: 第1行为 N; 第2行为 N 个正整数,其间用空格间隔。 输出 增序输出的奇数序列,数据之间以逗号间隔。数…...

【leetcode78-81贪心算法、技巧96-100】

贪心算法【78-81】 121.买卖股票的最佳时机 class Solution:def maxProfit(self, prices: List[int]) -> int:dp[[0,0] for _ in range(len(prices))] #dp[i][0]第i天持有股票&#xff0c;dp[i][1]第i天不持有股票dp[0][0] -prices[0]for i in range(1, len(prices)):dp[…...

IEC62056标准体系简介-4.IEC62056-53 COSEM应用层

为在通信介质中传输COSEM对象模型&#xff0c;IEC62056参照OSI参考模型&#xff0c;制定了简化的三层通信模型&#xff0c;包括应用层、数据链路层&#xff08;或中间协议层&#xff09;和物理层&#xff0c;如图6所示。COSEM应用层完成对COSEM对象的属性和方法的访问&#xff…...

嵌入式应用开发之代码整洁之道

前言&#xff1a;本系列教程旨在如何将自己的代码写的整洁&#xff0c;同时也希望小伙伴们懂如何把代码写脏&#xff0c;以备不时之需&#xff0c;同时本系列参考 正点原子 &#xff0c; C代码整洁之道&#xff0c;编写可读的代码艺术。 #好的代码的特点 好的代码应该都有着几…...

iwconfig iwpriv学习之路

iwconfig和iwpriv是两个常用的wifi调试工具&#xff0c;最近需要使用这两个工具完成某款wifi芯片的定频测试&#xff0c;俗话说好记性不如烂笔头&#xff0c;于是再此记录下iwconfig和iwpriv的使用方式。 -----再牛逼的梦想&#xff0c;也抵不住傻逼般的坚持&#xff01; ----2…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...