怎么开通公司网站,服务专业的网页制作公司,眉山建设银行官方网站,设计之窗LeetCode122.买卖股票的最佳时机II
那么这里面根据贪心思想#xff1a; 1、在最低点时买入#xff0c;如果该点比上一点价格更低#xff0c;只有两种情况#xff1a;上一点为买入点#xff0c;则此时更新买入点#xff1b;上一点不是买入点#xff0c;则此时将股票卖出…LeetCode122.买卖股票的最佳时机II
那么这里面根据贪心思想 1、在最低点时买入如果该点比上一点价格更低只有两种情况上一点为买入点则此时更新买入点上一点不是买入点则此时将股票卖出并更新买入点 2、在最高点卖出如果该点比上一点价格更高则继续向后观望直到最高的点。 3、首尾处的结果避免价格一直是单调序列因此在结尾处再添加一个卖出的操作。
代码如下
class Solution {
public:int maxProfit(vectorint prices) {int sum 0;int i 0;int buy 0;while(iprices.size()){if(i0 (prices[i]prices[i-1] || prices[i]prices[buy])){sum prices[i-1]-prices[buy];buy i;}i;}sum prices[prices.size()-1]-prices[buy];return sum;}
};
但是卡哥代码的思想比上述巧妙多了计算出每两天之间的利润只取正数利润相加即可求得最终结果代码如下
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;}
};
LeetCode55. 跳跃游戏
本题关键的思路在于覆盖只要取到任何一个点他下一步能覆盖到终点时就可以。
有一个错误点在于for循环时终止条件不应该是nums.size(),而是cover这样就可以解决[1,0,...]的情况并且cover是需要一直更新的。
代码如下
class Solution {
public:bool canJump(vectorint nums) {if(nums.size()1) return true;int cover 0;for(int i0;icover;i){cover max(inums[i],cover);if(covernums.size()-1) return true;}return false;}
};
LeetCode45.跳跃游戏II
思路确实不太好想贪心的策略就是尽量每一步走到最远处那么如何判断下一步的最远处呢那么这里就需要一直遍历到当前步的最远处来不断更新下一步的最远处并且步数1就跳到下一步的循环当中当下一步的最远处涵盖了终点时则就可以返回。
代码如下
class Solution {
public:int jump(vectorint nums) {if(nums.size()1) return 0;int curCover 0;int nextCover 0;int result 0;for(int i0;inums.size();i){nextCover max(inums[i],nextCover);if(icurCover){result;if(nextCovernums.size()-1) return result;curCover nextCover;}}return result;}
};
