【算法刷题 | 贪心算法05】4.27(K次取反后最大化的数组和、加油站)

在这里插入图片描述

文章目录

  • 8.K次取反后最大化的数组和
    • 8.1题目
    • 8.2解法:贪心
      • 8.2.1贪心思路
      • 8.2.2代码实现
  • 9.加油站
    • 9.1题目
    • 9.2解法:贪心
      • 9.2.1贪心思路
      • 9.2.2代码实现

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

8.1题目

给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组:

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i]

重复这个过程恰好 k 次。可以多次选择同一个下标 i

以这种方式修改数组后,返回数组 可能的最大和

  • 示例一:
输入:nums = [4,2,3], k = 1
输出:5
解释:选择下标 1 ,nums 变为 [4,-2,3] 。
  • 示例二:
输入:nums = [3,-1,0,2], k = 3
输出:6
解释:选择下标 (1, 2, 2) ,nums 变为 [3,1,0,2] 。

8.2解法:贪心

8.2.1贪心思路

  • 局部最优:让绝对值大的负数变为正数,当前数值达到最大
  • 整体最优:整个数组和达到最大。

如果将负数都转变为正数了,K依然大于0此时的问题是一个有序正整数序列,如何转变K次正负,让 数组和 达到最大。

又是一个贪心:

  • 局部最优:只找数值最小的正整数进行反转,当前数值和可以达到最大(例如正整数数组{5, 3, 1},反转1 得到-1 比 反转5得到的-5 大多了),

  • 全局最优:整个 数组和 达到最大。

  • 解题步骤:

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

