算法训练营第三十六天 | LeetCode 1005 K次取反后最大化的数组、LeetCode 134 加油站

news/2024/6/21 6:55:24/文章来源:https://blog.csdn.net/qq_63149342/article/details/139127366

LeetCode 1005 K次组饭后最大化的数组

这题贪的主要是数值最大化。如果K > 负数个数,我们就先将负数全部转换成它的相反数,并将K--,之后K剩余的值可以对2取模,为0的话直接得出最后结果,为的话我们要在当前所有值里取最小值,对其进行取反。如果K <= 负数个数,K用完直接结束,将数组累加即可。

代码如下:

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

LeetCode 134 加油站

兄弟们,这题我老一时隔一天,终于写出来了!其实也不是很难,就是一个比较复杂的模拟。但是里面用贪心缩短了循环次数,这就造成我们的麻烦了。

主要思路是用一个cnt模拟每次的起点,在循环内部用一个i变量模拟走过的加油站数,这里面涉及到i到达右边界后要回到1的问题。比较麻烦的是在刚开始起步时需要先走一步,便于二重循环的判断条件能够正常运转,不然i和cnt开始时处于同一位置无法判断是已经走一圈了还是刚开始的状态,这个后面需要优化下不然面试时也无法立刻就写出来。

同时这里面还用到一个特别的规律:如果从某个加油站起步没能到达的第一个加油站是a,那么从该起始加油站到a中间的任何一个加油站,都无法到达a,所以遇到无法到达的第一个加油站时,直接将cnt移到i + 1退出循环即可。需要注意判别cnt比i+1大的情况,这是为了防止多次遍历造成死循环的出现。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int cnt = 0;int gasNum = 0;while (cnt < gas.length) {gasNum += (gas[cnt] - cost[cnt]);if (gasNum < 0)  {cnt = cnt + 1;gasNum = 0;continue;}int i = cnt + 1;if (i == gas.length) i = 0;while (i != cnt) {if (gasNum + gas[i] - cost[i] >= 0) {gasNum += (gas[i] - cost[i]);i++;} else if (cnt < i + 1) {gasNum = 0;cnt = i + 1;break;} else {cnt = gas.length;break;}if (i == gas.length) i = 0;}if (i == cnt) return cnt;}   return -1;}
}

LeetCode 135 分发糖果

这题要贪心两次,一次从前往后遍历,如果右孩子比左孩子大并且他的评分比左孩子小或者相等,那么他的评分赋为左孩子评分+1

第二次从后往前遍历,如果左孩子比右孩子大并且他的评分比右孩子小或者相等,那么他的评分等于右孩子评分+1

两次分别取反向遍历的原因是有递推关系存在,前序遍历可以处理这样的情况:假如左边增加了,右边也要跟着增长,适用于右边大于左边的情况;后序遍历可以处理这样的情况:假如右边增长了,左边也要跟着增长,适用于左边大于右边的情况

这题需要再看下,不知道解法恐怕挺难写得出来

代码如下:

class Solution {public int candy(int[] ratings) {int[] num = new int[ratings.length];for (int i = 0; i < num.length; i++) {num[i] = 1;}for (int i = 0; i < ratings.length - 1; i++) {if (ratings[i] < ratings[i + 1] && num[i + 1] <= num[i]) num[i + 1] = num[i] + 1;}for (int i = ratings.length - 1; i > 0; i--) {if (ratings[i - 1] > ratings[i] && num[i - 1] <= num[i]) num[i - 1] = num[i] + 1;}int sum = 0;for (int i = 0; i < num.length; i++) sum+= num[i];return sum;}
}

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

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

相关文章

韩顺平0基础学Java——第11天

p234-249 又一个月了&#xff0c;时间过得好快啊&#xff0c;希望支棱起来 可变参数 public int sum(int ... nums){ } 这个nums是数组 细节&#xff1a; 1可变参数可以为0个&#xff0c;或任意个 2可变参数的实参可以为数组 3可变参数的本质就是数组 4可变参数可以和普通…

GaussDB数据库的备份与恢复

1.逻辑备份-gs_dump gs_dump是一款用于导出数据库相关信息的工具&#xff0c;支持导出完整一致的数据库对象&#xff08;数据库、模式、表、视图等&#xff09;数据&#xff0c;同时不影响用户对数据库的正常访问。 备份sql语句 gs_dump是openGauss用于导出数据库相关信息的工…

小程序-收货地址管理模块实现

页面结构代码&#xff1a; address-form.vue --->新建地址和修改地址页面 <template><view class"content"><form><!-- 表单内容 --><view class"form-item"><text class"label">收货人</text>…

【Docker系列】 Docker容器具体信息查询

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

excel里如何将数据分组转置?

这个表格怎样转换为下表&#xff1f;按照国家来分组&#xff0c;把不同年份对应的不同序列值进行转置&#xff1f;&#xff1f; 这演示用数据透视表就完成这个数据转换。 1.创建数据透视表 选中数据中任意单元格&#xff0c;点击插入选项卡&#xff0c;数据透视表&#xff0c;…

【C语言】大小端字节序存储

引子 不知道你是否像我一样好奇过一个问题&#xff1a;为什么每当我们在调试查看内存窗口时&#xff0c;&#xff08;以int类型为例&#xff09;4个字节内容存储的顺序好像是倒着的。 比如下面这张图&#xff0c;十进制数2077转换为十六进制是0x81d&#xff0c;四个字节分别是…

265 基于matlab的粒子群优化分数阶灰色预测模型

