做网站的公司名称,wordpress html5主题,天津ui设计公司,黑龙江龙采做网站如何题目#xff1a;122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II
参考链接#xff1a;代码随想录
122.买卖股票的最佳时机II
思路#xff1a;本题我一开始想到的是参考前面的摆动序列#xff0c;先用坡度图思考#xff0c;我们要返回最大利润#xff0c;即要做…题目122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II
参考链接代码随想录
122.买卖股票的最佳时机II
思路本题我一开始想到的是参考前面的摆动序列先用坡度图思考我们要返回最大利润即要做到不放过任何一个上坡。把每个上坡的距离加起来就是答案这明显也满足局部最优推出全局最优。时间复杂度O(n)。
class Solution {
public:int maxProfit(vectorint prices) {if(prices.size()1){return 0;}int ans0;for(int i1;iprices.size();i){//前面已经排除了0的情况所以直接从1开始if(prices[i]prices[i-1]){//只要不跌一切都好说ans(prices[i]-prices[i-1]);}}return ans;}
};本题想起来也不难主要是想到坡度就容易了。标答解释就是收集每天的正利润。也不需要长度为1单独考虑。 标答
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;}
};DP方法跳过。
55. 跳跃游戏
思路本题由于跳跃步数可以自由选故只要在我们的跳跃范围内全部都可以跳到只要一次遍历整个数组当跳跃范围覆盖到末尾即返回true如果还没遍历到数组末尾就已经超出了覆盖范围说明不可能到达末尾返回false。时间复杂度O(n)。
class Solution {
public:bool canJump(vectorint nums) {int range0;for(int i0;inums.size()irange;i){//i还需要在覆盖范围内if(rangeinums[i]){//更新覆盖范围rangeinums[i];}if(rangenums.size()-1){return true;}}return false;}
};本题的关键点是想到使用范围来覆盖。
45.跳跃游戏II
思路本题和上题的区别是题目说了一定可以到达末尾而要返回最小跳跃次数。想不到方法直接看答案。要以最小的步数增加覆盖范围覆盖范围一旦到达终点那么就是答案。考虑两步的覆盖范围即这一步的最大覆盖范围和下一步的最大覆盖范围如果这一步怎么都走不到终点那么就需要开始考虑下一步的覆盖范围了具体怎么跳我们不用考虑但我们知道两步一定可以达到这么的最大覆盖范围如果还没到终点就继续往后直到覆盖终点为止。时间复杂度O(n)。
class Solution {
public:int jump(vectorint nums) {if(nums.size()1) return 0;int curRange0;//一开始初始化为0int nextRange0;int ans0;for(int i0;inums.size();i){nextRangemax(nextRange,inums[i]);//不断更新下一步最大覆盖范围if(icurRange){//遍历到的当前最大下标,但是肯定还没到终点ans;curRangenextRange;if(nextRangenums.size()-1){break;}}}return ans;}
};代码的主要亮点是首先将curRange初始化为0这样以开始就可以进行nextRange的计算。
