当前位置：首页 > news >正文

代码随想录算法训练营：28/60

news 来源：原创 2024/9/19 9:58:51

非科班学习算法day28 | LeetCode122:买卖股票的最佳时机|| ，Leetcode55:跳跃游戏，Leetcode1005:K次取反后最大化的数组和

介绍

包含LC的两道题目，还有相应概念的补充。

一、LeetCode题目

1.LeetCode122:买卖股票的最佳时机||

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目解析

还是寻找局部最优解，我发现看例子很重要，看例子我的理解就是：我需要的是找差为正的区间，把他们的差收集起来；同时对于区间段的差，可以分解成每两天的差值，这就可以用for最大程度简化运算

c++代码如下：

class Solution {
public:// 开贪！-降低跳过-上升向后int maxProfit(vector<int>& prices) {int sum = 0;for (int i = 0; i < prices.size() - 1; ++i) {if (prices[i] < prices[i + 1]) {int temp = prices[i + 1] - prices[i];sum += temp;}}return sum;}
};

注意点1：因为涉及到差，所以区间确定很重要，不要超出范围。

2.Leetcode55:跳跃游戏

题目链接：55. 跳跃游戏 - 力扣（LeetCode）

题目解析

需要注意的就是维护数组的最大范围。

C++代码如下：

class Solution {
public:// 都用最大步数看能不能到最后，贪心！--维护最大覆盖范围bool canJump(vector<int>& nums) {if (nums.size() == 1)return true;int cover = 0;for (int i = 0; i <= cover; i++) // 包含cover的右边的那个点{cover = max(cover, i + nums[i]);// 注意这个覆盖范围是下标0开始的，所以是-1if (cover >= nums.size() - 1)return true;}return false;}
};

注意点1：需要注意要遍历到cover的右边的边界那个点

注意点2：不能添加nums的首位是0就false，因为存在一个例子，[0]是直接可以返回的

3.Leetcode1005:K次取反后最大化的数组和

题目链接：1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

题目解析

思路很重要，贪心的思路在于，想让尽可能的绝对值大的负数变为正数。其次我们需要处理如果次数多出来的话，就要反转绝对值最小的正数。所以需要按照绝对值排序，也算是拓展了以后的做题思路。

C++代码如下：

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] = -nums[i];k--;}}if(k%2){nums[nums.size() - 1] = -nums[nums.size() - 1];}int sum = 0;for(int i = 0; i<nums.size();i++){sum+=nums[i];}return sum;}
};

注意点1：这里使用了static将cmp作为全局的静态函数，养成良好的编程习惯。

注意点2：比较重要的技巧就是在遍历的时候，反转负数用k--作为控制变量，这样写更加简洁易懂，条件里加上k>0，这样就不需要添加很多的判断代码，记住这种处理方式。