【leetcode100-086到090】【动态规划】一维五题合集2

2024-02-06 06:04

本文主要是介绍【leetcode100-086到090】【动态规划】一维五题合集2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【单词拆分】

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

思路:

首先,我们依次考虑s的前i个字母能否被分割,直到i=n;

对一个确定的i,我们尝试在前i个字母中进行分割,枚举每一个分割点,如果分割点前面的部分能分割(肯定已经被计算过,直接查表即可),且分割点后的部分存在于 wordDict中,那么当前子串就是可分割的,记录到表中;

最后检查dp[n]即可。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();// dpvector<bool> dp(n + 1, false);dp[0] = true;//递推for (int i = 1; i <= n; i++) {for (int j = 0; j < i; j++) {//bool flag=false;// s[0]到s[j-1]能分割,s[j]到s[i-1]if (dp[j] &&(find(wordDict.begin(),wordDict.end(),s.substr(j, i - j)) != wordDict.end())) {dp[i] = true;break;}}}return dp[n];}
};

【最长递增子序列】

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

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

思路:

依次考虑前i个元素,计算以第i个元素结尾的递增子序列长度;

对第i个元素,我们检查它前面的所有元素,并试着把它接在该元素结尾的子序列后面,如果还能满足递增,则记录接上后的子序列长度;

随时记录当前找到的最大长度。

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

【乘积最大子数组】

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

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

子数组 是数组的连续子序列。

思路:

本题重点在于,会出现负数,想让一个包含负数的数组乘积最大,要么让这个负数乘绝对值最大的负数前缀乘积(实际值最小),要么什么也不干(如果前缀只有正数,乘正数要么不变要么变小,直接不考虑);

再考虑正数情况,想让一个包含该数的数组乘积最大,要么让它乘上最大的正的前缀乘积,要么什么也不干(前缀积只有负数时越乘越小);

如果遇到0,包含它的子数组乘积必为零,我们可以留到最后去判断;

以上逻辑看起来很复杂,要判断当前元素和0的关系,最大的前缀积最小的前缀积和零的关系,特殊值0的处理,等等,但实际上不管怎么样,我们需要的其实就是到当前元素为止的最大和最小乘积,而我们做的计算也只有当前元素x最大前缀积,当前元素x最小前缀积,当前元素不变三种情况,所以只要计算这三种结果,并取其中的最大值和最小值就可。

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

【分割等和自己】

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

思路:

把题目翻译一下,其实就是能不能找出一个子数组,它的和是原数组总和的一半,这样就变成0-1背包了;

首先算一下原数组总和,如果是奇数肯定不行,如果是偶数,那么它的一半就是我们要找的子数组的和,aka背包的容量,而我们要记录的是考虑前i个物品时能否恰好把容量为j的背包装满;

依次增加当前考虑的物品数量i,倒序遍历背包容量j,首先判断当前物品i,如果它的重量正好等于当前容量j,那么可以装满,如果前i-1个物品已经能把j容量装满,那么增加一个物品没有影响,肯定也可以装满,否则考虑前i-1个物品能否装满容量j-当前重量的背包,如果能的话,加上当前物品,就正好是前i个物品装满j容量的背包;

最后,考虑到每一轮循环我们需要的信息其实都只有第i-1行,进行空间优化,用一维数组来滚动即可。

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

【最长有效括号】

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

思路:

一开始疯狂条件判断,把自己都判晕了,后来才意识到本题的核心逻辑非常简单,归纳真有意思。

遍历串中的每个字符,我们记录以该字符结尾的最长有效子串长度;

当我们拿到一个新的字符i,有两种情况,左括号结尾的必无效,填0直接continue,右括号结尾时,我们要做的是:看看这个右括号能不能找到对应的左括号,把以字符i-1结尾的有效串包在里面,如果找到了,那么这个有效串的长度就增加了2,还没完,我们找到了最左边的括号以后,还要看看它的前一个字符能提供多长的有效串,拼接起来,此时才真正拿到了以字符i结尾的最长的有效串;

对当前字符是右括号且前一个字母是左括号的情况,我们还可以进行代码优化,直接用这两个字符组成的合法括号对拼接上前面的有效串即可(本质是用dp[i - 1]为0的信息简化了表达式)。

class Solution {
public:int longestValidParentheses(string s) {int n = s.size();if (n == 0)return 0;vector<int> dp(n + 1, 0);//dp[0] = dp[1] = 0;for (int i = 2; i <= n; i++) {//左结尾必不合法if (s[i - 1] == '(')continue;//右结尾时分情况讨论else {//正好是个左,凑一对if (s[i - 2] == '(')dp[i] = dp[i - 2] + 2;//是个右,要去当前元素左边的整个合法串的左边找找有没有配对的,配上的话还要再往前接龙else {//配上了if ((i - 2 - dp[i - 1] >= 0) &&(s[i - 2 - dp[i - 1]] == '('))dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];}}}return *max_element(dp.begin(), dp.end());}
};

这篇关于【leetcode100-086到090】【动态规划】一维五题合集2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/683354

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

EasyPlayer.js网页H5 Web js播放器能力合集

最近遇到一个需求,要求做一款播放器,发现能力上跟EasyPlayer.js基本一致,满足要求: 需求 功性能 分类 需求描述 功能 预览 分屏模式 单分屏(单屏/全屏) 多分屏(2*2) 多分屏(3*3) 多分屏(4*4) 播放控制 播放(单个或全部) 暂停(暂停时展示最后一帧画面) 停止(单个或全部) 声音控制(开关/音量调节) 主辅码流切换 辅助功能 屏

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

轨迹规划-B样条

B样条究竟是干啥的?白话就是给出一堆点,用样条的方式,给这些点连接起来,并保证丝滑的。 同时B样条分为准均匀和非均匀,以下为准均匀为例。 参考链接1:https://zhuanlan.zhihu.com/p/50626506https://zhuanlan.zhihu.com/p/50626506 参考链接2: https://zhuanlan.zhihu.com/p/536470972h

PMBOK® 第六版 规划进度管理

目录 读后感—PMBOK第六版 目录 规划进度管理主要关注为整个项目期间的进度管理提供指南和方向。以下是两个案例,展示了进度管理中的复杂性和潜在的冲突: 案例一:近期,一个长期合作的客户因政策要求,急需我们为多家医院升级一个小功能。在这个过程中出现了三个主要问题: 在双方确认接口协议后,客户私自修改接口并未通知我们,直到催进度时才发现这个问题关于UI设计的部分,后台开发人员未将其传递给