当前位置: 首页 > news >正文

算法题:K 次取反后最大化的数组和(典型的贪心算法问题)

这道题没有看题解,直接提交,成绩超越99.5%,说明思路是优的。就是考虑的情况里面弯弯绕比较多,需要考虑全面一点。(本题完整题目附在了最后面)

具体思路如下:

1、首先排序,然后从最小的负数开始一一变为正数,如果遍历到正数了,而k的次数没用完,如果剩余的k是偶数次,则直接可以退出了;如果k是奇数次且nums内有0元素也可以直接退出程序;如果k是奇数次且nums里面没有0元素,则挑一个最小的正数,将其置为负数,其实也就是比较正在遍历到的数和前一个数的大小,小的那个就是nums数组里的最小正数。

2、还有一种情况就是,数组已经遍历完了,k没用完,这个也很简单,直接对数组的最后一个数,也就是数组里面最小非负数进行操作,如果其为0则直接退出,如果是k是偶数也可直接退出,如果k是奇数则将这个数置为负数。

3、最后对nums数组求和。

代码如下:

class Solution(object):def largestSumAfterKNegations(self, nums, k):nums.sort()for i in range(len(nums)):if k <= 0: breakif nums[i] < 0:nums[i] = 0 - nums[i]k -= 1elif nums[i] == 0:k = 0breakelse:# 这里的 k & 1 是判断k是否为奇数的快速判断方法if nums[i] > nums[i - 1] and k & 1:  nums[i - 1] = 0 - nums[i - 1]elif nums[i] <= nums[i - 1] and k & 1:nums[i] = 0 - nums[i]k = 0breakif k > 0 and k & 1:nums[-1] = 0 - nums[-1]return sum(nums)if __name__ == '__main__':sol = Solution()# print(sol.largestSumAfterKNegations([2, -3, -1, 5, -4], 2))print(sol.largestSumAfterKNegations([-4, -2, -3], 4))

完整题目:

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

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

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

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

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

示例 1:

输入:nums = [4,2,3], k = 1
输出:5
解释:选择下标 1 ,nums 变为 [4,-2,3] 。

示例 2:

输入:nums = [3,-1,0,2], k = 3
输出:6
解释:选择下标 (1, 2, 2) ,nums 变为 [3,1,0,2] 。

示例 3:

输入:nums = [2,-3,-1,5,-4], k = 2
输出:13
解释:选择下标 (1, 4) ,nums 变为 [2,3,-1,5,4] 。

提示:

  • 1 <= nums.length <= 10^4
  • -100 <= nums[i] <= 100
  • 1 <= k <= 10^4

相关文章:

算法题:K 次取反后最大化的数组和(典型的贪心算法问题)

这道题没有看题解&#xff0c;直接提交&#xff0c;成绩超越99.5%&#xff0c;说明思路是优的。就是考虑的情况里面弯弯绕比较多&#xff0c;需要考虑全面一点。&#xff08;本题完整题目附在了最后面&#xff09; 具体思路如下&#xff1a; 1、首先排序&#xff0c;然后从最…...

Go语言中向[]byte数组中增加一个元素

要向http.Request的body中添加一个键值对&#xff0c;可以先将其转换为一个map&#xff0c;然后对其进行修改&#xff0c;最后再将其转回为byte数组。 以下是一个示例代码&#xff1a; import ("net/http""io/ioutil""encoding/json" )type Re…...

CSS 布局案例: 2行、多行每行格数不定,最后一列对齐

布局期望的效果如下&#xff1a; 第二行最后一格与第一行最后一格对齐。每行格数不定。自动拉伸填充整个宽度 实现&#xff1a; 一开始打算用display:flex&#xff0c; 自动分散&#xff0c;但是第二行对齐第一行最后一格控制不了。 使用grid fr均分单位控制。 <!DOCTYPE…...

数据结构--算法、数据结构的基本概念

&#x1f4d5;参考&#xff1a;王道 一、算法的基本概念 1.程序数据结构算法 2.算法的特性 &#xff08;1&#xff09;有穷性 执行有穷步之后结束&#xff0c;且每一步都可在有穷时间内完成。 &#xff08;2&#xff09;确定性 &#xff08;3&#xff09;可行性 可通过已经实…...

Edge浏览器下载文件被保存为 .crdownload 文件的问题小记

问题 近期使用Edge浏览器下载文件时&#xff0c;文件都被保存为 .crdownload 格式的文件了&#xff0c;不确定从哪个版本开始的。除非下载未完成导致文件不完整&#xff0c;否则不会被保存为 .crdownload 格式的文件&#xff1b;实际上文件已完成了下载&#xff0c;且手工修改…...

6-10 单链表分段逆转 分数 15

