算法题: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] <= 1001 <= k <= 10^4
相关文章:
算法题:K 次取反后最大化的数组和(典型的贪心算法问题)
这道题没有看题解,直接提交,成绩超越99.5%,说明思路是优的。就是考虑的情况里面弯弯绕比较多,需要考虑全面一点。(本题完整题目附在了最后面) 具体思路如下: 1、首先排序,然后从最…...
Go语言中向[]byte数组中增加一个元素
要向http.Request的body中添加一个键值对,可以先将其转换为一个map,然后对其进行修改,最后再将其转回为byte数组。 以下是一个示例代码: import ("net/http""io/ioutil""encoding/json" )type Re…...
CSS 布局案例: 2行、多行每行格数不定,最后一列对齐
布局期望的效果如下: 第二行最后一格与第一行最后一格对齐。每行格数不定。自动拉伸填充整个宽度 实现: 一开始打算用display:flex, 自动分散,但是第二行对齐第一行最后一格控制不了。 使用grid fr均分单位控制。 <!DOCTYPE…...
数据结构--算法、数据结构的基本概念
📕参考:王道 一、算法的基本概念 1.程序数据结构算法 2.算法的特性 (1)有穷性 执行有穷步之后结束,且每一步都可在有穷时间内完成。 (2)确定性 (3)可行性 可通过已经实…...
Edge浏览器下载文件被保存为 .crdownload 文件的问题小记
问题 近期使用Edge浏览器下载文件时,文件都被保存为 .crdownload 格式的文件了,不确定从哪个版本开始的。除非下载未完成导致文件不完整,否则不会被保存为 .crdownload 格式的文件;实际上文件已完成了下载,且手工修改…...
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.温度传感器 (1)测温度的方式:物理(汞柱,气压),电子(金属电性能随温度变化) (2)早期:热敏电阻(模…...
力扣 -- 5. 最长回文子串
解题步骤: 参考代码: 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.概述 消息推送在日常使用中的场景比较多,比如有人点赞了我的博客或者关注了我,这时我就会收到一条推送消息,以此来吸引我点击或者打开应用。消息推送的方式主要分为两种:web消息推送和移动端消息推送。它将所要发送的信息&…...
Vue、React和小程序中的组件通信:父传子和子传父
在前端开发中,组件化是一种常见的开发模式,它可以将复杂的用户界面拆分成多个可重用的组件。在Vue、React和小程序中,组件之间的数据和事件传递是非常关键的,其中父传子和子传父是常见的通信方式。本文将介绍在Vue、React和小程序…...
安卓玩机----展讯芯片机型解锁 读写分区工具 操作步骤解析
国内机型大都使用高通和MTK芯片。展讯芯片使用的较少。相对来说高通和mtk机型解锁以及读取分区工具较多。展讯的几乎没有。目前有大佬开发出了一款展讯芯片解锁 与读写分区工具.开源的tools 官方分享说明: 是一款专为 Windows 计算机设计的免费、用户友好的工具&am…...
微软放大招!Bing支持DALL-E3,免费AI绘画等你来体验!
最近 OpenAI 发布了DALL-E3模型,出图效果和Midjourney不相上下,不过要使用它有些门槛,必须是 ChatGPT Plus 账户,而且还要排队,怎么等都等不到,搞得大家都比较焦虑。 不过现在微软在Bing上也支持 DALL-E3 …...
tp5访问的时候必须加index.php,TP5配置隐藏入口index.php文件
PS:这里说的入口文件指的是public/index.php,配置文件就在这个目录下 可以去掉URL地址里面的入口文件index.php,但是需要额外配置WEB服务器的重写规则。 以Apache为例,需要在入口文件的同级添加.htaccess文件(官方默认自带了该文件)&#x…...
16k面试中的10个问题
你好,我是田哥 节前,有位朋友跟我反馈面试中一些问题,这位朋友的基本情况: 坐标:上海,年限:3年不到,期望薪资;16k 下面我们来看看具体问题: 01:请…...
STM32单片机入门学习(六)-光敏传感器控制LED
光敏传感器模块和LED接线 LED负极接B12,正极接VCC 光敏传感模块一DO端接B13,GND接GND,VCC接VCC,AO不接。 如图: 主程序代码: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…...
大数据学习,涉及哪些技术?
学习大数据需要涉及多种技术和概念,因为大数据领域非常广泛,涵盖了数据的采集、存储、处理、分析和可视化等多个方面。以下是学习大数据时需要考虑的一些关键技术和概念: 1、数据采集和存储: 数据库管理系统(DBMS&am…...
Clion中使用C/C++开发stm32程序
前言 从刚开始学习阶段,一直是用的keil5开发stm32程序,自从看到稚晖君推荐的CLion开发嵌入式程序后,这次尝试在CLion上开发stm32程序。 1、配置CLion用于STM32开发的环境 这里我就不详细写了,没必要重新写,网上教程很多…...
JavaScript Web APIs第五天笔记
Web APIs - 第5天笔记 目标: 能够利用JS操作浏览器,具备利用本地存储实现学生就业表的能力 BOM操作综合案例 js组成 JavaScript的组成 ECMAScript: 规定了js基础语法核心知识。比如:变量、分支语句、循环语句、对象等等 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 …...
手把手教你搭建基于Matlab/Simulink的插电式混合动力汽车4驱PHEV模型
基于Matlab/simulink的插电式混合动力汽车建模仿真模型4驱PHEV(比亚迪唐DM混动系统P2P4发动机——三擎四驱),包括整车HCU控制单元、发动机模型、驱动电机模型、ISG电机模型、AMT5档自动变速箱模型、驾驶员模型、电池能量管理控制模型等&#…...
石家庄整家定制哪个好
在石家庄,寻找合适的整家定制服务,是许多家庭打造理想居住空间的重要一步。今天,我们想为您介绍一个专注于中高端整家定制的品牌——MJ.HOME美境美家木作。关于美境美家木作美境美家木作是一个集整案设计施工与定制家居于一体的品牌。他们致力…...
用Verilog在FPGA上实现一个真实的十字路口红绿灯(附完整代码与仿真)
从零构建FPGA十字路口交通灯控制系统:Verilog实战指南 十字路口交通灯控制是数字逻辑设计的经典案例,也是FPGA初学者从理论迈向实践的重要一步。本文将带你完整实现一个基于Xilinx Basys3开发板的交通灯控制系统,涵盖状态机设计、时序约束、仿…...
开源工具Lenovo Legion Toolkit:游戏本性能管理的轻量化创新方案
开源工具Lenovo Legion Toolkit:游戏本性能管理的轻量化创新方案 【免费下载链接】LenovoLegionToolkit Lightweight Lenovo Vantage and Hotkeys replacement for Lenovo Legion laptops. 项目地址: https://gitcode.com/gh_mirrors/le/LenovoLegionToolkit …...
十字头零件的机械加工工艺规程及工装夹具设计 (论文+CAD图纸+任务书+过程卡+工序卡+外文翻译+参考文献……)
十字头零件作为机械传动系统中的关键构件,其加工精度直接影响设备运行的稳定性与寿命。制定科学合理的机械加工工艺规程及配套工装夹具设计方案,是确保零件质量、提升加工效率的核心环节。工艺规程需系统规划从毛坯准备到成品检验的全流程,涵…...
BURSTER 8645-5005 扭矩传感器
BURSTER 8645-5005(德国波斯特)是一款非接触式、磁致伸缩原理、高精度动态旋转扭矩传感器,量程 5 N・m,内置放大器,专为连续旋转工况下的动态扭矩测量设计一、型号与量程型号:BURSTER 8645-5005系列&#x…...
数值分析实战指南:北航研究生大作业解析与代码实现
1. 数值分析大作业的核心价值 第一次接触北航研究生数值分析大作业时,我和大多数同学一样感到无从下手。直到在实验室熬了三个通宵后,我才真正明白这份作业的独特价值——它完美架起了理论与实践的桥梁。这份大作业最精妙之处在于,它不仅仅是…...
轻量级嵌入式按键驱动库:BartOS-button设计与多平台实践
1. BartOS-button 库概述BartOS-button 是为 BartOS 嵌入式实时操作系统项目配套开发的轻量级按键驱动库,专为资源受限的 IoT 终端设备设计。该库不依赖特定硬件抽象层(HAL),采用纯 C 实现,支持裸机(Bare-m…...
SigmaStar SSD21X系列芯片:智能家居与工业控制的多场景显示解决方案
1. SigmaStar SSD21X系列芯片:智能家居与工业控制的显示利器 第一次接触SigmaStar SSD21X系列芯片是在一个智能门锁项目上。当时客户要求低成本实现高清彩色触控屏,还要支持人脸识别和远程控制。测试了几款方案后,SSD210的表现让我印象深刻—…...
基于STM32F103C8与CAN总线的步科步进电机PDO映射实战解析
1. STM32F103C8与步科步进电机的基础连接 第一次接触CAN总线控制步进电机时,最让我头疼的就是硬件连接部分。STM32F103C8的CAN接口引脚是固定的PA11(CAN_RX)和PA12(CAN_TX),而步科驱动器的CAN接口通常标注为CANH和CANL。这里有个容易踩坑的地方ÿ…...
