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 次取反后最大化的数组和 思路 第一步,从前向后遍历,遇到负数将其变为正数,同时K–第二步:如果K还大于0,那么反复转变数值最小的…...
最全对象存储(云盘)挂载本地主机或服务器
1.对象存储介绍 1.1 分类 分布式存储的应用场景相对于其存储接口,现在流行分为三种: 块存储: 这种接口通常以QEMU Driver或者Kernel Module的方式存在,这种接口需要实现Linux的Block Device的接口或者QEMU提供的Block Driver接口,块存储一般…...
24校招,江淮汽车软件测试工程师技术面+HR面
前言 记录一下楼主的面试经历,希望对后来者有用 时间:15min 平台:腾讯会议 过程 技术面试 自我介绍 为啥不考研 实习收获 你有做过软件开发的工作吗? 除了Java和Python,还会其他的语言吗? 学过C吗…...
从零开始学习Zeppelin:大数据可视化分析的交互式开发系统!
介绍:Apache Zeppelin是一个基于Web的交互式开发系统,主要用于进行大数据可视化分析。其核心概念是notebook,所有的操作都可以在notebook中完成。Zeppelin提供了一套非常全面的数据分析解决方案,支持数据采集、数据发现、数据分析…...
VCG 曲面重建之滚球算法
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 滚球算法(BPA)是一种与alpha形状相关的曲面重建方法。直观地想象一个具有给定半径的3D球,我们把它扔在点云上。如果它击中任何3个点(并且它没有穿过这3个点),它就创造了一个三角形。然后,算法从现有三角形的边缘…...
为什么使用双token实现无感刷新用户认证?
单token机制 认证机制:对与单token的认证机制在我们项目中仅使用一个Access Token的访问令牌进行用户身份认证和授权的方案处理。 不足之处: 安全性较低(因为只有一个token在客户端和服务器端之间进行传递,一目Acess Token被截获或者被泄露…...
论文阅读 Self-Supervised Burst Super-Resolution
这是一篇 ICCV 2023 的文章,主要介绍的是用自监督的方式进行多帧超分的学习 Abstract 这篇文章介绍了一种基于自监督的学习方式来进行多帧超分的任务,这种方法只需要原始的带噪的低分辨率的图。它不需要利用模拟退化的方法来构造数据,而且模…...
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的效果
目的:作为一个新手开发,我想使用 Vue 3 将代码封装在 HTML 文件中时,进行界面打开展示。 一、vue计数示例 学了一个简单计数器界面展示,代码如下: <!DOCTYPE html> <html lang"en"><head&…...
面试经典150题(88-89)
leetcode 150道题 计划花两个月时候刷完,今天(第四十四天)完成了2道(88-89)150: 88.(22. 括号生成) 题目描述: 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效…...
【设计模式-3.3】结构型——享元模式
说明:说明:本文介绍设计模式中结构型设计模式中的,享元模式; 游戏地图 在一些闯关类的游戏,如超级玛丽、坦克大战里面,游戏的背景每一个关卡都不相同,但仔细观察可以发现,其都是用…...
【征服redis6】Redis的内存淘汰详解
目录 1.redis的基本策略 2.Redis中的缓存淘汰策略 3.Redis内存不足的情况 4.几种淘汰策略的实现原理 5.项目实践与优化策略 5.1 配置案例 5.2 项目优化策略参考 数据库存储会将数据保存到磁盘中,而Redis的核心数据是在内存中的,而Redis本身主要用来…...
多文件转二维码的两种方式,有兴趣的了解一下
多个文件能一键生成二维码吗?二维码是现在很多人用来展示文件内容的一种手段,在制作二维码图片之后,其他人扫码就可以查看文件或者下载文件,有效的提升文件获取的效率。一般情况下,文件二维码分为多个文件生成一个二维…...
uniapp APP接入Paypal
1. 登录paypal开发者中心, 2. 选择 Apps & Credentials 点击 Create App创建应用,创建后点击编辑按钮,如图: 3. 进入应用详情,勾选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:如何设计和执行客户旅程?
在当今数字化时代,企业成功的关键之一是建立并优化客户旅程。HubSpot作为一体化市场营销平台,通过巧妙设计和执行客户旅程,实现了个性化决策,关键节点的精准引导,为企业带来了数字化转型的引领力。 一、HubSpot是如何设…...
【Go学习】macOS+IDEA运行golang项目,报command-line-arguments,undefined
写在前面的话:idea如何配置golang,自行百度 问题1:通过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 输入密码登录界面后界面模糊卡死,键盘鼠标失效 (不同于其他博主的问题解决方案,工控机Ubuntu的系统 优先看我的博客。) 系统版本:ubuntu18.04 主机:工控机 应用场景:电力系统巡…...
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. 修剪二叉搜索树 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 解题思路:如果当前结点小于所给区间,那该节点及其左子树肯定不符合条件,返回其右子树作为上一结点子树;反之…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
