目录
题目链接:122.买卖股票的最佳时机II
思路
代码
题目链接:55. 跳跃游戏
思路
代码
题目链接:45.跳跃游戏II
思路
代码
总结
题目链接:122.买卖股票的最佳时机II
思路
每天可以重复买卖,所以只需要计算每天的净利润,只加正数即可。想明白了就很简单。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0; // 记录利润和
for (int i = 0; i < prices.size() - 1; i++) {
// 记录每天的净利润,但只收集正数
int profit = prices[i + 1] - prices[i];
if (profit > 0) {
result += profit;
}
}
return result;
}
};
题目链接:55. 跳跃游戏
思路
数组中的数字代表可以跳跃的最大范围,例如3,可以选择1,2,3。不用跳跃来思考,用覆盖范围,主要覆盖范围足以达到最后一个下标,就说明可以达到。在遍历数组过程中,以覆盖范围为上限,并且每次更新最大的覆盖范围。
代码
class Solution {
public:
bool canJump(vector<int>& nums) {
// 数组长度为1,直接到达终点,返回true
if (nums.size() == 1)
return true;
int cover = 0; // 覆盖范围
// 遍历数组,只在覆盖范围内遍历
for (int i = 0; i <= cover; i++) {
// 取最大覆盖范围
cover = (i + nums[i]) > cover ? (i + nums[i]) : cover;
// 如果可以覆盖最后一个元素,说明可以到达
if (cover >= nums.size() - 1)
return true;
}
return false;
}
};
题目链接:45.跳跃游戏II
思路
与55.跳跃游戏不同的是还需要记录最小步数,因为每一步跳跃的步数不确定,还是从覆盖范围下手。只不过需要两个覆盖范围,一个是当前的覆盖范围,另一个是下一步的覆盖范围。
在遍历当前覆盖范围时,记录下一步的最大覆盖范围,并进行更新。
如果下标移动到了当前覆盖的最大范围处,则步数加一,当前覆盖范围更新为下一次的覆盖范围,继续遍历。
直至遍历到数组的倒数第二位结束遍历。不到最后是因为最后可以一步一定可以达到,题目给的都是可以到达的情况,所以只用关心步数即可。
代码
class Solution {
public:
int jump(vector<int>& nums) {
int curDistance = 0;
int nextDistance = 0;
int step = 0;
// 数组遍历到倒数第二位
// 如果覆盖范围刚好只能达到倒数第二位,步数加一即可达到最后一位
// 如果可以覆盖到最后一位,则结束,之前记录的步数就是最小步数
for (int i = 0; i < nums.size() - 1; i++) {
// 下一步可以跳多远,这里记录的是在这个区间内最大的跳跃范围
nextDistance = max(i + nums[i], nextDistance);
// 如果下标到了最大覆盖范围,说明该往下跳一步了
if (i == curDistance) {
// 更新覆盖范围,也是下一步最大的跳跃范围
curDistance = nextDistance;
step++; // 步数加1
}
}
return step;
}
};
总结
①第一题与昨天的最长子序列类似,但是刚开始不好理解题意,一天内可重复买卖是关键,突破点在于记录每天的盈利,只累加正数
②第二第三题也是思路的转变,从每步的跳跃,转变为每次的覆盖范围,这样转变可以避免讨论每次跳跃了几步
③目前来看,贪心问题难点不在于代码,而在于思路,想通的话代码写起来很简单