贪心算法part02
文章参考来源代码随想录
122.买卖股票的最佳时机II
本题我们把最终利润分解成每天的利润，然后取正利润即可
局部最优：取每天的正利润
全局最优：最大利润
代码1
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int>result(prices.size()-1,0);
int sum=0;
for(int i=0;i<prices.size();i++){
result[i]=prices[i+1]-prices[i];
if(result[i]>0)sum+=result[i];
}
return sum;
}
};代码2
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);//这里保证了每次加入result的的均为正数
}
return result;
}
};55. 跳跃游戏
局部最优：找到每次的最大覆盖值
全局最优：找到数组中的最大覆盖值
需要注意的是：
覆盖值取 当前下标与下标覆盖值之和&当前覆盖值中 的最大值
然后每次循环到当前覆盖值（可以取到，用覆盖值初始为0取理解）
当覆盖值大于等于数组最后一位下标时 说明可以到达输出true
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(i+nums[i],cover);
if(cover>=nums.size()-1)return true;
}
return false;
}
};45.跳跃游戏II
局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一
整体最优：一步尽可能多走，从而达到最少步数
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) return 0;
int curDistance = 0; // 当前覆盖最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖最远距离下标
for (int i = 0; i < nums.size(); i++) {
nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖最远距离下标
if (i == curDistance) { // 遇到当前覆盖最远距离下标
ans++; // 需要走下一步
curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了）
if (nextDistance >= nums.size() - 1) break; // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
}
}
return ans;
}
};1005.K次取反后最大化的数组和
局部最优：取最小的数的相反数（让绝对值大的负数变为正数），当前数值达到最大
全局最优：数组和达到最大
将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
从前向后遍历，遇到负数将其变为正数，同时K--
如果K还大于0，那么反复转变数值最小的元素，将K用完
求和
class Solution {
static bool cmp(int a,int b){
return abs(a)>abs(b);
}
public:
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(int k:nums)sum+=k;
return sum;
}
};原文地址：https://blog.csdn.net/2403_88990400/article/details/144251517
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！