void K_Reverse( List L, int K ) { //此题已经默认size > K 因为当size < K时 反转后将不再符合链表的定义//求出表中元素个数int size 0;for (List cur L->Next; cur ! NULL; cur cur->Next)size; List prv, cur, next, first, head L;//共需要反转 si…...

【单片机】17-温度传感器DS18B20

1.DS18B20相关背景知识 1.温度传感器 &#xff08;1&#xff09;测温度的方式&#xff1a;物理&#xff08;汞柱&#xff0c;气压&#xff09;&#xff0c;电子&#xff08;金属电性能随温度变化&#xff09; &#xff08;2&#xff09;早期&#xff1a;热敏电阻&#xff08;模…...

力扣 -- 5. 最长回文子串

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:string longestPalindrome(string s) {int ns.size();vector<vector<bool>> dp(n,vector<bool>(n));//最长回文串的起始位置int start0;//最长回文串的长度int len0;for(int in-1;i>…...

SpringCloud源码探析(十)-Web消息推送

1.概述 消息推送在日常使用中的场景比较多&#xff0c;比如有人点赞了我的博客或者关注了我&#xff0c;这时我就会收到一条推送消息&#xff0c;以此来吸引我点击或者打开应用。消息推送的方式主要分为两种&#xff1a;web消息推送和移动端消息推送。它将所要发送的信息&…...

Vue、React和小程序中的组件通信:父传子和子传父

在前端开发中&#xff0c;组件化是一种常见的开发模式&#xff0c;它可以将复杂的用户界面拆分成多个可重用的组件。在Vue、React和小程序中&#xff0c;组件之间的数据和事件传递是非常关键的&#xff0c;其中父传子和子传父是常见的通信方式。本文将介绍在Vue、React和小程序…...

安卓玩机----展讯芯片机型解锁 读写分区工具 操作步骤解析

国内机型大都使用高通和MTK芯片。展讯芯片使用的较少。相对来说高通和mtk机型解锁以及读取分区工具较多。展讯的几乎没有。目前有大佬开发出了一款展讯芯片解锁 与读写分区工具.开源的tools 官方分享说明&#xff1a; 是一款专为 Windows 计算机设计的免费、用户友好的工具&am…...

微软放大招!Bing支持DALL-E3,免费AI绘画等你来体验!

最近 OpenAI 发布了DALL-E3模型&#xff0c;出图效果和Midjourney不相上下&#xff0c;不过要使用它有些门槛&#xff0c;必须是 ChatGPT Plus 账户&#xff0c;而且还要排队&#xff0c;怎么等都等不到&#xff0c;搞得大家都比较焦虑。 不过现在微软在Bing上也支持 DALL-E3 …...

tp5访问的时候必须加index.php,TP5配置隐藏入口index.php文件

PS&#xff1a;这里说的入口文件指的是public/index.php,配置文件就在这个目录下 可以去掉URL地址里面的入口文件index.php&#xff0c;但是需要额外配置WEB服务器的重写规则。 以Apache为例&#xff0c;需要在入口文件的同级添加.htaccess文件(官方默认自带了该文件)&#x…...

16k面试中的10个问题

你好&#xff0c;我是田哥 节前&#xff0c;有位朋友跟我反馈面试中一些问题&#xff0c;这位朋友的基本情况&#xff1a; 坐标&#xff1a;上海&#xff0c;年限&#xff1a;3年不到&#xff0c;期望薪资&#xff1b;16k 下面我们来看看具体问题&#xff1a; 01&#xff1a;请…...

STM32单片机入门学习(六)-光敏传感器控制LED

光敏传感器模块和LED接线 LED负极接B12,正极接VCC 光敏传感模块一DO端接B13,GND接GND&#xff0c;VCC接VCC,AO不接。 如图&#xff1a; 主程序代码&#xff1a;main.c #include "stm32f10x.h" #include "Delay.h" //delay函数所在头文件 #include …...

MFC 鼠标悬停提示框

MFC 鼠标悬停提示框 运行效果 在MFC窗口中添加一个控件 工具栏中拖拽List Box到MFC窗口给List Box添加变量 CListBox m_listbox 增加成员变量 CWnd* m_tip_parent_wnd; CToolTipCtrl m_tip;给m_listbox创建提示框 void create_tip_window(CWnd* tip_wnd, CToolTipCtrl* ti…...

大数据学习,涉及哪些技术?

学习大数据需要涉及多种技术和概念&#xff0c;因为大数据领域非常广泛&#xff0c;涵盖了数据的采集、存储、处理、分析和可视化等多个方面。以下是学习大数据时需要考虑的一些关键技术和概念&#xff1a; 1、数据采集和存储&#xff1a; 数据库管理系统&#xff08;DBMS&am…...

Clion中使用C/C++开发stm32程序

前言 从刚开始学习阶段&#xff0c;一直是用的keil5开发stm32程序&#xff0c;自从看到稚晖君推荐的CLion开发嵌入式程序后&#xff0c;这次尝试在CLion上开发stm32程序。 1、配置CLion用于STM32开发的环境 这里我就不详细写了&#xff0c;没必要重新写&#xff0c;网上教程很多…...

JavaScript Web APIs第五天笔记

Web APIs - 第5天笔记 目标&#xff1a; 能够利用JS操作浏览器,具备利用本地存储实现学生就业表的能力 BOM操作综合案例 js组成 JavaScript的组成 ECMAScript: 规定了js基础语法核心知识。比如&#xff1a;变量、分支语句、循环语句、对象等等 Web APIs : DOM 文档对象模型&…...

[ICCV-23] Paper List - 3D Generation-related

ICCV-23 paper list 目录 Oral Papers 3D from multi-view and sensors Generative AI Poster Papers 3D Generation (Neural generative models) 3D from a single image and shape-from-x 3D Editing Face and gestures Stylization Dataset Oral Papers 3D from …...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...