代码训练营Day.34 | 1005. K次取反后最大化的数组和、134. 加油站、135. 分发糖果

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

1. LeetCode链接

1005. K 次取反后最大化的数组和 - 力扣(LeetCode)

2. 题目描述

3. 解法

整体来说,就是把负数全部取反,然后如果有剩余反转次数都给绝对值最小的数。

我的解法:先从小到大排序,这个需要分析多种情况。略。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i = 0;
        int sum = 0;
        for (; i < nums.size() && k > 0; i++) {
            if (nums[i] >= 0) break;
            nums[i] = 0 - nums[i];
            sum += nums[i];
            k--;
        }
        if (i != nums.size() && k != 0) {
            if (i > 0 && nums[i] > nums[i - 1]) {
                i--;
                sum -= nums[i];
            }
            if (k % 2 == 1) nums[i] = 0 - nums[i]; 
        } else if (i == nums.size() && k != 0) {
            if (k % 2 == 1) sum -= 2 *nums[nums.size() - 1];
        }
        for (; i < nums.size(); i++) {
            sum += nums[i];
        }
        return sum;
        // k <= nums中的非正数个数
        // k > nums中的非正数个数 && 有0
        // k > nums中的非正数个数 && no 0
        // nums中全是非正数
    }
};

简洁方法,直接按照绝对值大小排序。

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if(nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
            sum += nums[i];
        }
        if (k % 2 == 1) sum -= 2 * nums[nums.size() - 1];
        return sum;
    }
};

134. 加油站

1. LeetCode链接

134. 加油站 - 力扣(LeetCode)

2. 题目描述

3. 解法

整体来说,如果gas的总量 < cost的总量,汽车无论如何都不可能循环一周。否则,必可以循环一周。

我的解法:

1. 判断两个数组总量是否合理。求得存储两数组对应元素差值的数组left(表示,空油箱从i节点出发,到i + 1节点还能剩多少油)。

2. 如果left总和 < 0,直接return -1.

3. 如果left综合 > =0。在left数组上执行类似于LeetCode题目53.最大子序和的操作。首先,记录最大子序的长度len,直到长度与原数组长度相等,return 当前下标;count持续记录连续序列和,如果<0,则刷新len和count。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int count = 0;
        vector<int> left;
        for (int i = 0; i < gas.size(); i++) {
            left.push_back(gas[i] - cost[i]);
        }
        for (int i : left) count += i;
        if (count < 0) return -1;
        int len = gas.size();
        int i = 0;
        count = 0;
        while (1) {
            if (len == 0) return i;
            count += left[i];
            len--;
            if (count < 0) {
                count = 0;
                len = gas.size();
            }
            i = (i + 1) % gas.size();
        }
    }
};

还有更简单的是,记录累加和初始坐标start,这样可以在一遍遍历后得到答案,而且只需一次遍历。

因为如果在计算局部累加和时,count < 0,则说明其对应累加初始坐标一定不是循环起始点,累加和之间的坐标,也不是!这时,初始化count并记录start。

最后,因为是一次从前到后的完整遍历。判断记录后的累加差值是负数,则return -1。否则,return start。

start之后的是否可能也存在循环起点?因为start到末尾的累加和中,从来没有小于过0,所以,start一定是第一个。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0;
        int count = 0;
        int sum = 0;
        for (int i = 0; i < gas.size(); i++) {
            count += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (count < 0) {
                count = 0;
                start = i + 1;
            }
        }
        if (sum < 0) return -1;
        return start;
    }
};

135. 分发糖果

1. LeetCode链接

135. 分发糖果 - 力扣(LeetCode)

2. 题目描述

3. 解法

我的解法:

整体来说,就是每个孩子尽可能拿最少的糖果数量。

一般我们自己解这种题,都是先找极小值;然后,将极小值点设为1(颗糖果),从极小值开始,向左爬升到极大值点,糖果数量依次+1,向右爬升到极大值点,糖果数量一次+1。

