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

Day34 贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果

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

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

思路

  • 第一步,从前向后遍历,遇到负数将其变为正数,同时K–
  • 第二步:如果K还大于0,那么反复转变数值最小的元素,将K用完
  • 第三步:求和
class Solution {
public:static bool Compare(int& a, int& b){return abs(a) > abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end(),Compare); //绝对值排序for(int i = 0; i<nums.size();i++){if(nums[i]<0 && k>0){ //第一步贪心,取绝对值最大的数确保为正数nums[i] = -nums[i];k--;}}if(k%2==1) nums[nums.size()-1] *= -1; //第二步贪心,如果k还有剩余,进行绝对值最小数的操作int result = 0; //第三步,取结果for (int a : nums) result += a;       return result;}
};

134. 加油站

方法一(暴力)

leetcode超时(35/40)

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for(int i = 0; i<gas.size(); i++){int rest = gas[i]-cost[i]; //记录当天用油差值int Index = (i+1)%gas.size(); //方便下面的while进行判断while(rest>0 && Index!=i){rest+=gas[Index] - cost[Index];Index = (Index + 1) % cost.size();}if(Index ==i && rest >=0) return i; //返回当前i}return -1;}
};

方法二(贪心)

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i < gas.size(); i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0start = i + 1;  // 起始位置更新为i+1curSum = 0;     // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};

135. 分发糖果

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-1]<ratings[i]) candyVec[i] = candyVec[i-1] +1;}for(int i = ratings.size()-1; i>=1; i--){ //从后往前if(ratings[i] <ratings[i-1]) candyVec[i-1] =max(candyVec[i-1],candyVec[i]+1);}int result = 0;for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];return result;}
};

相关文章:

Day34 贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果

贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果 1005. K 次取反后最大化的数组和 思路 第一步&#xff0c;从前向后遍历&#xff0c;遇到负数将其变为正数&#xff0c;同时K–第二步&#xff1a;如果K还大于0&#xff0c;那么反复转变数值最小的…...

最全对象存储(云盘)挂载本地主机或服务器

1.对象存储介绍 1.1 分类 分布式存储的应用场景相对于其存储接口&#xff0c;现在流行分为三种: 块存储: 这种接口通常以QEMU Driver或者Kernel Module的方式存在&#xff0c;这种接口需要实现Linux的Block Device的接口或者QEMU提供的Block Driver接口&#xff0c;块存储一般…...

24校招,江淮汽车软件测试工程师技术面+HR面

前言 记录一下楼主的面试经历&#xff0c;希望对后来者有用 时间&#xff1a;15min 平台&#xff1a;腾讯会议 过程 技术面试 自我介绍 为啥不考研 实习收获 你有做过软件开发的工作吗&#xff1f; 除了Java和Python&#xff0c;还会其他的语言吗&#xff1f; 学过C吗…...

从零开始学习Zeppelin:大数据可视化分析的交互式开发系统!

介绍&#xff1a;Apache Zeppelin是一个基于Web的交互式开发系统&#xff0c;主要用于进行大数据可视化分析。其核心概念是notebook&#xff0c;所有的操作都可以在notebook中完成。Zeppelin提供了一套非常全面的数据分析解决方案&#xff0c;支持数据采集、数据发现、数据分析…...

VCG 曲面重建之滚球算法

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 滚球算法(BPA)是一种与alpha形状相关的曲面重建方法。直观地想象一个具有给定半径的3D球,我们把它扔在点云上。如果它击中任何3个点(并且它没有穿过这3个点),它就创造了一个三角形。然后,算法从现有三角形的边缘…...

为什么使用双token实现无感刷新用户认证?

单token机制 认证机制&#xff1a;对与单token的认证机制在我们项目中仅使用一个Access Token的访问令牌进行用户身份认证和授权的方案处理。 不足之处&#xff1a; 安全性较低(因为只有一个token在客户端和服务器端之间进行传递&#xff0c;一目Acess Token被截获或者被泄露…...

论文阅读 Self-Supervised Burst Super-Resolution

这是一篇 ICCV 2023 的文章&#xff0c;主要介绍的是用自监督的方式进行多帧超分的学习 Abstract 这篇文章介绍了一种基于自监督的学习方式来进行多帧超分的任务&#xff0c;这种方法只需要原始的带噪的低分辨率的图。它不需要利用模拟退化的方法来构造数据&#xff0c;而且模…...

Spring+SpringMVC+Mybatis进行项目的整合

Spring SpringMVCM Mybatis 整合 一、 通过idea创建maven工程 二、 引入依赖项以及导入mybatis逆向工程的插件 将如下的文件替换所在工程的pom文件 <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://maven.apache.org/POM/4…...

