代码随想录day28贪心算法2

122.买卖股票的最佳时机 II

题目链接
文章讲解

class Solution {
public:int maxProfit(vector<int>& prices) {int res=0;for(int i=0;i<prices.size()-1;i++){res+=max(prices[i+1]-prices[i],0);}return res;}
};

55. 跳跃游戏

题目链接
文章讲解

class Solution {
public:bool canJump(vector<int>& nums) {// Base case: 如果数组只有一个元素，直接返回trueif (nums.size() == 1) return true;int ans = nums[0];  // 以第一个元素的值作为初始的最大可达位置// 从第一个位置开始遍历数组for (int i = 1; i < nums.size(); i++) {// 如果当前位置 i 无法到达（i 大于 ans），则返回 falseif (i > ans) return false;// 更新最大可达位置ans = max(ans, i + nums[i]);// 如果可以到达最后一个位置，直接返回 trueif (ans >= nums.size() - 1) return true;}return false;  // 如果遍历结束后还没有到达最后一个位置，返回 false}
};

45.跳跃游戏 II

题目链接
文章讲解

class Solution {
public:int jump(vector<int>& nums) {// 初始化变量：cur表示当前能到达的最远位置，next表示下一步能到达的最远位置int cur = 0, next = 0;// 特殊情况：如果数组只有一个元素，已经在最后位置，跳跃次数为0if (nums.size() == 1) return 0;int res = 0;  // 记录跳跃的次数// 遍历整个数组for (int i = 0; i < nums.size(); i++) {// 更新当前能够到达的最远位置cur = max(cur, i + nums[i]);// 如果当前最远位置已经可以到达末尾，跳出循环if (cur >= nums.size() - 1) break;// 当i达到next时，意味着需要进行一次跳跃才能继续前进if (i == next) {res++;  // 跳跃次数增加next = cur;  // 更新下一跳能够到达的最远位置}}// 返回跳跃次数加1，因为跳跃结束后需要再加一次跳跃return res + 1;}
};

1005.K次取反后最大化的数组和

题目链接
文章讲解

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {// 首先对数组进行排序，将负数放到数组前面sort(nums.begin(), nums.end());// 遍历数组，对负数进行取反，直到操作次数 k 用完int j = 0;for (int i = 0; i < nums.size() && k > 0; i++) {if (nums[i] < 0) { // 如果当前元素是负数，取反并减少操作次数 knums[i] = -nums[i];k--; // 每次取反减少一个操作次数}else break; // 如果当前元素不再是负数，结束取反操作}// 排序一下数组，确保最小的数在数组前面sort(nums.begin(), nums.end());// 初始化总和变量int sum = 0;// 如果 k 仍为奇数，说明还剩一次操作，且最小的数已经是正数// 这时我们需要取反数组中的最小数来最大化和if (k % 2 == 1) {// 对数组中的第一个元素（最小的元素）进行取反nums[0] = -nums[0];}// 计算数组的总和for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 返回最终的总和return sum;}
};