编程时,需要先计算完所有极小值点向一侧爬升后,再考虑一起从另一侧爬升。这是因为一个极大值点,两侧各有一个极小值点;左侧极小值点向右爬升得到的糖果数量 和 右侧极小值点向左爬升得到的糖果数量,当前极大值点要取最大值。如果按极小值点先后顺序同时考虑两侧爬升,并不能考虑到这一点。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int pre = ratings[0];
        int cur;
        int post = 0;
        vector<int> index;
        vector<int> candies(ratings.size(), 0);    // 记录每个孩子能分发到的最终糖果数量
        for (int i = 0; i < ratings.size(); i++) {    // 找极小值点,其中判断时,仅考虑非严格递增/递减
            if (i == ratings.size() - 1) post = ratings[i];
            else post = ratings[i + 1];
            cur = ratings[i];
            if (pre >= cur && cur <= post) index.push_back(i);
            pre = cur;
        }
        for (int i = 0; i < index.size(); i++) {   // 从所有极小值点出发,向左爬升
            candies[index[i]] = 1;
            int c = 2;
            for (int j = index[i] - 1; j >=0; j--) {
                if (ratings[j] <= ratings[j + 1]) break;
                candies[j] = c;
                c++;
            }
        }
        for (int i = 0; i < index.size(); i++) {   // 从所有极小值点出发,向右爬升
            int c = 2;
            for (int j = index[i] + 1; j < ratings.size(); j++) {
                if (ratings[j] <= ratings[j - 1]) break;
                if (candies[j] > c) break;
                candies[j] = c;
                c++;
            }
        }
        int sum = 0;
        for (int i : candies) sum += i;     // 求和
        return sum;
    }
};

巧妙解法:

局部最优:所有孩子的相邻右孩子如果评分比他高的话+1糖果;所有孩子的相邻左孩子如果评分比他高的话+1糖果。

全局最优:相邻两个孩子评分更高的孩子会获得更多的糖果。

1. 先设置数组记录每个孩子分到的糖果数,设置基数都为1,即每个孩子都分到一个。

2. 从左向右遍历,如果当前孩子评分比前一个高,前一个糖果数+1。

3. 从右向左遍历,如果当前孩子评分比后一个高,取他原本的数/后一个糖果数+1中最大的。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int i : candies) sum += i;
        return sum;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/324014.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

浅谈专项测试之弱网络测试

一&#xff0e;弱网络测试背景 移动端产品的使用并非完全都是在流畅的wifi环境&#xff0c;大部分用户主要使用4G,3G,2G等网络&#xff0c;另外因为移动端产品使用的场景多变&#xff0c;如进公交&#xff0c;上地铁&#xff0c;坐电梯&#xff0c;使得弱网测试显得尤为重要。考…

HTML--JavaScript--引入方式

啊哈~~~基础三剑看到第三剑&#xff0c;JavaScript HTML用于控制网页结构 CSS用于控制网页的外观 JavaScript用于控制网页的行为 JavaScript引入方式 引入的三种方式&#xff1a; 外部JavaScript 内部JavaScript 元素事件JavaScript 引入外部JavaScript 一般情况下网页最好…

8个 Python 开发者必备的 PyCharm 插件

这8个顶级插件保证了更快、更轻松、更愉悦的开发过程。 在 PyCharm 插件列表中&#xff0c;我们发现了几个瑰宝插件&#xff0c;它们各自以独特的方式帮助开发者快速、简便、愉悦地开发。 今天我就给大家逐个介绍它们。 1. Key Promoter X 【下载链接】&#xff1a;https://…

OWASP漏洞原理启航(第一课)

OWASP Top 10 2021 介紹 漏洞原理启航介绍 OWASP 定义&#xff1a; AI介绍 OWASP (开放Web应用程序和安全项目) 是一个全球性的社区&#xff0c;致力于提供关于Web应用程序安全性的信息、教育和支持。OWASP是一个非盈利组织&#xff0c;由志愿者驱动&#xff0c;旨在提高Web应…

day-10 删除排序链表中的重复元素

思路 先统计每个值出现的次数&#xff0c;然后将出现次数为一的节点链接为一个链表即可 解题方法 while(t!null){ //统计每个值出现次数 arr[t.val100]1; tt.next; } while(t!null&&arr[t.val100]!1) tt.next;//确定返回的头结点 ttt; while(t!null&&t.next…

2024年全网最全春招时间线

2024年全网最全春招时间线 春招&#xff0c;许多同学可能会误以为这是春天才会进行。 你可能会想&#xff0c;期末刚考完试&#xff0c;先享受下寒假&#xff0c;再欢度春节&#xff0c;收些红包&#xff0c;甚至还能抽空去理个发型。等到春日明媚时&#xff0c;再参加春招活…

Linux常用命令大全(三)

系统权限 用户组 1. 创建组groupadd 组名 2. 删除组groupdel 组名 3. 查找系统中的组cat /etc/group | grep -n “组名”说明&#xff1a;系统每个组信息都会被存放在/etc/group的文件中1. 创建用户useradd -g 组名 用户名 2. 设置密码passwd 用户名 3. 查找系统账户说明&am…

C++学习笔记——类继承

目录 一、一个简单的基类 1.1封装性 1.2继承性 1.3虚函数 1.4多态性 二、基类 2.1一个简单的C基类的示例 2.2 Animal是一个基类。 三、继承 3.1概念 3.2is-a关系 3.3多态公有继承 3.4静态联编和动态联编 3.5访问控制 3.6ABC理念 一、一个简单的基类 C中的基类是一…

