day33 贪心算法 | 1005、K次取反后最大化的数组和 134、加油站 135、分发糖果
题目
1005、K次取反后最大化的数组和
给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)
以这种方式修改数组后,返回数组可能的最大和。
示例 1:
输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。
示例 2:
输入:A = [3,-1,0,2], K = 3
输出:6
解释:选择索引 (1, 2, 2) ,然后 A 变为 [3,1,0,2]。
示例 3:
输入:A = [2,-3,-1,5,-4], K = 2
输出:13
解释:选择索引 (1, 4) ,然后 A 变为 [2,3,-1,5,4]。
提示:
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100
class Solution {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();}
}
class Solution {public int largestSumAfterKNegations(int[] A, int K) {if (A.length == 1) return k % 2 == 0 ? A[0] : -A[0];Arrays.sort(A);int sum = 0;int idx = 0;for (int i = 0; i < K; i++) {if (i < A.length - 1 && A[idx] < 0) {A[idx] = -A[idx];if (A[idx] >= Math.abs(A[idx + 1])) idx++;continue;}A[idx] = -A[idx];}for (int i = 0; i < A.length; i++) {sum += A[i];}return sum;}
}
134、加油站
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
说明:
如果题目有解,该答案即为唯一答案。
输入数组均为非空数组,且长度相同。
输入数组中的元素均为非负数。
示例 1: 输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3 解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。
示例 2: 输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释: 你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。因此,无论怎样,你都不可能绕环路行驶一周。
// 解法1
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;}
}
// 解法2
class Solution {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;}
}
135、分发糖果
老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
你需要按照以下要求,帮助老师给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、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;}
}
相关文章:
day33 贪心算法 | 1005、K次取反后最大化的数组和 134、加油站 135、分发糖果
题目 1005、K次取反后最大化的数组和 给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。) 以这种方式修改…...
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
1.题目描述n 个砖块排成一排,从左到右编号依次为 1∼n。每个砖块要么是黑色的,要么是白色的。现在你可以进行以下操作若干次(可以是 0 次):选择两个相邻的砖块,反转它们的颜色。(黑变白…...
mysql读写分离(maxscale)
1. 环境架构 需要三台服务器。192.168.2.10(master)192.168.2.20(slave)192.168.2.30(maxscale) 2. 部署mysql主从同步 mysql主从同步可以参考mysql主从同步 3. 部署maxscale服务 MaxScale中间件软件 …...
第八章 - 数据分组( group by , having , select语句顺序)
第八章 - 数据分组 group by数据分组过滤分组 having分组排序groub by语句的一些规定select语句顺序数据分组 在使用group by进行分组时,一般都会配合聚合函数一起使用,实现统计数据的功能。比如下面例子,需要按性别计算人数。按性别进行分组…...
Git(GitHub,Gitee 码云,GitLab)详细讲解
目录第一章 Git 概述1.1 何为版本控制1.2 为什么需要版本控制1.3 版本控制工具1.4 Git 简史1.5 Git 工作机制1.6 Git 和代码托管中心第二章 Git 安装第三章 Git 常用命令3.1 设置用户签名3.2 初始化本地库3.3 查看本地库状态3.3.1 首次查看(工作区没有任何文件&…...
策略模式(Strategy Pattern)
编写鸭子项目,具体要求如下: 1) 有各种鸭子(比如 野鸭、北京鸭,水鸭等,鸭子有各种行为,比如 叫,飞行等) 2)显示鸭子的信息 传统方案解决鸭子问题 1࿰…...
《Qt6开发及实例》6-2 Qt6基础图形的绘制
目录 一、绘图框架设计 二、绘图区的实现 2.1 PaintArea类 2.2 PaintArea类讲解 三、主窗口的实现 3.1 MainWidget类 3.2 MainWidget类讲解 3.3 槽函数编写 3.5 其他内容 一、绘图框架设计 界面 两个类 二、绘图区的实现 2.1 PaintArea类 paintarea.h #ifndef…...
LeetCode 382. 链表随机节点
原题链接 难度:middle\color{orange}{middle}middle 题目描述 给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样 。 实现 SolutionSolutionSolution 类: Solution(ListNodehead)Solution…...
iOS开发AppleDeveloper中给别人授权开发者权限后,对方一直显示不了我的开发账号team
在iOS开发经常出现多人协作开发的情况。这时我们通常要发邮件邀请别的用户为开发者或者app管理就可以开发我们自己的项目了。但是这次我给别人授权开发者权限后,发现别人权限中没有证书相关权限如图:并且别人登录该账号后,在xcode中只有一个看…...
FreeRTOS数据类型和编程规范
目录 数据类型 变量名 函数名 宏的名 数据类型 每个移植的版本都含有自己的portmacro.h头文件,里面定义了2个数据类型 TickType_t FreeRTOS配置了一个周期性的时钟中断:Tick Interrupt每发生一次中断,中断次数累加,这被称为t…...
【python知识】win10下如何用python将网页转成pdf文件
一、说明 本篇记录一个自己享用的简单工具。在大量阅读网上文章中,常常遇到一个专题对应多篇文章,用浏览器的收藏根本不够。能否见到一篇文章具有搜藏价值,就转到线下,以备日后慢慢消化吸收。这里终于找到一个办法,将在…...
C语言常见关键字
写在前面 这个博客是结合C语言深度解剖这本书和我以前学的知识综合而成的,我希望可以更见详细的谈一下C语言的关键字,内容有点多,有错误还请斧正. 常见关键字 下面我们说下C语言的关键字,所谓的关键字是指具有特定功能的单词,我们可以使用关键字来帮助我们完成不同的事物.C语…...
【MT7628】固件开发-SDK4320添加MT7612E WiFi驱动操作说明
解压5G WiFi MT7612E驱动1.1解压指令 tar -xvf MT76x2E_MT7620_LinuxAP_V3.0.4.0_P2_DPA_20160308.tar.bz2 1.2解压之后会出现以下两个目录 rlt_wifi rlt_wifi_ap 1.3将解压后的文件拷贝到系统下 拷贝路径 RT288x_SDK/source/linux-2.6.36.x/drivers/net/wireless 内核中打开驱…...
如何从手工测试进阶自动化测试?阿里10年测开经验分享...
随着行业的竞争加剧,互联网产品迭代速度越来越快,QA 与测试工程师都需要在越来越短的测试周期内充分保证质量。可是,App 测试面临着很多挑战,比如多端发布、多版本发布、多机型发布等等,导致了手工测试很难完全胜任。因…...
C++复习笔记11
1. vector是表示可变大小数组的序列容器。 2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被…...
【MT7628】固件开发-SDK4320添加MT7628 WiFi驱动操作说明
解压2.4G WiFi MT7628驱动1.1解压指令 tar -xvf MT7628_LinuxAP_V4.1.0.0_DPA_20160310.tar.bz2 1.2解压之后会出现以下两个目录 mt_wifi mt_wifi_ap 1.3将解压后的文件拷贝到系统下 拷贝路径 RT288x_SDK/source/linux-2.6.36.x/drivers/net/wireless 内核中打开驱动编译修改R…...
C#开发的OpenRA游戏加载界面的实现
C#开发的OpenRA游戏加载界面的实现 游戏的UI是一个游戏必备, 但是游戏的UI都是自己处理的,不能使用像Windows自带的UI。 这样游戏的UI,其实也是使用游戏的方式来显示的, 只不过使用了低帧率的方式来显示。 比如OpenRA游戏界面,就会显示如下: 游戏的界面有很多,先从一个简…...
渲染农场优势是什么_云渲染农场怎么用?
在回答渲染农场的优势这个问题之前,我先申明一下本文中提到的渲染农场/云渲染平台/云渲染农场,都特指CG领域内的专业3D渲染平台,有一些文章会强调这个叫法的区别,但是业内一般都不会分这么细,所以也就不赘述了。渲染农…...
SoapUI、Jmeter、Postman三种接口测试工具的比较分析
目录 前言 1. 用例组织方式 2. 支持的接口类型与测试类型 3. 配置不同接口类型 4. 自定义变量以及变量的作用域 5. 数据源、生成器,进行参数化 6. 流程控制 7. 结果解析、展示 8. 断言 9. 脚本扩展能力 10. 团队协作 总结 重点:配…...
Python内置函数 — sort,sorted
1、sort 列表的属性方法,对列表进行排序,默认升序,返回None值。 源码注释: """ Sort the list in ascending order and return None.The sort is in-place (i.e. the list itself is modified) and stable (i.e.…...
mysql事务隔离级别
mysql锁机制及原理1.隔离级别2.实践2.1查看事务隔离级别2.2 设置隔离级别2.3 不可重复读2.4 幻读3.幻读怎么解决3.1 Record Lock3.2 Gap Lock3.3 Next-Key Lock引用:https://blog.csdn.net/xinyuan_java/article/details/1284932051.隔离级别 SERIALIZABLE(序列化)…...
【C++】string类(下)
文章目录1.迭代器(正向遍历)begin有两个版本2.反向迭代器(反向遍历)rbegin由两个版本3. at4. insert ——头插在pos位置前插入一个字符串在pos位置前插入n个字符在迭代器前插入一个字符5. erase从pos位置开始删除len个字符从迭代器位置开始删除6. replace——替换从pos位置开始…...
Elasticsearch: Prefix queries - 前缀查询
Prefix queries 被用于在查询时返回在提供的字段中包含特定前缀的文档。有时我们可能想使用前缀查询单词,例如 Leonardo 的 Leo 或 Marlon Brando、Mark Hamill 或 Martin Balsam 的 Mar。 Elasticsearch 提供了一个前缀查询,用于获取匹配单词开头部分&a…...
GEE学习笔记 七十七:GEE学习方法简介
这是一篇关于学习方法的思考探索,当然我不会大篇文章介绍什么学习方法(因为我也不是这方面的专家?),这个只是总结一下我是如何学习GEE以及在学习中遇到问题时如何解决问题的。我写这篇文章的目的就是在和一些学习GEE的新同学接触…...
20基于主从博弈的智能小区代理商定价策略及电动汽车充电管理MATLAB程序
参考文档:《基于主从博弈的智能小区代理商定价策略及电动汽车充电管理》基本复现仿真平台:MATLABCPLEX/gurobi平台优势:代码具有一定的深度和创新性,注释清晰,非烂大街的代码,非常精品!主要内容…...
长按power键,点击重启按钮,系统重启流程一
1.有可能会涉及到如下文件 2.文件流程...
数据的TCP分段和IP分片
本文简述下TCP分段和IP分片的区别与联系。 我们知道,用户空间的数据拷贝到内核空间的TCP发送缓冲区(这个是一个结构体,叫sk_buffer,简称skb)后就由内核网络协议栈做后续的封装和发送处理了,用户无需考虑下…...
HTML中嵌入B站视频
HTML中嵌入B站视频 在网页中实现一个HTML播放器需要先从b站获取视频嵌入代码, 以前嵌入代码可以从视频分享那里拿到, 现在好像不行了 必须是自己投稿的视频, 从投稿管理页面才能找到 复制嵌入代码 建一个.html文件, 放入下面代码 <!DOCTYPE html> <html><head…...
Mars3D Studio 的使用方法
Mars3D Studio的使用 1、介绍: mars3d Studio是mars3d研发团队于近期研发上线的一款 场景可视化编辑平台。拥有资源存档、团队协作、定制材质等丰富的功能。可以实现零代码构建一个可视化三维场景。 2、功能介绍 (1)数据上传:…...
Flutter For Web实践
1 什么是Flutter Flutter是Google开源的一套UI工具包,帮助开发者通过一套代码库高效构建多平台精美应用,支持移动APP、web、桌面和嵌入式平台。Flutter和其他的跨平台解决方案的实现方式上有比较大的差异。 我们以React Native(下文简称RN&…...
360免费做网站电话/建站系统推荐
吃蜂巢的好处和坏处?吃蜂巢对人体有什么好处?大家平时最常见的蜂产品就是蜂蜜,很多人吃过蜂蜜,对于蜂蜜也比较了解,经常吃蜂蜜对身体有很多好处,最近听说有人吃蜂巢,那吃蜂巢有什么好处和坏处呢?大家平时说的蜂巢其…...
wordpress获取点赞数/品牌策略包括哪些内容
t的内省机制剖析(转)所谓内省是指面向对象语言的一种在运行期间查询对象信息的能力, 比如如果该语句有运行期间检查对象型别的能力,那么我们称它是型别内省(type intropection)的,型别内省可以用…...
wordpress启用多站点/今日足球赛事分析推荐
泉源:/www.knowsky.com做开辟的光阴要做MySQL的数据库同步,两台安设一样的琐细,都是FreeBSD5.4,安设了Apache 2.0.55和PHP 4.4.0,MySQL的版本是4.1.15,都是而今最新的版本。 1. 安设置置 两台服务器&#x…...
政府网站 建设app/google推广工具
每次看到三元表达式就会惶惶然分不清怎样读,正如语文中的断句一样,jquery源代码中的三元表达式更是不知怎样断句。附jquery中的inArray实现。 大家熟悉jquery的应该都不陌生inArray的使用方法。在源代码实现中,先推断了arr是否存在࿰…...
北京直销网站开发/磁力岛
在Unity手游开发中,经常用到插值运算,我们可以使用Mathf.Lerp自行去实现效果,但是使用插件提高了我们的开发效率,这里归结一下DoTween的基本使用方式以及效果说明: 直接代码: 1 using DG.Tweening;2 using …...
湛江有帮公司做网站/抖音排名优化
Bootstrap 是当下最流行的前端框架(界面工具集)。 是一个用于快速开发 Web 应用程序和网站的前端框架。用于开发响应式布局、移动设备优先的 WEB 项目。 移动设备优先:自 Bootstrap 3 起,框架包含了贯穿于整个库的移动设备优先的样…...