【代码随想录算法训练营Day33】1005.K次取反后最大化的数组和;134.加油站;135.分发糖果

news/2024/4/24 17:00:53/文章来源:https://blog.csdn.net/Tammy2001/article/details/136448569

❇️Day 33 第八章 贪心算法 part03

✴️今日任务

  • 1005.K次取反后最大化的数组和
  • 134.加油站
  • 135.分发糖果

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

  • 本题简单一些,估计大家不用想着贪心 ,用自己直觉也会有思路。
  • 题目链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
  • 视频讲解:https://www.bilibili.com/video/BV138411G7LY
  • 文章链接:https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

自己的思路

  1. 先对数组进行排序
  2. 先对负数从小到大依次进行反转,
  3. 当负数被反转完了还需要反转的话,就不停反转绝对值最小的一个数(跳出循环重新排序)

自己的代码(✅通过98.38%)

踩坑:

  • 没考虑k > nums.length的情况,应该把重新排序放在for循坏外
public static int largestSumAfterKNegations(int[] nums, int k) {int sum = 0;//先对数组进行排序Arrays.sort(nums);//System.out.println(Arrays.toString(nums));//对数组中的负数进行反转for (int i = 0; i < nums.length; i++) {if(k > 0){if(nums[i] < 0){nums[i] = -nums[i];k --;//System.out.println("翻转:"+Arrays.toString(nums));}//当没有负数但还需要反转时跳出循环else{break;}}}//跳出循环找最小的正数Arrays.sort(nums);//System.out.println("重新排序:"+Arrays.toString(nums));//根据反转的次数判断第一个数的正负if(k % 2 == 0){sum += nums[0];}else{sum += -nums[0];}for (int i = 1; i < nums.length; i++) {sum += nums[i];}return sum; } 随想录思路 与我自己的大差不差 随想录代码 public int largestSumAfterKNegations(int[] nums, int K) {// 将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();int len = nums.length;      for (int i = 0; i < len; i++) {//从前向后遍历,遇到负数将其变为正数,同时K--if (nums[i] < 0 && K > 0) {nums[i] = -nums[i];K--;}}// 如果K还大于0,那么反复转变数值最小的元素,将K用完if (K % 2 == 1) nums[len - 1] = -nums[len - 1];return Arrays.stream(nums).sum();}

❇️134. 加油站

  • 本题有点难度,不太好想,推荐大家熟悉一下方法二
  • 题目链接:https://leetcode.cn/problems/gas-station/
  • 视频讲解:https://www.bilibili.com/video/BV1jA411r7WX
  • 文章链接:https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

随想录思路

贪心算法(方法一)

直接从全局进行贪心选择,情况如下:

  1. 如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的
  2. rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。
  3. 如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。
    其实我不认为这种方式是贪心算法,因为没有找出局部最优,而是直接从全局最优的角度上思考问题。
贪心算法(方法二)

可以换一个思路,首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈,说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。
如图:
在这里插入图片描述

那么为什么一旦[0,i]区间和为负数,起始位置就可以是i+1呢,i+1后面就不会出现更大的负数?
如果出现更大的负数,就是更新i,那么起始位置又变成新的i+1了。

  • 局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行
  • 全局最优:找到可以跑一圈的起始位置

总结:

  1. 定义rest[i] = gas[i]-cost[i]为一天剩下的油,curSum为rest当前累加的总和
  2. 当数组rest所有总和小于0时,说明走不了一圈
  3. 当curSum < 0时,再向后找开头

自己的代码(✅通过90.12%)

public static int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int startIndex = 0;int[] rest = new int[gas.length];int sum = 0;for (int i = 0; i < gas.length; i++) {rest[i] = gas[i] - cost[i];sum += rest[i];}if(sum < 0) return -1;for (int i = 0; i < rest.length; i++) {curSum += rest[i];if(curSum < 0){curSum = 0;startIndex = i + 1;}}return startIndex;
}

随想录代码

public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int totalSum = 0;int index = 0;for (int i = 0; i < gas.length; i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {index = (i + 1) % gas.length ;curSum = 0;}}if (totalSum < 0) return -1;return index;
}

其他方法

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length;// 相当于图表中的坐标点和最低点int sum = 0, min = 0;int start = 0;for(int i = 0; i < n; i++) {sum += gas[i] - cost[i];if(sum < min) {// 经过第i个站点后遇到新低// 所以i+1个站点就是最低点min = sum;start = i + 1;}}if(sum < 0) return -1;return start % n;}
}

❇️135. 分发糖果

  • 本题涉及到一个思想,就是想处理好一边再处理另一边,不要两边想着一起兼顾,后面还会有题目用到这个思路
  • 题目链接:https://leetcode.cn/problems/candy/
  • 视频讲解:https://www.bilibili.com/video/BV1ev4y1r7wN
  • 文章链接:https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