使用ChatGPT对进行论文改写与润色

一、内容改写 关键在于明确改写的具体要求。 例如:[论文内容] 可以指明需要提升该段落的流畅性和逻辑连贯性。 常用指令 细微调整文本 轻微编辑 重写以增强表述清晰度 简化句式 校正语法和拼写错误 提升文本的流畅性和条理性 优化词汇使用 调整文本风格 进行深度编辑…

15.鸿蒙HarmonyOS App(JAVA)进度条与圆形进度条

15.鸿蒙HarmonyOS App(JAVA)进度条与圆形进度条 progressBar2.setIndeterminate(true);//设置无限模式,运行查看动态效果 //创建并设置无限模式元素 ShapeElement element new ShapeElement(); element.setBounds(0,0,50,50); element.setRgbColor(new RgbColor(255,0,0)); …

VueCli-自定义创建项目

参考 1.安装脚手架 (已安装可以跳过) npm i vue/cli -g2.创建项目 vue create 项目名 // 如&#xff1a; vue create dn-demo键盘上下键 - 选择自定义选型 Vue CLI v5.0.8 ? Please pick a preset:Default ([Vue 3] babel, eslint)Default ([Vue 2] babel, eslint) > M…

window系统安装MySQL -- MySQL(1)

第一步&#xff1a; 下载mysql安装包 1&#xff09;打开MySQL官方链接&#xff1a;https://www.mysql.com 2&#xff09;选择 DOWNLOADS 3&#xff09;往下滑&#xff0c;点击社区版本下载 4&#xff09;点击 MySQL installer for Windows 5&#xff09;点击安装 第二步&#…

git 中的概念

git 中的概念 在使用 Git 版本控制的过程中&#xff0c;有些概念我们必须有所了解&#xff0c;这样才能更有效率也更有意义的学下去。 有清楚且正确的概念认知&#xff0c;不但有助于我们学习如何操作 Git 命令&#xff0c;更重要的是&#xff0c;学习 Git 的相关知识也会更加…

【Python学习】Python学习14-函数

目录 【Python学习】Python学习14-函数 前言自定义函数创建语法自定义函数与调用参数传递参考 文章所属专区 Python学习 前言 本章节主要说明Python的函数。函数是组织好的&#xff0c;可重复使用的&#xff0c;用来实现单一&#xff0c;或相关联功能的代码段。 函数能提高应…

FFmpeg 入门

1. 编译 参考文档&#xff1a;FFmpeg编译和集成(FFmpeg开发基础知识)&#xff0c;重点注意这句话&#xff1a; 在MSYS2 Packages可以查到云仓库有哪些包&#xff0c;直接安装可节约大量时间。 注意&#xff1a;这个路径可自定义 吐槽 在看到这篇文章之前&#xff0c;花了大…

系列二、Spring Security中的核心类

一、Spring Security中的核心类 1.1、自动配置类 UserDetailsServiceAutoConfiguration 1.2、密码加密器 1.2.1、概述 Spring Security 提供了多种密码加密方案&#xff0c;官方推荐使用 BCryptPasswordEncoder&#xff0c;BCryptPasswordEncoder 使用 BCrypt 强哈希函数&a…

深入浅出关于go web的请求路由

文章目录 前言一、是否一定要用框架来使用路由&#xff1f;二、httprouter2.1 httprouter介绍2.2 httprouter原理2.3 路由冲突情况 三、gin中的路由总结 前言 最近重新接触Go语言以及对应框架&#xff0c;想借此机会深入下对应部分。 并分享一下最近学的过程很喜欢的一句话&am…

(Java企业 / 公司项目)JMeter接口压测使用(保姆式手把手教会)

一. JMeter简介认识&#xff08;重点是下面的使用方法&#xff09; JMeter是一个开源的Java应用程序&#xff0c;由Apache软件基金会开发和维护&#xff0c;可用于性能测试、压力测试、接口测试等。 1. 原理 JMeter的基本原理是模拟多用户并发访问应用程序&#xff0c;通过发…

ECMAScript

ECMAScript 是 JavaScript 语言的国际标准化规范。它定义了 JavaScript 的语法、类型、语句、关键字、保留字、操作符、对象等核心语言特性&#xff0c;为 JavaScript 的实现提供了一致性和标准化的指南。 1.概念介绍 1.1.背景和历史 起源&#xff1a;ECMAScript 起源于 199…

腾讯云服务器怎么买?两种购买方式更省钱

腾讯云服务器购买流程很简单&#xff0c;有两种购买方式&#xff0c;直接在官方活动上购买比较划算&#xff0c;在云服务器CVM或轻量应用服务器页面自定义购买价格比较贵&#xff0c;但是自定义购买云服务器CPU内存带宽配置选择范围广&#xff0c;活动上购买只能选择固定的活动…