当前位置: 首页 > 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…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

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": …...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

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…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...