自己的思路

  • 一次只考虑两个小孩
    • ratings[i - 1] > ratings[i]时i - 1给2,i给1
      • 当ratings[i] > ratings[i + 1]时,前面所有小孩都多给一个(有问题),sum + i + 1
    • ratings[i - 1] < ratings[i]时i - 1给1,i+1给2
  • 所以一开始定义sum = 1,定义preCount = 1,从ratings[1]开始遍历
    • ratings[i] < ratings[i - 1]时,sum += i + preCount + 1
    • ratings[i] > ratings[i - 1]时,sum += i + 1
  • 不太对,看视频吧

随想录思路

这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼。

  1. 先确定右边评分大于左边的情况(也就是从前向后遍历)

    1. 局部最优:只要右边评分比左边大,右边的孩子就多一个糖果
    2. 全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果。
      [图片]
  2. 再确定左孩子大于右孩子的情况(从后向前遍历)

遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?
因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果,所以 要从后向前遍历。
如果从前向后遍历,rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了

如图:
在这里插入图片描述

所以确定左孩子大于右孩子的情况一定要从后向前遍历!

  • 如果 ratings[i] > ratings[i + 1]
    • candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1)

如图:
在这里插入图片描述

随想录代码

class Solution {/**分两个阶段1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 12、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大*/public int candy(int[] ratings) {int len = ratings.length;int[] candyVec = new int[len];candyVec[0] = 1;for (int i = 1; i < len; i++) {candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;}for (int i = len - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);}}int ans = 0;for (int num : candyVec) {ans += num;}return ans;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_998335.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何在Windows上使用Docker,搭建一款实用的个人IT工具箱It- Tools

文章目录 1. 使用Docker本地部署it-tools2. 本地访问it-tools3. 安装cpolar内网穿透4. 固定it-tools公网地址 本篇文章将介绍如何在Windows上使用Docker本地部署IT- Tools&#xff0c;并且同样可以结合cpolar实现公网访问。 在前一篇文章中我们讲解了如何在Linux中使用Docker搭…

从huggingface下载模型像本地加载但是UnicodeDecodeError

我自己是在Linux下出现了这个问题 原文&#xff1a;https://github.com/huggingface/transformers/issues/13674 The path for the AutoModel should be to a directory pointing to a pytorch_model.bin and to a config.json. Since you’re pointing to the .bin file dire…

全局渐变滚动条样式

效果如下&#xff1a; APP.vue<style> /* 整个滚动条 */ ::-webkit-scrollbar {width: 5px;height: 10px; } /* 滚动条上的滚动滑块 */ ::-webkit-scrollbar-thumb {background-color: #49b1f5;/* 关键代码 */background-image: -webkit-linear-gradient(45deg,rgba(255,…

Linux--搭建Zabbix监控系统

11.1 案例分析 要想实时地了解服务器的运行状况并且能在出现问题时及时解决&#xff0c;利用监控软件是一个很好的 途径。 Zabbix&#xff08;免费的&#xff09;是一个基于Web界面的企业级开源监控套件&#xff0c;提供分布式系统监控与网络监视功能。具备主机的性能监控。网络…

基于SpringBoot的中小型超市数据分析系统设计与实现

目 录 摘 要 I Abstract II 引 言 1 1 系统开发相关技术 3 1.1 SpringBoot框架 3 1.1.1发展历程 3 1.1.2 什么是SpringBoot 3 1.1.3 SpringBoot特性 3 1.1.4 SpringBoot的优势 3 1.2 MyBatis框架 4 1.2.1框架简介 4 1.2.2框架特性 4 1.3 Java语言 5 1.3.1 Java语言简介 5 1.3.…

OpenAI-Sora学习手册

通过Sora看2024红利&#xff1a;文生视频&#xff0c;虽然AI不一定是风口&#xff0c;但一定是未来深入到生活工作&#xff0c;乃至思考的必备工具。 目录 Sora介绍 Sora基础介绍 Sora官方网址 Sora的价值 1.物理世界的交互 2.创意世界的绽放 3.多角色、更精准、更细节…

Sora,OpenAI带来的视觉革新

目录 1、Sora&#xff1a;不只是一个视频生成工具 2、从文本到视频的魔法之旅 3、技术革命&#xff1a;从文本到视频的华丽转变 4、应用范围&#xff1a;无限的可能性 5、好用的GPT网站 ⭐ 想象一下&#xff0c;如果你可以仅通过敲击键盘&#xff0c;就能让你的思维火花转…

Spark实战-基于Spark日志清洗与数据统计以及Zeppelin使用

Saprk-日志实战 一、用户行为日志 1.概念 用户每次访问网站时所有的行为日志(访问、浏览、搜索、点击)用户行为轨迹&#xff0c;流量日志2.原因 分析日志&#xff1a;网站页面访问量网站的粘性推荐3.生产渠道 (1)Nginx(2)Ajax4.日志内容 日志数据内容&#xff1a;1.访问的…

