算法题: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 …...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
