1005. K 次取反后最大化的数组和 - 力扣(LeetCode)

题目描述

给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)

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

题目示例

输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。

解题思路

使用贪心算法,两次贪心策略解决该题,首先将数组按照绝对值从大到小排序,然后进行以下两次贪心策略。

  • 第一次贪心,我们取反,首先取反绝对值最大的负数,也就是最小值。如果第一次贪心正好消耗完 k,就不需要第二次贪心了。
  • 第二次贪心,如果我们按照第一次贪心之后,还有取反次数,我们再将数组的最后一个元素(因为第一次贪心完成后,如果还有取反次数,代表数组所有的负数已经全被取反,数组只剩正数,数组最后一个元素即为最小值)进行取反(如果 k 还剩奇数的话,因为偶数的话来回取反还是原来的值,所以就不用取反了)

最后将取反完成的数组取总和返回结果。
在这里插入图片描述

参考代码

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();
        // 第一次贪心,将最大的负数取反
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        // 第二次贪心,如果还有取反机会,将最小数字取反
        if(k % 2 == 1) {
            nums[nums.length - 1] *= -1;
        }
        // 取修改完数组的总和
        return Arrays.stream(nums).sum();
    }
}

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

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

相关文章

Oracal学习

Oracle是什么 是甲骨文公司的一款支持事务且吞吐量高的数据库特点&#xff1a; &#xff08;1&#xff09;支持多用户、大事务量的事务处理 &#xff08;2&#xff09;数据安全性和完整性控制 &#xff08;3&#xff09;支持分布式数据处理 &#xff08;4&#xff09;可移植性…

深度学习中RGB影像图的直方图均衡化python代码and对图片中指定部分做基于掩模的特定区域直方图均衡化

