「代码随想录算法训练营」第二十四天 | 贪心算法 part2
122. 买卖股票的最佳时机II
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
题目难度：中等
文章讲解：https://programmercarl.com/0122.买卖股票的最佳时机II.html
视频讲解：https://www.bilibili.com/video/BV1ev4y1C7na
题目状态：贪心有点像脑筋急转弯，靠想，没技巧
思路：
将问题化简为下图：
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i = 1; i < prices.size(); ++i) {
res += max(prices[i] - prices[i - 1], 0);
}
return res;
}
};
55. 跳跃游戏
题目链接：https://leetcode.cn/problems/jump-game/
题目难度：中等
文章讲解：https://programmercarl.com/0055.跳跃游戏.html
视频讲解：https://www.bilibili.com/video/BV1VG4y1X7kB
题目状态：没有思路，看题解
思路：
看跳跃覆盖到面积是否超出数组的长度
代码：
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if(nums.size() == 1) return true;
for(int i = 0; i <= cover; ++i) {
cover = max(nums[i] + i, cover);
if(cover >= nums.size() - 1) return true;
}
return false;
}
};
45. 跳跃游戏II
题目链接：https://leetcode.cn/problems/jump-game-ii/
题目难度：中等
文章讲解：https://programmercarl.com/0045.跳跃游戏II.html
视频讲解：https://www.bilibili.com/video/BV1Y24y1r7XZ
题目状态：依旧没有思路，看题解
思路：
这题和上一题有点变化，需要在加一个变量来记录下一步的最大覆盖面积，当这一步的覆盖面积遍历完之后还没有到达终点，那么就加步数，到下一步的最大覆盖面积上遍历，若当前覆盖面积大于等于终点了，就直接退出。
代码：
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() == 1) return 0;
int curDistance = 0;
int step = 0;
int nextDistance = 0;
for(int i = 0; i < nums.size(); ++i) {
nextDistance = max(nums[i] + i, nextDistance);
if(i == curDistance) {
step++;
curDistance = nextDistance;
if(nextDistance >= nums.size() - 1) break;
}
}
return step;
}
};
思路二
第二种思路就是贪心算法的思路，和上面类似，但不用比较下一步的最远覆盖面积了，因为如果第一步遍历到了最大覆盖面积的下一个位置了，说明当前覆盖面积并没有包括到终点，继续加一步找最远覆盖面积就行。
代码二
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() == 1) return 0;
int curDistance = 0;
int step = 0;
int nextDistance = 0;
for(int i = 0; i < nums.size() - 1; ++i) {
nextDistance = max(nums[i] + i, nextDistance);
if(i == curDistance) {
step++;
curDistance = nextDistance;
}
}
return step;
}
};
1005. K 次取反后最大化的数组和
题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
题目难度：简单
文章讲解：https://programmercarl.com/1005.K次取反后最大化的数组和.html
视频讲解：https://www.bilibili.com/video/BV138411G7LY
题目状态：久违的有思路并且通过！果然，我还是适合简单题
思路：
遍历 k 次，每次寻找数组中最小的元素，将其改为相反的数，最后将数组中的元素相加得到结果。
代码：
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
while(k--) {
int minNum = INT_MAX;
int minIdx = 0;
for(int i = 0; i < nums.size(); ++i) {
if(minNum > nums[i]) {
minNum = nums[i];
minIdx = i;
}
}
nums[minIdx] = -nums[minIdx];
}
int sum = 0;
for(auto &num : nums) sum += num;
return sum;
}
};
思路二：
使用贪心思维，将数组按照绝对值从大到小的顺序排列，然后将数组中最大且为负数的值变为正数，遍历一圈后，若 k 值还在，那就找到最小的值，反复将其转变正负数，直到 k 值消耗完。
代码二：
class Solution {
public:
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), cmp);
for(int i = 0; i < nums.size(); ++i) {
if(nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
}
if(k % 2 == 1) nums[nums.size() - 1] *= -1;
int sum = 0;
for(auto &num : nums) sum += num;
return sum;
}
};