关键词:
文章目录
LeetCode刷题笔记-动态规划-day7
1014. 最佳观光组合
1.题目
原题链接:1014. 最佳观光组合
2.解题思路
- 仔细观察
a[i] + a[j] + i - j
,可分解为:(a[j]-j)+(a[i]+i)
- 又因为
i<j
,我们可以把j
当做当前点,所以这道题我们只需要遍历一遍。用一个变量f
维护j
点之前的所有a[i]+i
的最大值 res=max(res,f+a[j]-j);
扫描一遍即可求出最大值
3.代码
class Solution
public:
int maxScoreSightseeingPair(vector<int>& a)
int f=a[0];
int res=-1e9;
for(int i=1;i<a.size();i++)
res=max(res,f+a[i]-i);
f=max(a[i]+i,f);
return res;
;
121. 买卖股票的最佳时机
1.题目
原题链接:121. 买卖股票的最佳时机
2.解题思路
- 用一个变量
minn
维护[0,i-1
]的最小价格 - 枚举到
i
时,prices[i]-minn
就表示当前点i
卖出的最大收益 - 遍历所有点,取最大值:
res=max(res,prices[i]-minn);
3.代码
class Solution
public:
int maxProfit(vector<int>& prices)
int minn=1e9,res=0;
for(int i=0;i<prices.size();i++)
res=max(res,prices[i]-minn);
minn=min(minn,prices[i]);
return res;
;
122. 买卖股票的最佳时机 II
1.题目
原题链接:122. 买卖股票的最佳时机 II
2.解题思路
算法:贪心
具体情况可以分为三类:
- 单独交易日:设今天价格P1、明天价格P2,则今天买入、明天免除可赚取金额P2−P1(负值代表亏损)
- 连续上涨交易日:设此上涨交易日股票价格分别为P1,P2,…,Pn 则第一天买最后一天卖收益最大,即Pn−P1;等价于每天都买卖,即Pn−P1=(P2−P1)+(P3−P2)+…+(Pn−Pn−1)
- 连续下降交易日:则不买卖收益最大,即不会亏钱
总结可得到:由于不考虑交易次数。我们考虑相邻两天的股票价格,如果后一天的股票价格大于前一天的,那么在进行买入卖出操作后,即可获利。这样的贪心一定能获得最大的利润。
直接遍历整个数组。如果prices[i+1]-prices[i]
大于0,则加入最终总利润。
3.代码
class Solution
public:
int maxProfit(vector<int>& prices)
int res=0;
for(int i=0;i<prices.size()-1;i++)
res+=max(0,prices[i+1]-prices[i]);
return res;
;
leetcode刷题笔记-动态规划-day6(代码片段)
文章目录LeetCode刷题笔记-动态规划-day6152.乘积最大子数组1.题目2.解题思路3.代码1567.乘积为正数的最长子数组长度1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day6152.乘积最大子数组1.题目原题链接:152.乘积最大子数组2.解... 查看详情
leetcode刷题笔记-动态规划-day6(代码片段)
文章目录LeetCode刷题笔记-动态规划-day6152.乘积最大子数组1.题目2.解题思路3.代码1567.乘积为正数的最长子数组长度1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day6152.乘积最大子数组1.题目原题链接:152.乘积最大子数组2.解... 查看详情
leetcode刷题笔记-动态规划-day1(代码片段)
文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接:509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情
leetcode刷题笔记-动态规划-day1(代码片段)
文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接:509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情
leetcode刷题笔记-动态规划-day5(代码片段)
文章目录LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目2.解题思路3.代码918.环形子数组的最大和1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目原题链接:53.最大子数组和2.解题思路算法:... 查看详情
leetcode刷题笔记-动态规划-day3(代码片段)
文章目录LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目2.解题思路3.代码213.打家劫舍II1.题目2.解题思路3.代码740.删除并获得点数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目原题链接:198.打家劫舍2.... 查看详情
leetcode刷题笔记-动态规划-day3(代码片段)
文章目录LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目2.解题思路3.代码213.打家劫舍II1.题目2.解题思路3.代码740.删除并获得点数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day3198.打家劫舍1.题目原题链接:198.打家劫舍2.... 查看详情
leetcode刷题笔记-动态规划-day4(代码片段)
文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接:55.跳跃游戏2.解题思路算法:贪心我们用变量j表示从前... 查看详情
leetcode刷题笔记-动态规划-day4(代码片段)
文章目录LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目2.解题思路3.代码45.跳跃游戏II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day455.跳跃游戏1.题目原题链接:55.跳跃游戏2.解题思路算法:贪心我们用变量j表示从前... 查看详情
leetcode刷题笔记-动态规划-day2(代码片段)
文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接:70.爬楼梯2.解题思路算法:递推定义数组f[i]表示... 查看详情
leetcode刷题笔记-动态规划-day2(代码片段)
文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接:70.爬楼梯2.解题思路算法:递推定义数组f[i]表示... 查看详情
leetcode刷题笔记——动态规划(代码片段)
动态规划的⼀般流程就是三步:暴⼒的递归解法->带备忘录的递归解法->迭代的动态规划解法。就思考流程来说,就分为⼀下⼏步:找到状态和选择->明确dp数组/函数的定义->寻找状态之间的关系。明确dp[i][j]... 查看详情
leetcode刷题笔记-数据结构-day7(代码片段)
文章目录LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述2.解题思路3.代码763.划分字母区间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述原题链接:90.单词规律2.解题思路算法:哈希表... 查看详情
leetcode刷题笔记-动态规划-day1(代码片段)
文章目录LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目2.解题思路3.代码1137.第N个泰波那契数1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day1509.斐波那契数1.题目原题链接:509.斐波那契数2.解题思路可以用dp数组递推做... 查看详情
leetcode刷题分类笔记(代码片段)
leetcode刷题分类笔记202204130.常规操作1.链表83.删除排序链表中的重复元素203.移除链表元素2.二叉树leetcode108.将有序数组转换为二叉搜索树111.二叉树的最小深度113.路径总和II543.二叉树的直径3.动态规划45.跳跃游戏II96.不同的二叉搜... 查看详情
leetcode刷题笔记-动态规划-day5(代码片段)
文章目录LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目2.解题思路3.代码918.环形子数组的最大和1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day553.最大子数组和1.题目原题链接:53.最大子数组和2.解题思路算法:... 查看详情
leetcode刷题笔记-动态规划-day2(代码片段)
文章目录LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目2.解题思路3.代码746.使用最小花费爬楼梯1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day270.爬楼梯1.题目原题链接:70.爬楼梯2.解题思路算法:递推定义数组f[i]表示... 查看详情
leetcode之动态规划刷题总结8(代码片段)
leetcode之动态规划刷题总结8动态规划(英语:Dynamicprogramming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法... 查看详情