深度学习很重要的预处理步骤 就是需要对做直方图均衡化 其中主要分成灰度图以及RGB图的直方图均衡化 这俩的方法和代码不同 想要去看具体原理的朋友可以查看下面这篇博客的内容 写的很详细颜色直方图均衡化(https://www.cnblogs.com/wancy/p/17668345.html) 我们这个场景中会用…

Git 入门精讲

我们为什么要学习git&#xff1f; 就当下的发展而言&#xff0c;只要你从事开发就一定会接触git。作为最强大的分布式版本控制器&#xff0c;git 与 svn 有着本质上的区别。 Git是一种分布式版本控制系统&#xff0c;每个开发者都可以在本地维护完整的代码库&#xff0c;可以离…

04 经典的OSPF

思维导图的方式回顾OSPF 什么是OSPF?为什么需要OSPF? - 华为 (huawei.com) 1 ospf 领行学习思维导图 1.1 ospf 的工作过程 建立领据表同步数据库计算路由表1.2 ospf 的状态

C++ 红黑树

目录 一、红黑树的概念和性质 二、实现红黑树 1、节点定义构造 2、插入 3、左单旋&右单旋 4、中序遍历 5、检查平衡 6、获取树的高度 7、查找 8、析构 测试 完整版 一、红黑树的概念和性质 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一…

数据恢复与硬盘修理

第1篇 数据恢复与硬盘修理基础 本篇包括第1章&#xff0c;主要介绍数据恢复的发展现状、硬盘维修的基本知识以及一些基本工具的使用。 第1章 基础知识 1.1 数据恢复技术的发展和研究现状 目前国内的数据恢复服务市场处于一个极不规范的状态。虽然大部分数据恢复服务提供商是…

Linux CentOs7 安装Mysql(5.7和8.0版本)密码修改 超详细教程

CSDN 成就一亿技术人&#xff01; 今天出一期Centos下安装Mysql&#xff08;详细教程&#xff09;包括数据库密码跳过修改 CSDN 成就一亿技术人&#xff01; 目录 1.获取安装包 2.安装程序 安装下载的rpm包 查看安装包 修改5.7版本&#xff08;重要&#xff09; 安装M…

如何生成漂亮的静态文档说明页

分享&#xff1a;如何生成漂亮的静态文档说明页 最近经常被问 https://t.itmuch.com/doc.html 文档页是怎么制作的&#xff0c;考虑到步骤略复杂&#xff0c;写篇手记总结下吧。 TIPS https://t.itmuch.com/doc.html 是个人在慕课网视频《 面向未来微服务:Spring Cloud Alibab…

二叉树堆的应用实例分析:堆排序 | TOP-K问题

&#x1f4f7; 江池俊&#xff1a; 个人主页 &#x1f525;个人专栏&#xff1a; ✅数据结构冒险记 ✅C语言进阶之路 &#x1f305; 有航道的人&#xff0c;再渺小也不会迷途。 文章目录 前言一、堆排序1.1 排序思想1.2 堆排序过程&#xff08;图解&#xff09;1.3 堆排序代…

C++ 数论相关题目(欧拉函数、筛法求欧拉函数)

1、欧拉函数 给定 n 个正整数 ai &#xff0c;请你求出每个数的欧拉函数。 欧拉函数的定义 1∼N 中与 N 互质的数的个数被称为欧拉函数&#xff0c;记为 ϕ(N) 。 若在算数基本定理中&#xff0c;Npa11pa22…pamm &#xff0c;则&#xff1a; ϕ(N) Np1−1p1p2−1p2…pm−1p…

【数学建模】插值与拟合

文章目录 插值插值方法用Python解决插值问题 拟合最小二乘拟合数据拟合的Python实现 适用情况 处理由试验、测量得到的大量数据或一些过于复杂而不便于计算的函数表达式时&#xff0c;构造一个简单函数作为要考察数据或复杂函数的近似 定义 给定一组数据&#xff0c;需要确定满…

b+树的理解

二叉树&#xff1a; 每个节点支持两个分支的树结构&#xff0c;相比于单向链表&#xff0c;多了一个分支。 二叉查找树&#xff1a; 在二叉树的基础上增加了一个规则&#xff0c;左子树的所有节点都小于它的根节点&#xff0c;右子树的所有节点都大于他的根节点。 二叉查找树…

Flutter中实现中国省份地图

效果展示(这里只展示局部&#xff0c;完全展示违规)&#xff1a; 可以点击省份改变颜色&#xff0c;更多功能可以自行拓展。 注&#xff1a;非完整中国地图&#xff01;&#xff01;&#xff01; 本文用于记录在Flutter项目中安卓端实现中国地图&#xff0c;因为实现过程是通过…

分类预测 | Matlab实现GRU-Attention-Adaboost基于门控循环单元融合注意力机制的Adaboost数据分类预测/故障识别

分类预测 | Matlab实现GRU-Attention-Adaboost基于门控循环单元融合注意力机制的Adaboost数据分类预测/故障识别 目录 分类预测 | Matlab实现GRU-Attention-Adaboost基于门控循环单元融合注意力机制的Adaboost数据分类预测/故障识别分类效果基本描述程序设计参考资料 分类效果 …

【Linux C | 进程】Linux 进程间通信的10种方式(2)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

手写一个图形验证码

文章目录 需求分析 需求 使用 JS 写一个验证码&#xff0c;并在前端进行校验 分析 新建文件 VueImageVerify.vue <template><div class"img-verify"><canvas ref"verify" :width"state.width" :height"state.height&qu…

OpenCV-Python(51):基于Haar特征分类器的面部检测

目标 学习了解Haar 特征分类器为基础的面部检测技术将面部检测扩展到眼部检测等。 基础 以Haar 特征分类器为基础的对象检测技术是一种非常有效的对象检测技术(2001 年Paul_Viola 和Michael_Jones 提出)。它是基于机器学习的,通过使用大量的正负样本图像训练得到一个cascade_…

socket以及字节序

1. socket 介绍&#xff1a; 简介&#xff1a; 所谓 socket&#xff08; 套接字&#xff09;&#xff0c;就是对网络中不同主机上的应用进程之间进行双向通信的 端点的抽象。 一个套接字就是网络上进程通信的一端&#xff0c;提供了应用层进程利用网络协议交换数据的机制。从所…

推荐一个还可以的windows ssh工具

1.下载 https://github.com/kingToolbox/WindTerm/releases 2.解压 3.使用 上传 下载都很快 比cmd窗口好用 当然和finalshell有点像

Linux编辑器vim(含vim的配置)

文章目录 前言vim的基本概念vim基本操作进入vim模式切换退出vim vim指令vim命令模式指令vim底行模式命令 简单vim配置 前言 本篇文章&#xff0c;小编将介绍Linux编辑器–>vim以及vim的配置。 vim的基本概念 正常/普通/命令模式(Normal mode) 控制屏幕光标的移动&#xf…