代码随想录二刷 day34 | 贪心之1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

news/2025/1/15 12:20:00/

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

题目链接
解题思路: 两次贪心
如何可以让数组和最大呢?
局部最优:让绝对值大的负数变为正数,当前数值达到最大,整体最优:整个数组和达到最大
如何转变K次正负,让 数组和 达到最大。
局部最优:只找数值最小的正整数进行反转,当前数值和可以达到最大(例如正整数数组{5, 3, 1},反转1 得到-1 比 反转5得到的-5 大多了),全局最优:整个数组和达到最大。
解题步骤为:

  • 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
  • 第二步:从前向后遍历,遇到负数将其变为正数,同时K- -
  • 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
  • 第四步:求和

代码如下:

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp);       // 第一步for (int i = 0; i < A.size(); i++) { // 第二步if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步int result = 0;for (int a : A) result += a;        // 第四步return result;}
};

134. 加油站

题目链接
解题思路:
从全局进行贪心选择,情况如下:

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的
  • 情况二:rest[i] =gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。
  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。

C++代码如下:

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX; // 从起点出发,油箱里的油量最小值for (int i = 0; i < gas.size(); i++) {int rest = gas[i] - cost[i];curSum += rest;if (curSum < min) {min = curSum;}}if (curSum < 0) return -1;  // 情况1if (min >= 0) return 0;     // 情况2// 情况3for (int i = gas.size() - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
};

135. 分发糖果

题目链接
解题思路: 先确定 一边 再确定另一边
先确定右边评分大于左边的情况(也就是从前向后遍历)

此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个,所以贪心:candyVec[i] = candyVec[i - 1] + 1

代码如下:

// 从前向后
for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}

在这里插入图片描述再确定左孩子大于右孩子的情况(从后向前遍历)

遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?

因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果,所以 要从后向前遍历。

如果从前向后遍历,rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图:
在这里插入图片描述所以确定左孩子大于右孩子的情况一定要从后向前遍历
如果 ratings[i] > ratings[i + 1],此时candyVec[i](第i个小孩的糖果数量)就有两个选择了,一个是candyVec[i + 1] + 1(从右边这个加1得到的糖果数量),一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。

那么又要贪心了,局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。

局部最优可以推出全局最优。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多。

如图:
在这里插入图片描述所以该过程代码如下:

// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}
}

整体代码如下:

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);// 从前向后for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}// 从后向前for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}}// 统计结果int result = 0;for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];return result;}
};

http://www.ppmy.cn/news/580618.html

相关文章

CDN能防住攻击吗?

&#x1f482; 个人网站:【海拥】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 目录 前言什么是CDN&#xf…

施乐700彩机服务器维修,佳铭办公设备:施乐彩机维修代码

009-360 Y 鼓没有装好 009-361 M 鼓没有装好 009-362 C鼓没有装好 009-363 K鼓没有装好 009-380 Y 显影仓没装好 752-109改为0 009-381 M 显影仓没装好 752-110改为0 009-382 C 显影仓没装好 752-111改为0 009-383 K 显影仓没装好 752-112改为0 009-390 K 碳粉盒 752-686改为0 …

彩色打印机水印门:佳能、施乐暗藏美国政府跟踪代码

2019独角兽企业重金招聘Python工程师标准>>> 电子前线基金&#xff08;EFF&#xff09;近日揭开了一个隐藏多年的办公室秘密&#xff1a;市面上大多数彩色打印机打印文档的防伪点阵水印中暗藏着可供美国政府特勤部门追踪的代码&#xff08;上图&#xff09;。 据国外…

5ic计算机考试考卷读取错误,最新计算机一级试题第五套

最新计算机一级试题第五套 (15页) 本资源提供全文预览&#xff0c;点击全文预览即可全文预览,如果喜欢文档就下载吧&#xff0c;查找使用更方便哦&#xff01; 19.9 积分 全真模拟试卷一、基础知识必答题(共45题)(一)是非题1. 确保网络信息安全的目的是为了保证网络能高速运行…

深度学习期末复习

学期内容回顾 一、人工智能的概念&#xff0c;发展历程及每个历程的特点和代表性理论或算法&#xff0c;或主要驱动力 二、人工神经网络ANN的前向传播计算和误差反向回传原理 三、卷积神经网络CNN的前向传播计算和误差反向回传原理 注意对比分析ANN与CNN的相同之处和不同之…

罗晨:梦想照进现实,一个独立开发者的田园诗

非商业转载请注明作译者、出处&#xff0c;并保留本文的原始链接&#xff1a;http://www.ituring.com.cn/article/47972 他种有机蔬菜、他搞全景摄影、他自己设计制作硬件产品&#xff0c;他还是个程序员&#xff0c;并以此为生。罗晨&#xff0c;他是Markdown编辑器Mou的作者&…

数字图像处理(冈萨雷斯 第三版)

1.1 图像与图像处理的概念 图像(Image)&#xff1a; 使用各种观测系统以不同形式和手段观测客观世界而获得的&#xff0c;可以直接或间接作用于人眼并进而产生视觉的实体。包括&#xff1a; 各类图片&#xff0c;如普通照片、X光片、遥感图片&#xff1b; 各类光学图像&…

文章收录1

3.Hive Metastore 代码简析 4.受限的玻尔兹曼机 5.以公司实际应用讲解OpenStack到底是什么 6.Ubuntu12.04安装hadoop 7.vpsmate安装完再重启服务器&#xff0c;vpsmate不无再次打开的解决方法 8.如何使用JDBC快速处理大数据 9.关于集群技术的几个新工具的介绍 10.CHD4 impala安…