海智算法训练营第三十三天 | 第八章 贪心算法 part03 | ● 1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果

 今日任务:

1.k次取反后最大化数组和

2.贪心解决加油站问题

3.左右边界分别处理——分发糖果

1.k次取反后最大化数组和

力扣题目链接

这道题比较简单就不多说了。

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);for (int i = 0; i < nums.length && nums[i] < 0 && k > 0; i++) {nums[i] = -nums[i];k--;}Arrays.sort(nums);if(k % 2 == 1)  nums[0] = -nums[0];int sum = Arrays.stream(nums).sum();return sum;}
}

2.贪心解决加油站问题

力扣题目链接

题目要求: 

这是此题的贪心解法,先把每个站点总需要花费的油量计算出来,如果所有油量加起来是小于零的那么不管怎样都是不能转一圈的。

这道题可以这样理解,找到curSum的最小值,从该最小值的后一个值开始走就对了,理解成,你需要在前面累积最多的油量,给这个消耗最多的点去用。

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

此外另外一种方法也很好理解但是不是贪心的算法:

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum = 0;int min = 0;for (int i = 0; i < gas.length; i++) {sum += (gas[i] - cost[i]);min = Math.min(sum, min);}if (sum < 0) return -1;if (min >= 0) return 0;for (int i = gas.length - 1; i > 0; i--) {min += (gas[i] - cost[i]);if (min >= 0) return i;}return -1;}
}

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

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的

  • 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。

  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。(主要是这里,从后往前遍历和负数进行抵消)

3.左右边界分别处理——分发糖果

力扣题目

题目描述:

首先创建数组,给每个位置都赋值为1,先看左边,从左到右如果右边的数比左边大,那么就+1,再看右边,从右到左,如果左边比右边大,那么这时候如果想要满足左边又满足右边的条件的话那就需要选取当前的最大值,这样才不会冲突。

看评论有个比较好理解的说法:两种情况要同时满足,原先小的糖果数我就可以满足,我更大的糖果数怎么就满足不了了呢?

class Solution {public int candy(int[] ratings) {int res[] = new int[ratings.length];Arrays.fill(res,1);for (int i = 1; i < ratings.length; i++) {if(ratings[i] > ratings[i-1]){res[i] = res[i-1] + 1;}}for (int i = ratings.length-2; i >= 0; i--) {if(ratings[i] > ratings[i+1]){res[i] = Math.max(res[i] , res[i+1] + 1);}}return Arrays.stream(res).sum();}
}

学习时长:2h

总结:此次学习贪心如何解决区间问题,以及遇到需要左右判断的题目怎么去逐一分开去做。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

AS-V1000 视频监控平台产品介绍:客户端功能介绍(五)

目 录 一、引言 1.1 AS-V1000视频监控平台介绍 1.2平台服务器配置说明 二、软件概述 2.1 客户端软件用途 2.2 客户端功能 三、客户端功能说明 3.1系统配置 3.2 服务器时间校正 3.3退出 一、引言 1.1 AS-V1000视频监控平台介绍 AS-V1000视频监控平台…

【Python数据分析系列】多个dataframe写入同一个excel文件(案例源码)

一、引言 将多个DataFrame写入同一个excel文件中&#xff0c;每个DataFrame作为一个sheet&#xff0c;可以使用pandas库中的ExcelWriter类。这个类可以在一个Excel文件中创建多个sheet&#xff0c;并将不同的数据写入这些sheet中。本文演示如何将多个DataFrame写入同一个CSV文件…

用C#开发Excel插件的强大开源工具

推荐一个开源项目&#xff0c;方便我们使用C#为Excel开发插件。 01 项目简介 Excel-DNA是一个.Net开源项目&#xff0c;为开发者提供了一种便利的方法&#xff0c;可以将.Net代码与Excel集成&#xff0c;能够轻松的为Excel创建自定义函数、图表、表单等&#xff0c;一方面不仅…

<网络安全>《55 概念讲解<第二课 MAC地址>》

1 MAC地址是什么&#xff1f; MAC地址&#xff08;Media Access Control Address&#xff09;是一种标识网络设备的唯一地址&#xff0c;也被称为物理地址或硬件地址。它由网络设备制造商在生产过程中写入网卡的EPROM&#xff08;一种可擦写的闪存芯片&#xff09;。 IP地址和…

状态机-----

1.原理 同步的意思就是状态的跳转都是在时钟的作用下跳转的&#xff0c;有限是指状态机中状态的个数是有限的。两种状态机的共同点都是状态的跳转只和输入有关&#xff0c;区别就是如果最后的输出只和当前状态有关而与输入无关&#xff0c;则是moore型状态机。如果最后的输出不…

华为配置AP和AC之间NAT穿越示例

配置AP和AC之间NAT穿越示例 组网图形 图1 组网配置图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件 业务需求 企业用户接入WLAN网络&#xff0c;以满足移动办公的最基本需求。且在覆盖区域内移动发生漫游时&#xff0c;不影响用户的业务使用。 AP位于企业分部…

C/C++基础语法

