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

Day29- 贪心算法part03

一、K 次取反后最大化的数组和 

题目一:1005. K 次取反后最大化的数组和

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

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

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

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

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

问题的关键在于优先反转数组中的负数,因为这样可以增加数组的总和。

如果数组中的负数少于 K,剩余的操作应该用于反转最小的正数(如果有的话),并且要注意,如果剩余操作次数是偶数,最终结果不会改变;如果是奇数,则最终结果会减少两倍的最小元素的值。

/** @lc app=leetcode.cn id=1005 lang=cpp** [1005] K 次取反后最大化的数组和*/// @lc code=start
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {std::sort(nums.begin(), nums.end());for (int i = 0; i < nums.size() && k > 0; ++i) {if (nums[i] < 0) {nums[i] = -nums[i];--k;}}if (k % 2 == 1) {std::sort(nums.begin(), nums.end());nums[0] = -nums[0];}int sum = 0;for (int num : nums) {sum += num;}return sum;}
};
// @lc code=end

二、加油站

题目一:134. 加油站 

134. 加油站

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

如果一个车从加油站 A 出发,无法到达加油站 B,那么 A 和 B 之间的任何一个加油站都不能作为起始点到达加油站 B。

/** @lc app=leetcode.cn id=134 lang=cpp** [134] 加油站*/// @lc code=start
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int totalTank = 0, currTank = 0, startingStation = 0;for (int i = 0; i < gas.size(); ++i) {totalTank += gas[i] - cost[i];currTank += gas[i] - cost[i];if (currTank < 0) {startingStation = i + 1;currTank = 0;}}return totalTank >= 0 ? startingStation : -1;}
};
// @lc code=end

三、分发糖果

题目一:135. 分发糖果 

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。

首先,需要给每个孩子至少一颗糖果。

然后,首先从左向右遍历,确保每个孩子如果比他左边的孩子评分高,则获得更多的糖果;其次,从右向左遍历,确保每个孩子如果比他右边的孩子评分高,则也获得更多的糖果

/** @lc app=leetcode.cn id=135 lang=cpp** [135] 分发糖果*/// @lc code=start
class Solution {
public:int candy(vector<int>& ratings) {int size = ratings.size();if (size < 2) {return size;}vector<int> candies(size, 1);  for (int i = 1; i < size; ++i) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}for (int i = size - 2; i >= 0; --i) {if (ratings[i] > ratings[i + 1]) {candies[i] = std::max(candies[i], candies[i + 1] + 1);}}return accumulate(candies.begin(), candies.end(), 0);}
};
// @lc code=end

相关文章:

Day29- 贪心算法part03

一、K 次取反后最大化的数组和 题目一&#xff1a;1005. K 次取反后最大化的数组和 1005. K 次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k &#xff0c;按以下方法修改该数组&#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰…...

RPA与ChatGPT的融合:智能化流程的未来

RPA&#xff08;Robotic Process Automation&#xff09;是一种利用软件机器人模拟人类操作的技术&#xff0c;可以实现对各种业务流程的自动化执行。ChatGPT是一种基于深度学习的自然语言生成模型&#xff0c;可以根据给定的上下文生成流畅、连贯、有逻辑的文本。RPA与ChatGPT…...

Ubuntu安装maven并且配置阿里源

ubuntu环境搭建专栏&#x1f517;点击跳转 Ubuntu系统环境搭建&#xff08;十二&#xff09;——Ubuntu安装maven并且配置阿里源 文章目录 Ubuntu系统环境搭建&#xff08;十二&#xff09;——Ubuntu安装maven并且配置阿里源1.安装maven1.1更新源列表1.2安装1.3验证 2.配置阿…...

如何通过idea使用JDK8.0创建Spring项目

目前 IDEA 进行了优化&#xff0c;所以我们在创建 Spring 项目时会发现&#xff0c;以及不能选择通过 JDK8.0 创建了&#xff0c;这是因为官方已经不再提供 JDK8.0 创建 Spring 项目&#xff0c;我们可以通过修改创建 Spring 项目的路径来解决该问题 在创建 Spring 项目的页面&…...

Spark读取kafka(流式和批数据)

spark读取kafka&#xff08;批数据处理&#xff09; # 按照偏移量读取kafka数据 from pyspark.sql import SparkSessionss SparkSession.builder.getOrCreate()# spark读取kafka options {# 写kafka配置信息# 指定kafka的连接的broker服务节点信息kafka.bootstrap.servers: n…...

经典目标检测YOLO系列(二)YOLOV2的复现(1)总体网络架构及前向推理过程

经典目标检测YOLO系列(二)YOLOV2的复现(1)总体网络架构及前向推理过程 和之前实现的YOLOv1一样&#xff0c;根据《YOLO目标检测》(ISBN:9787115627094)一书&#xff0c;在不脱离YOLOv2的大部分核心理念的前提下&#xff0c;重构一款较新的YOLOv2检测器&#xff0c;来对YOLOV2有…...

怎样使用崭新的硬盘

新买的一块硬盘&#xff0c;接到电脑上&#xff0c;打开机器&#xff0c;却找不到新的硬盘&#xff0c;怎么回事&#xff1f;新的硬盘是坏的么&#xff1f;怎样才能把新硬盘用起来&#xff1f; 可能有几种原因导致您的电脑无法识别新的硬盘。以下是一些建议的解决方法&#xff…...

