一.力扣122.买卖股票的最佳时机
思路
方法一：这个题跟上一期的摆动数列有点像，简单来说就是找多个递增序列，用每个序列中的的最大值减去最小值，并求和。
要求得最大值减去最小值，我们可以累加递增序列相邻元素的差值。
方法二：求出数组中相邻元素的差值（当前元素减去上一个），会得出一个利润数组，显而易见，这个利润数组可能有正数有负数，我们只需要把所有的正数加起来就可以了。
代码实现
方法一：
class Solution {
public:
int maxProfit(vector
int con = 0;//记录利润
int i = 0;
for(int j = 1;j < prices.size();j++)
{
if(prices[j] > prices[i])
con += (prices[j]-prices[i]);
i = j;
}
return con;
}
};
方法二：
class Solution {
public:
int maxProfit(vector
int con = 0;//记录利润
for(int j = 1;j < prices.size();j++)
{
con += max(prices[j]-prices[j-1],0);
}
return con;
}
};
二. 55跳跃游戏
思路
假如当前所在下标指向的元素使3，我们要确定的不是这次走几步，而是最多能走到哪里，即覆盖范围，确定了这个元素覆盖范围之后，再找覆盖范围之内每个元素的覆盖范围，直到找到倒数第二个元素的覆盖范围，看最大覆盖范围是否能到达终点。
代码实现
class Solution {
public:
bool canJump(vector
int s = nums.size();
if(s == 1)//特殊情况，只有一个元素
return true;
int cover = nums[0];
for(int i = 1;i < s-1;i++)
{
if(i <= cover)
cover = max(cover,i+nums[i]);
}
if(cover >= s-1)
return true;
return false;
}
};
三. 45跳跃游戏II
思路
这个题目和上一个一样还是看覆盖范围，只不过这次是以步数为单位去看，看每一步的最大覆盖范围，如果最大范围到不了终点就加一步，如图所示
易错点
这是我的错误代码（错误点：1.在 i 大于cover的时候才更新了cover和con 2.更新nextcover时的语句错误）
class Solution {
public:
int jump(vector
int s = nums.size();
int con = 1;//记录步数
if(s == 1)//只有一个元素的特殊情况
return 0;
int cover = nums[0];
int nextcover = cover;
for(int i = 1;i < s-1;i++)
{
if(cover >= s-1)
break;
if(i <= cover)
nextcover = max(cover,i+nums[i]);
else
{
con++;
cover = nextcover;
}
}
return con;
}
};
无法通过下图示例
自己模拟一下运行过程发现
第一：
当i = 1时，cover未更新，con为1
然后我们进入下一次循环，发现此时i已经不满足进入下一次循环的条件，就算进入了下一次循环，那也是更新cover为nextcover，但此时我们并没有判断更新i点的覆盖范围也就是nextcover。
由此可见，错误点在于每一次循环都需要判断是否应该更新nextcover，而且要在i = cover时更新cover和con，因为此时已经到达了此步数所能走到的最远处，这里不是终点，所以步数势必会加1，而且如果现在不修改下一步已经超过cover，那是新的cover也就是nextcover应该限制的位置。
第二：
更新nextcover的语句应为 nextcover = max(nextcover,i+nums[i]);
代码实现
class Solution {
public:
int jump(vector
int s = nums.size();
int con = 1;//记录步数
if(s == 1)//只有一个元素的特殊情况
return 0;
int cover = nums[0];
int nextcover = cover;
for(int i = 1;i < s-1;i++)
{
if(cover >= s-1)
break;
nextcover = max(nextcover,i+nums[i]);
if(i == cover)
{
con++;
cover = nextcover;
}
}
return con;
}
};
推荐阅读
发表评论