vue3 实现简单计数器示例——一个html文件展示vue3的效果

目的&#xff1a;作为一个新手开发&#xff0c;我想使用 Vue 3 将代码封装在 HTML 文件中时&#xff0c;进行界面打开展示。 一、vue计数示例 学了一个简单计数器界面展示&#xff0c;代码如下&#xff1a; <!DOCTYPE html> <html lang"en"><head&…...

面试经典150题(88-89)

leetcode 150道题 计划花两个月时候刷完&#xff0c;今天&#xff08;第四十四天&#xff09;完成了2道(88-89)150&#xff1a; 88.(22. 括号生成) 题目描述&#xff1a; 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效…...

【设计模式-3.3】结构型——享元模式

说明&#xff1a;说明&#xff1a;本文介绍设计模式中结构型设计模式中的&#xff0c;享元模式&#xff1b; 游戏地图 在一些闯关类的游戏&#xff0c;如超级玛丽、坦克大战里面&#xff0c;游戏的背景每一个关卡都不相同&#xff0c;但仔细观察可以发现&#xff0c;其都是用…...

【征服redis6】Redis的内存淘汰详解

目录 1.redis的基本策略 2.Redis中的缓存淘汰策略 3.Redis内存不足的情况 4.几种淘汰策略的实现原理 5.项目实践与优化策略 5.1 配置案例 5.2 项目优化策略参考 数据库存储会将数据保存到磁盘中&#xff0c;而Redis的核心数据是在内存中的&#xff0c;而Redis本身主要用来…...

多文件转二维码的两种方式,有兴趣的了解一下

多个文件能一键生成二维码吗&#xff1f;二维码是现在很多人用来展示文件内容的一种手段&#xff0c;在制作二维码图片之后&#xff0c;其他人扫码就可以查看文件或者下载文件&#xff0c;有效的提升文件获取的效率。一般情况下&#xff0c;文件二维码分为多个文件生成一个二维…...

uniapp APP接入Paypal

1. 登录paypal开发者中心&#xff0c; 2. 选择 Apps & Credentials 点击 Create App创建应用&#xff0c;创建后点击编辑按钮&#xff0c;如图&#xff1a; 3. 进入应用详情&#xff0c;勾选Log in with PayPal点击 Advanced Settings 添加return URL等信息并保存。如图&a…...

QT-贪吃小游戏

QT-贪吃小游戏 一、演示效果二、关键程序三、下载链接 一、演示效果 二、关键程序 #include "Snake.h" #include "Food.h" #include "Stone.h" #include "Mushroom.h" #include "Ai.h" #include "Game.h" #inclu…...

HubSpot:如何设计和执行客户旅程?

在当今数字化时代&#xff0c;企业成功的关键之一是建立并优化客户旅程。HubSpot作为一体化市场营销平台&#xff0c;通过巧妙设计和执行客户旅程&#xff0c;实现了个性化决策&#xff0c;关键节点的精准引导&#xff0c;为企业带来了数字化转型的引领力。 一、HubSpot是如何设…...

【Go学习】macOS+IDEA运行golang项目,报command-line-arguments,undefined

写在前面的话&#xff1a;idea如何配置golang&#xff0c;自行百度 问题1&#xff1a;通过idea的terminal执行go test报错 ✘ xxxxxmacdeMacBook-Pro-3  /Volumes/mac/.../LearnGoWithTests/hello  go test go: go.mod file not found in current directory or any parent …...

优先看我的博客:工控机 Ubuntu系统 输入密码登录界面后界面模糊卡死,键盘鼠标失效(不同于其他博主的问题解决方案,优先看我的博客。)

工控机Ubuntu 输入密码登录界面后界面模糊卡死&#xff0c;键盘鼠标失效 &#xff08;不同于其他博主的问题解决方案&#xff0c;工控机Ubuntu的系统 优先看我的博客。&#xff09; 系统版本&#xff1a;ubuntu18.04 主机&#xff1a;工控机 应用场景&#xff1a;电力系统巡…...

SAP 中的外部接口:预扣税

文章目录 1 Introduction2 implementation3 Summary 1 Introduction We use BP create WTAX_TYPE ,I don’t find a bapi. We will update for it . We will impement WTax type , WTax code ,Subject in the ‘BP’. 2 implementation UPDATE lfbw SET witht gs_alv-wit…...

代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 解题思路&#xff1a;如果当前结点小于所给区间&#xff0c;那该节点及其左子树肯定不符合条件&#xff0c;返回其右子树作为上一结点子树&#xff1b;反之…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...