Kafka-多线程消费及分区设置

目录 一、Kafka是什么&#xff1f;消息系统&#xff1a;Publish/subscribe&#xff08;发布/订阅者&#xff09;模式相关术语 二、初步使用1.yml文件配置2.生产者类3.消费者类4.发送消息 三、减少分区数量1.停止业务服务进程2.停止kafka服务进程3.重新启动kafka服务4.重新启动业…...

计算机导论06-人机交互

文章目录 人机交互基础人机交互概述人机交互及其发展人机交互方式人机界面 新型人机交互技术显示屏技术跟踪与识别&#xff08;技术&#xff09;脑-机接口 多媒体技术多媒体技术基础多媒体的概念多媒体技术及其特性多媒体技术的应用多媒体技术发展趋势 多媒体应用技术文字&…...

hot100:07接雨水

题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 算法思想&#xff1a; 这里采取的是暴力解法和双指针的解法&#xff0c;但是这个题目还有其他的两种解法&#xff08;单调栈和动态规划&#xff0c;同学可以自行了解&#xff…...

Docker安装MySQL教程分享(附MySQL基础入门教程)

docker安装MySQL Docker可以通过以下命令来安装MySQL容器&#xff1a; 首先确保已经在计算机上安装了Docker。如果没有安装&#xff0c;请根据操作系统的不同进行相应的安装。 打开终端或命令提示符&#xff0c;并运行以下命令拉取最新版本的MySQL镜像&#xff1a; docker pu…...

麒麟V10挂载iso,配置yum源

本文介绍yum 如何挂载本地镜像源 1) 拷贝镜像到本地 2) 执行以下命令&#xff1a; # mount -o loop 镜像路径及镜像名字 /mnt&#xff08;或 media&#xff09; 挂载前 挂载后 3) 进入/etc/yum.repos.d&#xff08;yum.repos.d 是一个目录&#xff0c;该目录是分析 RPM 软件…...

《Linux C编程实战》笔记:信号的捕捉和处理

Linux系统中对信号的处理主要由signal和sigaction函数来完成&#xff0c;另外还会介绍一个函数pause&#xff0c;它可以用来响应任何信号&#xff0c;不过不做任何处理 signal函数 #include <signal.h> void (*signal(int signum, void (*handler)(int)))(int);可以分解…...

python算法与数据结构---单调栈与实践

单调栈 单调栈是一个栈&#xff0c;里面的元素的大小按照它们所在栈的位置&#xff0c;满足一定的单调性&#xff1b; 性质&#xff1a; 单调递减栈能找到左边第一个比当前元素大的元素&#xff1b;单调递增栈能找到左边第一个比当前元素小的元素&#xff1b; 应用场景 一般用…...

文心一言使用分享

ChatGPT 和文心一言哪个更好用&#xff1f; 一个直接可以用&#xff0c;一个还需要借助一些工具&#xff0c;还有可能账号会消失…… 没有可比性。 通用大模型用于特定功能的时候需要一些引导技巧。 import math import time def calculate_coordinate(c, d, e, f, g, h,…...

【C++干货铺】C++11新特性——lambda表达式 | 包装器

个人主页点击直达&#xff1a;小白不是程序媛 C系列专栏&#xff1a;C干货铺 代码仓库&#xff1a;Gitee 目录 C98中的排序 lambda表达式 lambda表达式语法 表达式中的各部分说明 lambda表达式的使用 基本的使用 [var]值传递捕捉变量var ​编辑 [&var]引用传递捕…...

在 EggJS 中实现 Redis 上锁

配置环境 下载 Redis Windows 访问 https://github.com/microsoftarchive/redis/releases 选择版本进行下载 - 勾选 [配置到环境变量] - 无脑下一步并安装 命令行执行&#xff1a;redis-cli -v 查看已安装的 Redis 版本&#xff0c;能成功查看就表示安装成功啦~ Mac brew i…...

Unity-场景

创建场景 创建新的场景后&#xff1a; 文件 -> 生成设置 -> Build中的场景 -> 将项目中需要使用的场景拖进去 SceneTest public class SceneTest : MonoBehaviour {// Start is called before the first frame updatevoid Start(){// 两个类&#xff1a; 场景类、场…...

MATLAB R2023b for Mac 中文

MATLAB R2023b 是 MathWorks 发布的最新版本的 MATLAB&#xff0c;适用于进行算法开发、数据可视化、数据分析以及数值计算等任务的工程师和科学家。它包含了一系列新增功能和改进&#xff0c;如改进了数据导入工具&#xff0c;增加了对数据帧和表格对象的支持&#xff0c;增强…...

01 MyBatisPlus快速入门

1. MyBatis-Plus快速入门 版本 3.5.31并非另起炉灶 , 而是MyBatis的增强 , 使用之前依然要导入MyBatis的依赖 , 且之前MyBatis的所有功能依然可以使用.局限性是仅限于单表操作, 对于多表仍需要手写 项目结构&#xff1a; 先导入依赖&#xff0c;比之前多了一个mybatis-plus…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...