您的位置:首页 > 游戏 > 手游 > 佛山企业网站建站_淘宝主图制作_网站建立具体步骤是_网络优化工程师需要学什么

佛山企业网站建站_淘宝主图制作_网站建立具体步骤是_网络优化工程师需要学什么

2024/12/23 15:23:24 来源:https://blog.csdn.net/2403_88990400/article/details/144251517  浏览:    关键词:佛山企业网站建站_淘宝主图制作_网站建立具体步骤是_网络优化工程师需要学什么
佛山企业网站建站_淘宝主图制作_网站建立具体步骤是_网络优化工程师需要学什么

文章参考来源代码随想录

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;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com