8.2.2代码实现

	public int largestSumAfterKNegations(int[] nums, int k) {//1、将数组按照绝对值从小到大排序nums = IntStream.of(nums).boxed().sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();//2、将数组中的负数(绝对值大)变成负数,同时k--int len=nums.length;for(int i=0;i<len;i++){if(nums[i]<0 && k>0){nums[i]*=-1;k--;}}//3、检查k是否为0,不为0,则反转绝对值最小的正数if(k%2!=0){nums[len-1]=-1*nums[len-1];}//4、求和return Arrays.stream(nums).sum();}

9.加油站

9.1题目

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -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 可为起始索引。
  • 示例二:
l;l输入: 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 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。

9.2解法:贪心

9.2.1贪心思路

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

9.2.2代码实现

image-20240427204219642

	public int canCompleteCircuit(int[] gas, int[] cost) {int sum=0;                  //从起点开始,油箱最终剩下的油量int min=Integer.MAX_VALUE;  //每个加油站过后,最小的油量for(int i=0;i<gas.length;i++){int rest=gas[i]-cost[i];sum+=rest;min=Math.min(min,sum);}//1、判断最后剩余油量是否小于0if(sum<0){return -1;}//2、循环过程中最小的油量大于等于0,说明可以从索引为0的节点开始if(min>=0){return 0;}//3、从后往前遍历,找到第一个使得min大于等于0的起点for(int i=gas.length-1;i>=0;i--){//计算当前节点剩余油量int rest=gas[i]-cost[i];min+=rest;if(min>=0){return i;}}return -1;}

在这里插入图片描述

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

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

相关文章

制作github.io学术个人主页

制作如图的学术个人主页。About me - Xianwen Ling’s Blog 学术个人主页是一个学者展示个人学术成果和研究方向的重要工具。个人主页可以集中展示学者的研究论文、出版物、演讲和发布的项目等学术成果&#xff0c;这样其他人可以更方便地了解和评估学者的研究贡献。个人主页可…

Python | Leetcode Python题解之第60题排列序列

题目&#xff1a; 题解&#xff1a; class Solution:def getPermutation(self, n: int, k: int) -> str:factorial [1]for i in range(1, n):factorial.append(factorial[-1] * i)k - 1ans list()valid [1] * (n 1)for i in range(1, n 1):order k // factorial[n - …

c#数据库: 4.修改学生成绩

将4年级的学生成绩全部修改为100分,。修改前的学生信息表如图所示: using System; using System.Collections.Generic; using System.Data.SqlClient; using System.Linq; using System.Text; using System.Threading.Tasks;namespace StudentUpdate {internal class Program{s…

Web后端开发中对三层架构解耦之控制反转与依赖注入

内聚与耦合 内聚 比如说我们刚刚书写的员工的实现类 在这里我们仅仅书写的是和员工相关的代码 而与员工无关的代码都没有放到这里 说明内聚程度较高 耦合 以后软件开发要高内聚 低耦合 提高程序灵活性 扩拓展性 分析代码 如何解耦 创建容器 提供一个容器 存储东西 存储E…

【图论】图论基础

图论不同地方讲的不太一样&#xff0c;本文仅限作者的理解 定义 图一般由点集 V V V 和边集 E E E 组成。 对于 v ∈ V v\in V v∈V&#xff0c;称 v v v 为该图的一个节点。 对于 e ∈ E e\in E e∈E&#xff0c;一般用二元组 ( u , v ) (u,v) (u,v) 表示 e e e&…

VS2022 .Net6.0 无法打开窗体设计器

拿Vs2022 建了个Demo&#xff0c;运行环境是net6.0-windows&#xff0c;无论双击或是右键都打不开窗体设计器 打开项目目录下的*.csproj.user <?xml version"1.0" encoding"utf-8"?> <Project ToolsVersion"Current" xmlns"htt…

2024年第二十一届 五一杯 (B题)大学生数学建模挑战赛 | 最大流问题,深度学习分析 | 数学建模完整代码解析

DeepVisionary 每日深度学习前沿科技推送&顶会论文&数学建模与科技信息前沿资讯分享&#xff0c;与你一起了解前沿科技知识&#xff01; 本次DeepVisionary带来的是五一杯的详细解读&#xff1a; 完整内容可以在文章末尾全文免费领取&阅读&#xff01; 第一个问题…

[高质量]2024五一数学建模A题保奖思路+代码(后续会更新)

你的点赞收藏是我继续更新的最大动力&#xff0c;可点击文末卡片获取更多资料 你是否在寻找数学建模比赛的突破点&#xff1f; 作为经验丰富的数学建模团队&#xff0c;我们将为你带来2024 年华东杯&#xff08;A题&#xff09;的全面解析包。这个解决方案包不仅包括完整的代…

实习面试算法准备之图论

这里写目录标题 1 基础内容1.1 图的表示1.2图的遍历 2 例题2.1 所有可能的路径2.2 课程表&#xff08;环检测算法&#xff09;2.2.1 环检测算法 DFS版2.2.2 环检测算法 BFS版 2.3 课程表 II &#xff08;拓扑排序算法&#xff09;2.3.1 拓扑排序 DFS版 1 基础内容 图没啥高深的…

百度安全多篇议题入选Blackhat Asia以硬技术发现“芯”问题

Blackhat Asia 2024于4月中旬在新加坡隆重举行。此次大会聚集了业界最杰出的信息安全专业人士和研究者&#xff0c;为参会人员提供了安全领域最新的研究成果和发展趋势。在本次大会上&#xff0c;百度安全共有三篇技术议题被大会收录&#xff0c;主要围绕自动驾驶控制器安全、跨…

IDEA实现Springboot项目自动热部署

每当我们在修改代码时&#xff0c;往往需要重新启动项目&#xff0c;这样不仅浪费时间而且很麻烦&#xff0c;我们可以通过IDEA的热部署来提高效率 1、首先点file >> settings >> Build Excution >> Compire&#xff0c;选择Build project auto matically 2.…

有关CSS中排版常见问题(清除默认样式问题 + 元素居中问题 + 元素之间的空白问题 + 行内块的幽灵空白问题)

前言&#xff1a;在练习CSS排版的时候&#xff0c;我们经常会遇到一些排版上的问题&#xff0c;那么我们如何去解决这些问题呢&#xff1f;本篇文章给出了一些新手在练习排版时候可能会遇到的问题的解决方案。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我…

【竞技宝jjb.lol】LOL:MSI首日赛事前瞻

北京时间2024年5月1日,英雄联盟2024MSI季中赛将在今天正式开打,今天将进行两场入围赛的比赛,分别为FLY对阵PSG以及T1对阵EST。入围赛的战队实力差距较大,但如今各大赛区的实力越来越小,即使是外卡赛区的队伍也有爆冷的可能,下面小编就为大家带来MSI首日赛事前瞻。 FLY VS PSG …

做外贸如何主动开发外贸客户

在外贸业务中&#xff0c;主动开发客户是至关重要的一步&#xff0c;它能够帮助你扩大市场覆盖范围&#xff0c;建立稳定的客户基础。以下是一些有效的策略和方法&#xff0c;可以帮助你更有效地主动开发外贸客户&#xff1a; 明确目标市场&#xff1a;首先&#xff0c;你需要确…

一键PDF水印添加工具

一键PDF水印添加工具 引言优点1. 精准定位与灵活布局2. 自由旋转与透明度调控3. 精细化页码选择4. 全方位自定义水印内容5. 无缝整合工作流程 功能详解结语工具示意图【工具链接】 引言 PDF作为最常用的文档格式之一&#xff0c;其安全性和版权保护显得尤为重要。今天&#xff…

启明云端2.4寸屏+ESP32-S3+小型智能调速电动家用除草机案例 触控三档调速,能显示电压故障码

今天给大家分享个启明云端2.4寸屏ESP32-S3小型智能调速电动家用除草机案例&#xff0c;国外有草坪文化&#xff0c;这个机器能智能触控三档调速&#xff0c;带屏能显示电压故障码&#xff0c;数显档位&#xff08;3档最大&#xff09;&#xff0c;触控屏&#xff0c;长按3秒就能…

K-近邻算法的 sklearn 实现

实验目的与要求 掌握基于 K-近邻分类算法的编程方法通过编程理解 K-近邻分类算法和该算法的基本步骤 实验器材 硬件&#xff1a;PC 机&#xff08;参与实验的学生每人一台&#xff09;软件环境&#xff1a;Python3.7 Pycharm 实验内容 使用 sklearn 库中的 neighbors 模块实…

基于python的舞蹈经验分享交流网站django+vue

1.运行环境&#xff1a;python3.7/python3.8。 2.IDE环境&#xff1a;pycharmmysql5.7/8.0; 3.数据库工具&#xff1a;Navicat11 4.硬件环境&#xff1a;windows11/10 8G内存以上 5.数据库&#xff1a;MySql 5.7/8.0版本&#xff1b; 运行成功后&#xff0c;在浏览器中输入&am…

计算机网络——应用层协议(1)

在这篇文章初识网络中&#xff0c;我介绍了关于计算机网络的相关知识&#xff0c;以及在这两篇文章中Socket编程和Socket编程——tcp&#xff0c;介绍了使用套接字在两种协议下的网络间通信方式。本篇文章中我将会进一步介绍网络中网络协议的部分&#xff0c;而这将会从应用层开…

Vue 组件单元测试深度探索:细致解析与实战范例大全

Vue.js作为一款广受欢迎的前端框架&#xff0c;以其声明式的数据绑定、组件化开发和灵活的生态系统赢得了广大开发者的心。然而&#xff0c;随着项目规模的增长&#xff0c;确保组件的稳定性和可靠性变得愈发关键。单元测试作为软件质量的守护神&#xff0c;为Vue组件的开发过程…