基于matlab的粒子群优化分数阶灰色预测模型&#xff0c;以误差结果为目标进行预测&#xff0c;输出多个预测结果。并输出迭代曲线。程序已调通&#xff0c;可直接运行。 265 分数阶灰色预测 粒子群优化算法 - 小红书 (xiaohongshu.com)

ESP32C3驱动SPI NAND

最近收到了一片国产工业级SD NAND&#xff0c;可以替代SD卡&#xff0c;容量大&#xff0c;贴片封装&#xff0c;非常适合做飞控"黑匣子"。 不用写驱动程序自带坏块管理的NAND Flash&#xff08;贴片式TF卡&#xff09;&#xff0c;尺寸小巧&#xff0c;简单易用&…

张军率中国法院代表团访问乌兹别克斯坦

张军率中国法院代表团访问乌兹别克斯坦并会见乌最高法院院长伊斯拉莫夫。张军与伊斯拉莫夫共同签署《中华人民共和国最高人民法院与乌兹别克斯坦共和国最高法院合作备忘录》。应乌兹别克斯坦共和国最高法院院长巴赫季亚尔伊斯拉莫夫邀请,当地时间5月21日至25日,中华人民共和国…

GpuMall智算云:AUTOMATIC1111/stable-diffusion-webui/stable-diffusion-webui-v1.8.0

配置环境介绍 目前平台集成了 Stable Diffusion WebUI 的官方镜像&#xff0c;该镜像中整合如下资源&#xff1a; GpuMall智算云 | 省钱、好用、弹性。租GPU就上GpuMall,面向AI开发者的GPU云平台 Stable Diffusion WebUI版本&#xff1a;v1.8.0 Python版本&#xff1a;3.10.…

【免费Web系列】大家好 ,今天是Web课程的第六天点赞收藏关注,持续更新作品 !

这是Web第一天的课程大家可以传送过去学习 http://t.csdnimg.cn/K547r 后端Web实战(IOCDI) 前言 Web开发的基础知识 &#xff0c;包括 Tomcat、Servlet、HTTP协议等&#xff0c;我们都已经学习完毕了&#xff0c;那接下来&#xff0c;我们就要进入Web开发的实战篇。在实战篇中…

linux 排查java内存溢出(持续更新中)

场景 tone.jar 启动后内存溢出,假设pid 为48044 排查 1.确定java程序的pid(进程id) ps 或 jps 都可以 ps -ef | grep tone jps -l 2.查看堆栈信息 jmap -heap 48044 3.查看对象的实例数量显示前30 jmap -histo:live 48044 | head -n 30 4.查看线程状态 jstack 48044

设计模式9——适配器模式

写文章的初心主要是用来帮助自己快速的回忆这个模式该怎么用&#xff0c;主要是下面的UML图可以起到大作用&#xff0c;在你学习过一遍以后可能会遗忘&#xff0c;忘记了不要紧&#xff0c;只要看一眼UML图就能想起来了。同时也请大家多多指教。 适配器模式&#xff08;Adapte…

这方法真牛B!论文降重从81%直降1.9%

目录 一、万字论文&#xff0c;从0到1&#xff0c;只需1小时二、获取途径三、论文从81&#xff05;降到1.9&#xff05;四、内容是别人的&#xff0c;话是自己的五、AI工具 --> 中文论文降重六、论文降重小技巧 一、万字论文&#xff0c;从0到1&#xff0c;只需1小时 通过O…

python基于深度学习的聊天机器人设计

python基于深度学习的聊天机器人设计 开发语言:Python 数据库&#xff1a;MySQL所用到的知识&#xff1a;Django框架工具&#xff1a;pycharm、Navicat、Maven 系统功能实现 登录注册功能 用户在没有登录自己的用户名之前只能浏览本网站的首页&#xff0c;想要使用其他功能都…

Thinkphp5内核宠物领养平台H5源码

源码介绍 Thinkphp5内核流浪猫流浪狗宠物领养平台H5源码 可封装APP&#xff0c;适合做猫狗宠物类的发信息发布&#xff0c;当然懂的修改一下&#xff0c;做其他信息发布也是可以的。 源码预览 源码下载 https://download.csdn.net/download/huayula/89361685

最新流媒体在线音乐系统网站源码| 音乐社区 | 多语言 | 开心版

最新流媒体在线音乐系统网站源码 源码免费下载地址抄笔记 (chaobiji.cn)

4月粽子行业线上市场销售数据分析

随着节日庆祝常态化&#xff0c;消费者对礼物消费的态度发生变化&#xff0c;这会影响粽子的消费模式和市场需求。再加上技术进步&#xff0c;如速冻粽子和真空粽子的推广&#xff0c;也极大地推动了粽子行业的发展&#xff0c;使得产品更易于保存和运输&#xff0c;从而满足了…

Redis篇 有关Redis的认识和Redis的特性应用场景

Redis 一. Redis的基本概念1.1 应用/系统1.2 模块/组件1.3 分布式1.4 集群1.5 主/从1.6 中间件1.7 可用性1.8 响应时长1.9 吞吐 二.Redis的特性三.使用场景 一. Redis的基本概念 1.1 应用/系统 一个应用就是一个组,一个服务器程序 1.2 模块/组件 一个应用,里面有很多功能,每个…

Linux VIM指令

三种模式 命令模式&#xff1a;控制屏幕光标的移动&#xff0c;字符、字或行的删除等输入对文件的一些指令 插入模式&#xff1a;对文件内容进行文字输入 底行摸索&#xff1a;文件保存或退出&#xff0c;也可以进行文件替换&#xff0c;找字符串&#xff0c;列出行号等操作…