代码随想录算法训练营第三十四天-贪心算法3| 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果
1005. Maximize Sum Of Array After K Negations
参考视频:贪心算法,这不就是常识?还能叫贪心?LeetCode:1005.K次取反后最大化的数组和_哔哩哔哩_bilibili
贪心🔍
的思路,局部最优:让绝对值大的负数变为正数,当前数值达到最大,整体最优:整个数组和达到最大。
局部最优可以推出全局最优。
那么如果将负数都转变为正数了,K依然大于0,此时的问题是一个有序正整数序列,如何转变K次正负,让 数组和 达到最大。
那么又是一个贪心:局部最优:只找数值最小的正整数进行反转,当前数值和可以达到最大(例如正整数数组{5, 3, 1},反转1 得到-1 比 反转5得到的-5 大多了),全局最优:整个 数组和 达到最大。
虽然这道题目大家做的时候,可能都不会去想什么贪心算法,一鼓作气,就AC了。
我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路,这么一道简单题,就用了两次贪心!
那么本题的解题步骤为:
第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
第二步:从前向后遍历,遇到负数将其变为正数,同时K--
第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
第四步:求和
public class Leetcode1005 {public static int largestSumAfterKNegations(int[] nums, int k) {sort(nums);for (int i = 0; i < nums.length; i++) {if (k > 0 && nums[i] < 0) {nums[i] *= -1;k--;}}if (k % 2 == 1) nums[nums.length - 1] *= -1;int res = 0;for (int num : nums) {res += num;}return res;}public static void sort(int[] nums) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (Math.abs(nums[i]) < Math.abs(nums[j])) {int temp = nums[j];nums[j] = nums[i];nums[i] = temp;}}}}
}
134. 加油站
解题思路:
可以换一个思路,首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈,说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。
public class Leetcode134 {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i < gas.length; i++) {curSum += (gas[i] - cost[i]);totalSum += (gas[i] - cost[i]);if (curSum < 0) {start = i + 1;curSum = 0;}}if (totalSum < 0) return -1;return start;}
}
135. 分发糖果
public class Leetcode135 {public static int candy(int[] ratings) {int[] candy = new int[ratings.length];Arrays.fill(candy, 1);for (int i = 1; i < ratings.length; i++) {if (ratings[i] > ratings[i - 1]) {candy[i] = candy[i - 1] + 1;}}System.out.println(Arrays.toString(candy));for (int i = ratings.length - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candy[i] = Math.max(candy[i + 1] + 1, candy[i]);}}System.out.println(Arrays.toString(candy));int res = 0;for (int i : candy) {res += i;}return res;}
}
相关文章:
代码随想录算法训练营第三十四天-贪心算法3| 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果
1005. Maximize Sum Of Array After K Negations 参考视频:贪心算法,这不就是常识?还能叫贪心?LeetCode:1005.K次取反后最大化的数组和_哔哩哔哩_bilibili 贪心🔍 的思路,局部最优ÿ…...
比较系统的学习 pandas (2)
pandas 数据读取与输出方法和常用参数 1、读取 CSV文件 pd.read_csv("pathname",step,encoding"gbk",header"infer",name[],skip_blank_linesTrue,commentNone) path : 文件路径 step : 指定分隔符,默认为 逗号 enco…...
怎么查看电脑主板最大支持多少内存?
很多电脑,内存不够用,但应速度慢;还有一些就是买了很大的内存条,但是还是反应慢;这是为什么呢?我今天明白了,原来每个电脑都有自己的适配内存,就是每个电脑能支持多大的内存…...
数据结构——线段树
线段树的结构 线段树是一棵二叉树,其结点是一条“线段”——[a,b],它的左儿子和右儿子分别是这条线段的左半段和右半段,即[a, (ab)/2 ]和[(ab)/2 ,b]。线段树的叶子结点是长度为1的单位线段[a,a1]。下图就是一棵根为[1,10]的线段树࿱…...
【C++进阶】实现C++线程池
文章目录1. thread_pool.h2. main.cpp1. thread_pool.h #pragma once #include <iostream> #include <vector> #include <queue> #include <thread> #include <mutex> #include <condition_variable> #include <future> #include &…...
Redis常用五种数据类型
一、Redis String字符串 1.简介 String类型在redis中最常见的一种类型 string类型是二制安全的,可以存放字符串、数值、json、图像数据 value存储最大数据量是512M 2. 常用命令 set < key>< value>:添加键值对 nx:当数据库中…...
C++ Primer第五版_第十一章习题答案(1~10)
文章目录练习11.1练习11.2练习11.3练习11.4练习11.5练习11.6练习11.7练习11.8练习11.9练习11.10练习11.1 描述map 和 vector 的不同。 map 是关联容器, vector 是顺序容器。 练习11.2 分别给出最适合使用 list、vector、deque、map以及set的例子。 list:…...
GEE:使用LandTrendr进行森林变化检测详解
作者:_养乐多_ 本文介绍了一段用于地表变化监测的代码,该代码主要使用谷歌地球引擎(GEE)中的 Landsat 时间序列数据,采用了 Kennedy 等人(2010) 发布的 LandTrendr 算法,对植被指数进行分割,通过计算不同时间段内植被指数的变化来检测植被变化。 目录 一、加入矢量边界 …...
docker项目实施
鲲鹏916架构openEuler-arm64成功安装docker并跑通tomcat容器_闭关苦炼内功的技术博客_51CTO博客鲲鹏916架构openEuler-arm64成功安装docker并跑通tomcat容器,本文是基于之前这篇文章鲲鹏920架构arm64版本centos7安装docker下面开始先来看下系统版本卸载旧版本旧版本…...
springboot实现邮箱验证码功能
引言 邮箱验证码是一个常见的功能,常用于邮箱绑定、修改密码等操作上,这里我演示一下如何使用springboot实现验证码的发送功能; 这里用qq邮箱进行演示,其他都差不多; 准备工作 首先要在设置->账户中开启邮箱POP…...
Java 进阶(5) Java IO流
⼀、File类 概念:代表物理盘符中的⼀个⽂件或者⽂件夹。 常见方法: 方法名 描述 createNewFile() 创建⼀个新文件。 mkdir() 创建⼀个新⽬录。 delete() 删除⽂件或空⽬录。 exists() 判断File对象所对象所代表的对象是否存在。 getAbsolute…...
“终于我从字节离职了...“一个年薪40W的测试工程师的自白...
”我递上了我的辞职信,不是因为公司给的不多,也不是因为公司待我不好,但是我觉得,我每天看中我憔悴的面容,每天晚上拖着疲惫的身体躺在床上,我都不知道人生的意义,是赚钱吗?是为了更…...
设计模式之策略模式(C++)
作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 一、策略模式是什么? 策略模式是一种行为型的软件设计模式,针对某个行为,在不同的应用场景下&…...
从工厂普工到Python女程序员,聊聊这一路我是如何逆袭的?
我来聊聊我是如何从一名工厂普工,到国外程序员的过程,这里面充满了坎坷。过去我的工作是在工厂的流水线上,我负责检测电池的正负极。现如今我每天从早上6:20起床,6点四五十分出发到地铁站,7:40到公司。我会给自己准备一…...
全国青少年信息素养大赛2023年python·选做题模拟二卷
目录 打印真题文章进行做题: 全国青少年电子信息智能创新大赛 python选做题模拟二卷 一、单选题 1. numbers = [1, 11, 111, 9], 运行numbers.sort() 后,运行numbers.reverse() numbers会变成?( )...
分布式事务Seata原理
Seata 是一款开源的分布式事务解决方案,致力于提供高性能与简单易用的分布式事务服务,为用户提供了 AT、TCC、SAGA 和 XA 几种不同的事务模式。Seata AT模式是基于XA事务演进而来,需要数据库支持。AT 模式的特点就是对业务无入侵式࿰…...
用ChatGPT怎么赚钱?普通人用这5个方法也能赚到生活费
ChatGPT在互联网火得一塌糊涂,因为它可以帮很多人解决问题。比如:帮编辑人员写文章,还可以替代程序员写代码,帮策划人员写文案策划等等。ChatGPT这么厉害,能否用它来赚钱呢?今天和大家分享用ChatGPT赚钱的5…...
( “树” 之 DFS) 110. 平衡二叉树 ——【Leetcode每日一题】
110. 平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1: 输入:root [3,9,20,null,null,15,7] …...
nvm软件使用-同一个环境下控制多个不同node版本
1.使用场景 nvm是一个用于管理Node.js版本的工具,它可以让你在同一台机器上安装和切换不同的Node.js版本。使用nvm的好处有以下几点: 1.1.nvm可以让你轻松地测试你的代码在不同的Node.js版本下的兼容性和性能,避免因为版本差异导致的问题。…...
连续两个南航的研究生面试出了从来没出现过的问题,本科和研究生都是计算机专业的,竟然说static是不可更改的。
最近面试人数有点多,面试有点频繁,因此发现了一些学生普遍会发生的错误,可以说是很离谱。 因为做了十多年的面试官,无论是大中小厂的面试,还是社招、校招。 从来没有遇到过这样的情况,而且发生在两个南航…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