最新2024年阿里云服务器地域和可用区全球分布表,不只是中国

2024年最新阿里云服务器地域分布表&#xff0c;地域指数据中心所在的地理区域&#xff0c;通常按照数据中心所在的城市划分&#xff0c;例如华北2&#xff08;北京&#xff09;地域表示数据中心所在的城市是北京。阿里云地域分为四部分即中国、亚太其他国家、欧洲与美洲和中东&…

GIN与Echo:选择正确Go框架的指南

您是否在Go中构建Web应用&#xff1f;选择正确的框架至关重要&#xff01;GIN和Echo是两个热门选择&#xff0c;每个都有其优势和特点。本指南将详细介绍每个框架的特性、速度、社区热度以及它们各自擅长的项目类型。最后&#xff0c;您将能够为您的下一个Web项目选择完美的框架…

如何在Windows系统部署Jellyfin Server并实现公网访问内网影音文件

文章目录 1. 前言2. Jellyfin服务网站搭建2.1. Jellyfin下载和安装2.2. Jellyfin网页测试 3.本地网页发布3.1 cpolar的安装和注册3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5. 结语 1. 前言 随着移动智能设备的普及&#xff0c;各种各样的使用需求也被开发出来&…

moi3D安装

下载文件双击文件 下一步 同意下一步 下一步 下一步 下一步 安装下一步 完成 破解 将如图中的文件复制到文件目录下 汉化 在目录中进入ui文件夹下 在安装包中找到如下的文件复制到ui目录下 在打开 另存为 另存为时改一下编码格式如图 打开软件 找到如图options进入…

C++:拷贝构造函数

1.概念 在现实生活中&#xff0c;可能存在一个与你一样的自己&#xff0c;我们称之为双胞胎。那在创建对象的时候&#xff0c;可否创建一个与已存在对象一模一样的新对象呢&#xff1f;答案是可以的&#xff0c;这就要通过拷贝构造函数来实现了。 拷贝构造函数&#xff1a;只有…

MindOpt优化器: 浅谈版本0.x和1.x之间API的差异

Mindopt 是一个优化求解器&#xff0c;如果它有两个主要版本——0.xx和1.x.x&#xff08;最新版本1.1.1&#xff09;&#xff0c;它们代表着软件开发的两个不同阶段。版本1.0.0表示软件的一个大的里程碑&#xff0c;代表着软件第一个正式的“成熟”发布版本&#xff0c;而0.25是…

【SpringBoot】多环境切换的灵活配置

文章目录 profile 的使用激活 profile 的方式命令行启动idea 中配置配置文件中激活 开发中最灵活的多环境配置创建四个配置主配置文件其他几个环境配置使用方式 配置文件拆分总结 在日常的开发中&#xff0c;一般都会分好几种环境&#xff0c;比如通常的 开发环境&#xff1a;一…

NTFS Disk by Omi NTFS for mac v1.1.4中文版

NTFS Disk by Omi NTFS for Mac&#xff1a;NTFS文件系统的无缝桥梁 软件下载&#xff1a;NTFS Disk by Omi NTFS for mac v1.1.4中文版 &#x1f310; 跨平台访问&#xff0c;文件无阻 NTFS Disk by Omi NTFS for Mac 为您的Mac提供了对NTFS文件系统的无缝访问。无论您是在Win…

FPGA-VGA成像原理与时序

什么是VGA: VGA, Video Graphics Array。即视频图形阵列,具有分辨率高、显示速率快、颜色丰富等优点。VGA接口不但是CRT显示设备的标准接口,同样也是LCD液晶显示设备的标准接口,具有广泛的应用范围。在FGPA中,常广泛用于图像处理等领域。 VGA 显示器成像原理 在 VGA 标准刚兴…

戏说c第二十六篇: 测试完备性衡量(代码覆盖率)

前言 师弟&#xff1a;“师兄&#xff0c;我又被鄙视了。说我的系统太差&#xff0c;测试不过关。” 我&#xff1a;“怎么说&#xff1f;” 师弟&#xff1a;“每次发布版本给程夏&#xff0c;都被她发现一些bug&#xff0c;太丢人了。师兄&#xff0c;有什么方法来衡量测试的…

供应链思维导图

https://author.baidu.com/home?frombjh_article&app_id1733215801356691 1 供应链管理流程图 2. 进销存 功能

【李沐精读系列】GPT、GPT-2和GPT-3论文精读

论文&#xff1a; GPT&#xff1a;Improving Language Understanding by Generative Pre-Training GTP-2&#xff1a;Language Models are Unsupervised Multitask Learners GPT-3&#xff1a;Language Models are Few-Shot Learners 参考&#xff1a;GPT、GPT-2、GPT-3论文精读…