网站设计速成,提供手机网站怎么做,企业网站制作,免费网站备案目录
122.买卖股票的最佳时机 II
前言
思路
算法实现
55. 跳跃游戏
思路
算法实现
45.跳跃游戏 II
前言
思路
算法实现
总结 122.买卖股票的最佳时机 II 题目链接 文章链接 前言 本题要求只能持有一支股票#xff0c;根据每日股票的价格控制股票的买入和卖出获取最…目录
122.买卖股票的最佳时机 II
前言
思路
算法实现
55. 跳跃游戏
思路
算法实现
45.跳跃游戏 II
前言
思路
算法实现
总结 122.买卖股票的最佳时机 II 题目链接 文章链接 前言 本题要求只能持有一支股票根据每日股票的价格控制股票的买入和卖出获取最大利润。
思路 可以将最终利润分解分解为每天为单位的维度假如第 0 天买入第 3 天卖出那么利润为prices[3] - prices[0]相当于(prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - prices[0])那么根据 prices 可以得到每天的利润序列(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。 只要我们收集每天的正利润区间就是股票买卖的区间我们只需要关注最终利润而不需记录区间。 局部最优收集每天的正利润全局最优求得最大利润。局部最优可以推出全局最优找不出反例试一试贪心
算法实现
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 1; i prices.size(); i){result max(prices[i] - prices[i - 1], 0);}return result;}
};
55. 跳跃游戏 题目链接 文章链接 思路 对于每个位置跳几步不要过于细化和具体其实跳几步无所谓关键在于可跳的覆盖范围有点类似于窗口的思想那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点 每次移动取最大跳跃步数得到最大的覆盖范围每移动一个单位就更新最大覆盖范围。贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。
算法实现
class Solution {
public:bool canJump(vectorint nums) {int cover 0;if (nums.size() 1) return true;for (int i 0; i cover; i){cover max(cover,i nums[i]);if (cover nums.size() - 1) return true;}return false;}
}; i 每次移动只能在 cover 的范围内移动每移动一个元素cover 得到该元素数值新的覆盖范围的补充让 i 继续移动下去。而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。如果 cover 大于等于了终点下标直接 return true 就可以了。
45.跳跃游戏 II 题目链接 文章链接 前言 本题可以继承上一题求最大覆盖范围的思路但是在具体处理上还要复杂一些。
思路 本题要求的是到达最后一个位置的最少跳跃次数从覆盖范围出发覆盖范围内一定是可以跳到的以最小的步数增加覆盖范围覆盖范围一旦覆盖了终点得到的就是最少步数 这里需要统计两个覆盖范围当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了还没有到终点的话那么就必须再走一步来增加覆盖范围直到覆盖范围覆盖了终点。
算法实现
class Solution {
public:int jump(vectorint nums) {if (nums.size() 1) return 0;int curDistance 0;int nextDistance 0;int ans 0;for (int i 0; i nums.size(); i){nextDistance max(nextDistance, nums[i] i);if (i curDistance){ans;curDistance nextDistance;if (nextDistance nums.size() - 1) return ans;}}return false;}
};
总结 贪心算法的题目确实思路比较难想有点费脑子。