C/C基础语法 文章目录 C/C基础语法头文件经典问题秒数转换闰年斐波那契数列打印n阶菱形曼哈顿距离菱形图案的定义大数计算 输入输出格式化输入输出getline()函数解决cin只读入一个单词的问题 运算符赋值运算符 Switch循环处理未知数量输入的几种常见方法for-each 字符串String字…

【Java EE初阶二十五】简单的表白墙(一)

1. 前端部分 1.1 前端代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"wid…

【嵌入式学习】QT-Day4-Qt基础

简单实现闹钟播报&#xff0c;设置时间&#xff0c;当系统时间与设置时间相同时播报语音5次&#xff0c;然后停止。如果设置时间小于当前系统时间&#xff0c;则弹出消息提示框&#xff0c;并清空输入框。 #include "my_clock.h" #include "ui_my_clock.h&quo…

远程控制APP,高效生活的秘诀!

在这个科技日新月异的时代&#xff0c;我们的生活被各种手机软件所包围。几乎每个人都有一个甚至多个手机&#xff0c;你是否也有遇到过需要远程操作自己某一台手机的场景呢&#xff1f;今天&#xff0c;我要向大家推荐一款神奇的手机远程操作神器&#xff0c;让你可以随时随地…

C++ //练习 9.5 重写上一题的函数,返回一个迭代器指向找到的元素。注意,程序必须处理未找到给定值的情况。

C Primer&#xff08;第5版&#xff09; 练习 9.5 练习 9.5 重写上一题的函数&#xff0c;返回一个迭代器指向找到的元素。注意&#xff0c;程序必须处理未找到给定值的情况。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 3工具&#xff1a;vim 代码块 …

Anaconda和TensorFlow环境搭建!!

Anaconda下载 进入官网下载 https://www.anaconda.com/download 也可以通过清华的映像站下载&#xff1a; https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 我这里下载的是3.4.20版本。下载好就可以安装默认安装就行。 打开Anaconda Prompt修改成国内镜像 conda c…

Coursera吴恩达机器学习专项课程02:Advanced Learning Algorithms 笔记 Week01

Advanced Learning Algorithms Week 01 笔者在2022年7月份取得这门课的证书&#xff0c;现在&#xff08;2024年2月25日&#xff09;才想起来将笔记发布到博客上。 Website: https://www.coursera.org/learn/advanced-learning-algorithms?specializationmachine-learning-in…

Kafka源码搭建以及系统架构

Kafka源码分析环境搭建 使用截止目前为止Kafka的最新版本3.3.1版本的源码进行环境搭建 Kafka源码下载 从kafka官网下载kafka-3.3.1版本的源码 http://kafka.apache.org/downloads 解压(要放到英文目录&#xff0c;不然会报一些奇怪的错误) Scala安装 因为在源码中配置的sc…

什么是SSH端口转发?

目录 前言&#xff1a; 一、SSH端口转发的概念 二、SSH端口转发的类型 2.1 本地端口转发 2.2 远程端口转发 2.3 动态端口转发 三、SSH端口转发的用途 3.1 安全远程访问 3.2 跨越网络限制 3.3 加密流量传输 3.4 跨越 NAT 网络 3.5 安全代理 四、总结 前言&#xff…

AI:138-开发一种能够自动化生成艺术品描述的人工智能系统

🚀点击这里跳转到本专栏,可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航! 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带关键代码,详细讲解供大家学习,希望…

时间序列分析实战(六):ARIMA乘法(疏系数)模型建模及预测

&#x1f349;CSDN小墨&晓末:https://blog.csdn.net/jd1813346972 个人介绍: 研一&#xff5c;统计学&#xff5c;干货分享          擅长Python、Matlab、R等主流编程软件          累计十余项国家级比赛奖项&#xff0c;参与研究经费10w、40w级横向 文…

HarmonyOS—低代码开发Demo示例

接下来为大家展示一个低代码开发的JS工程的Demo示例&#xff0c;使用低代码开发如下华为手机介绍列表的HarmonyOS应用/服务示例。 1.删除模板页面中的控件后&#xff0c;选中组件栏中的List组件&#xff0c;将其拖至中央画布区域&#xff0c;松开鼠标&#xff0c;实现一个List组…

多模态表征—CLIP及中文版Chinese-CLIP:理论讲解、代码微调与论文阅读

我之前一直在使用CLIP/Chinese-CLIP&#xff0c;但并未进行过系统的疏导。这次正好可以详细解释一下。相比于CLIP模型&#xff0c;Chinese-CLIP更适合我们的应用和微调&#xff0c;因为原始的CLIP模型只支持英文&#xff0c;对于我们的中文应用来说不够友好。Chinese-CLIP很好地…

Mysql常见函数和用法(重点)

where子句中经常使用的运算符 -- 查询总分大于200分的所有同学 select * from student2 where (chineseenglishmath)>200; -- 查询math大于60 并且(and)id大于4的学生成绩 select * from student2 where math>60 and id>4; -- 查询英语成绩大于语文成绩的同学 select …