1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

简介: **1005**:通过选择性地将数组元素取反 K 次,使数组和最大化。核心思想是优先将绝对值最大的负数变为正数,若 K 剩余,则对最小的正数反复取反以保持数组和最大。 - **134**:解决环形路径上的加油站问题,判断是否能绕一圈并找到起点。关键在于分析剩余油量的变化趋势,若总油量不足则无法完成,否则从能使最低油量非负的位置出发即可。 - **135**:根据评分分发糖果,确保评分高的孩子获得更多糖果。采用两次遍历策略,先保证右边评分高的孩子获得更多糖果,再调整左边的关系,最终实现全局最优分配。

题目: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 <= 104

-100 <= nums[i] <= 100

1 <= k <= 104

思考历程与知识点:  

本题思路其实比较好想了,如何可以让数组和最大呢?

贪心的思路,局部最优:让绝对值大的负数变为正数,当前数值达到最大,整体最优:整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了,K依然大于0,此时的问题是一个有序正整数序列,如何转变K次正负,让 数组和 达到最大。

那么又是一个贪心:局部最优:只找数值最小的正整数进行反转,当前数值和可以达到最大(例如正整数数组{5, 3, 1},反转1 得到-1 比 反转5得到的-5 大多了),全局最优:整个 数组和 达到最大。

题解:

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};

 题目:134. 加油站

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

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

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

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

输出: 3

解释:

从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油

开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油

开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油

开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油

开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油

开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。

因此,3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]

输出: -1

解释:

你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。

我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油

开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油

开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油

你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。

因此,无论怎样,你都不可能绕环路行驶一周。

提示:

gas.length == n

cost.length == n

1 <= n <= 105

0 <= gas[i], cost[i] <= 104

思考历程与知识点:  

直接从全局进行贪心选择,情况如下:

情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的

情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。

情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。

题解:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX; // 从起点出发,油箱里的油量最小值
        for (int i = 0; i < gas.size(); i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            if (curSum < min) {
                min = curSum;
            }
        }
        if (curSum < 0) return -1;  // 情况1
        if (min >= 0) return 0;     // 情况2
                                    // 情况3
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

 题目:135. 分发糖果

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

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

每个孩子至少分配到 1 个糖果。

相邻两个孩子评分更高的孩子会获得更多的糖果。

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

示例 1:

输入:ratings = [1,0,2]

输出:5

解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2:

输入:ratings = [1,2,2]

输出:4

解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。

    第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。

提示:

n == ratings.length

1 <= n <= 2 * 104

0 <= ratings[i] <= 2 * 104

思考历程与知识点:  

这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼。

先确定右边评分大于左边的情况(也就是从前向后遍历)

此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果

局部最优可以推出全局最优。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个,所以贪心:candyVec[i] = candyVec[i - 1] + 1

题解:

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};


相关文章
|
网络协议 前端开发 Java
SpringBoot 整合 WebSocket
WebSocket是基于TCP协议的一种网络协议,它实现了浏览器与服务器全双工通信,支持客户端和服务端之间相互发送信息。在有WebSocket之前,如果服务端数据发生了改变,客户端想知道的话,只能采用定时轮询的方式去服务端获取,这种方式很大程度上增大了服务器端的压力,有了WebSocket之后,如果服务端数据发生改变,可以立即通知客户端,客户端就不用轮询去换取,降低了服务器的压力。目前主流的浏览器都已经支持WebSocket协议了。
SpringBoot 整合 WebSocket
|
存储 运维 安全
SaaS多租户和单租户的区别解析
SaaS多租户的系统维护成本低,多租户系统在升级时,只需要更新一次,维护人员不需要对每个用户更新,节省了很大的运维成本,这对于所有客户都在做同样事情的系统来说是很有用的。
1174 3
|
设计模式 算法 安全
JUC系列之《深入理解AQS:Java并发锁的基石与灵魂 》
本文深入解析Java并发核心组件AQS(AbstractQueuedSynchronizer),从其设计动机、核心思想到源码实现,系统阐述了AQS如何通过state状态、CLH队列和模板方法模式构建通用同步框架,并结合独占与共享模式分析典型应用,最后通过自定义锁的实战案例,帮助读者掌握其原理与最佳实践。
拯救你的排版噩梦,搞定Deepseek到WPS的完美转换!
使用DeepSeek生成的文案复制到WPS后排版混乱?别担心,本文教你用LibreOffice解决此问题。首先下载并安装LibreOffice,然后将DeepSeek文案粘贴其中,保存为Word格式,最后用WPS打开,排版完美保留。简单四步,轻松搞定!
|
存储 人工智能 Docker
Heygem:开源数字人克隆神器!1秒视频生成4K超高清AI形象,1080Ti显卡也能轻松跑
Heygem 是硅基智能推出的开源数字人模型,支持快速克隆形象和声音,30秒内完成克隆,60秒内生成4K超高清视频,适用于内容创作、直播、教育等场景。
6020 8
|
安全 Java 定位技术
Android 浅度解析:AIDL & Binder (1)
Android 浅度解析:AIDL & Binder (1)
1134 0
|
C语言
C语言形参和实参的区别
在C语言中,形参(形式参数)与实参(实际参数)有着明确的角色区分。形参是在函数定义中声明的参数,用于接收调用函数时传入的数据;实参则是调用函数时传递的具体值或变量。简言之,实参提供数据,形参接收并处理这些数据。
1767 2
|
机器学习/深度学习 编解码 自然语言处理
【YOLOv8改进 - 注意力机制】 MHSA:多头自注意力(Multi-Head Self-Attention)
YOLO目标检测专栏探讨了BoTNet,一种在ResNet瓶颈块中用全局自注意力替换卷积的架构,提升实例分割和检测性能。BoTNet表现优于先前的ResNeSt,且在ImageNet上速度更快。文章介绍了多头自注意力(MHSA)机制,用于学习输入的不同部分间的关系。BoTNet的MHSA层整合在低分辨率特征图中,以捕获长距离依赖。YOLOv8进一步引入MHSA,通过具体的模块定义(如提供的`MHSA`类)来增强模型的注意力机制。相关论文和代码链接可供参考。
|
API
表情包-搜狗版免费API接口教程
该接口用于通过指定关键词搜索搜狗表情包,支持POST或GET请求方式。需提供用户ID和KEY,可选参数包括关键词(长度不超过10个汉字)和页码,默认第1页。返回状态码、信息提示、当前页码及表情包图片地址集合。示例中ID与KEY为公共测试用,建议使用个人ID与KEY以提高调用频率。
1126 4
|
ARouter Android开发
Android不同module布局文件重名被覆盖
Android不同module布局文件重名被覆盖
1382 0