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

LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖果)

文章目录

  • 前置知识
  • 1005.K次取反后最大化的数组和
    • 题目描述
    • 分情况讨论
    • 贪心算法
  • 134. 加油站
    • 题目描述
    • 暴力解法
    • 贪心算法
  • 135. 分发糖果
    • 题目描述
    • 暴力解法
    • 贪心算法
  • 总结

前置知识

参考前文

参考文章:
LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)
LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)

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

题目描述

在这里插入图片描述

LeetCode链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

分情况讨论

首先sort nums, 然后统计其中的负数的数量为n
n=k, 将所有负数转为正数
n>k, 从小到大地处理k个负数, 然后结束
n<k, 将所有负数转为正数后, 再sort数组, 对sort后的数组最小数处理(k-n)

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int n=0;for(int num : nums){if(num<0)n++;elsebreak;}if(n>=k){for(int i=0; i<k; i++){nums[i] = -nums[i];}}else{for(int i=0; i<n; i++){nums[i] = -nums[i];}sort(nums.begin(), nums.end());int key = k-n;if(key%2 != 0)nums[0] = -nums[0];}int ans=0;for(int num : nums){ans += num;}return ans;}
};

贪心算法

换一种实现方法: 先按照绝对值进行从大到小排序, 然后遍历加和
k没用完的时候遇到负数就加上其绝对值, k--
k用完了就加上其本身值, 遍历到最后如果k还有剩余, 且剩余k为奇数, 就加上最后一个数的负数

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

134. 加油站

题目描述

在这里插入图片描述

LeetCode链接:https://leetcode.cn/problems/gas-station/description/

暴力解法

① 暴力解法, 把每个点都尝试跑一遍

class Solution {
public:bool check(int index, vector<int>& diff){int sum=diff[index], cur=index+1;if(cur>=diff.size())cur=0;while(cur != index){if(sum<0){return false;}else{sum += diff[cur];cur ++;if(cur>=diff.size())cur=0;}}if(sum<0)return false;return true;}int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();vector<int> diff(n);for(int i=0; i<n; ++i){diff[i] = gas[i] - cost[i];}for(int i=0; i<n; ++i){if(check(i, diff))return i;}return -1;}
};

贪心算法

很遗憾, 暴力解法超出时间限制了
② 贪心算法, 过程中维护curSumtotalSum;
curSum<0时整个计数从i+1开始(curSum置为0)(将ans置为i+1)
totalSum记录所有的sum, 如果最后totalSum<0, 那么返回-1

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

135. 分发糖果

题目描述

在这里插入图片描述

LeetCode链接:https://leetcode.cn/problems/candy/description/

暴力解法

暴力解法: 创建vector<int> candy(ratings.size(), 1), 记录给每个孩子分的糖, 初始每个孩子都有一颗糖
多次遍历, 发现一个孩子比相邻的孩子ratings高, 但是candy没有更多, 就candy++, 同时ans++
循环遍历, 直到没有发现以上情况

class Solution {
public:bool check(int i, vector<int>& ratings, vector<int>& candy){if(i==0){if(ratings[i]>ratings[i+1] && candy[i]<=candy[i+1])return true;elsereturn false;}else if(i==ratings.size()-1){if(ratings[i]>ratings[i-1] && candy[i]<=candy[i-1])return true;elsereturn false;}else{if((ratings[i]>ratings[i+1] && candy[i]<=candy[i+1]) || (ratings[i]>ratings[i-1] && candy[i]<=candy[i-1]))return true;elsereturn false;}return false;}int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 1);int ans=ratings.size();if(ans<=1)return ans;bool changed=true;while(changed==true){changed = false;for(int i=0; i<ratings.size(); ++i){if(check(i, ratings, candy)){candy[i] ++;changed = true;ans ++;}}}return ans;}
};

贪心算法

很遗憾, 通过样例, 但是超出时间范围
参考<代>, 使用贪心算法, 具体操作如下
进行两次遍历, 一次从前往后, 一次从后往前
从前往后遍历过程中: 如果发现ratings[i+1]>ratings[i], 则candy[i+1] = max(candy[i+1], candy[i]+1);
从后往前遍历过程中: 如果发现ratings[i-1]>ratings[i], 则candy[i-1] = max(candy[i-1], candy[i]+1);

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

总结

贪心, 讲真就是只有思想, 没有固定的套路.
现在做(被折磨)多了, 下意识的, 逐渐有一种"看看了解了解"的想法了.

如果笔试的时候真遇到类似的题目, 如果可以想到贪心, 那么最好;
如果一时半会儿没有想到很巧妙的方法, 最好先用暴力解法, 通过一部分测试用例, 分到手最好.

归根到底还是要代码实现能力过硬, 可不要感觉暴力解法是那么简单哦~
很多时候想的很清楚, 写出来就是很奇怪;

并且写的是一会儿, 往往在代码层面可以有优化很多的写法.
当然, 这样的功夫, 也只能在不断的练习过程中慢慢培养了.

本文参考:
K次取反后最大化的数组和
加油站
分发糖果

相关文章:

LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖果)

文章目录 前置知识1005.K次取反后最大化的数组和题目描述分情况讨论贪心算法 134. 加油站题目描述暴力解法贪心算法 135. 分发糖果题目描述暴力解法贪心算法 总结 前置知识 参考前文 参考文章&#xff1a; LeetCode刷题笔记【23】&#xff1a;贪心算法专题-1&#xff08;分发饼…...

java基础面试题 第四天

一、java基础面试题 第四天 1. String 为什么不可变&#xff1f; **不可变对象&#xff1a;**不可变对象在java中就是被final修饰的类就称为不可变对象&#xff0c;具体含义是&#xff0c;不可变对象一但被赋值以后&#xff0c;他的引用地址就不能被修改&#xff08;它的属性…...

postgresql-常用日期函数

postgresql-常用日期函数 简介计算时间间隔获取时间中的信息截断日期/时间创建日期/时间获取系统时间时区转换 简介 PostgreSQL 提供了以下日期和时间运算的算术运算符。 获取当前系统时间 select current_date,current_time,current_timestamp ;-- 当前系统时间一周后的日…...

【业务场景】用户连点

处理用户连点 1.时间戳处理 思路&#xff1a;通过检查当前时间和上一次触发事件的时间之间的间隔&#xff0c;判断是否允许继续执行。 代码如下&#xff1a; // clickThrottle.js /* 防止重复点击 */ let clickTimer 0function clickThrottle(interval 3000) {let now n…...

zabbix企业微信告警

目前&#xff0c;企业微信使用要设置可信域名 华为云搜索云函数 创建函数 选择http函数&#xff0c;随便输入函数名字 回到函数列表&#xff0c;选择刚创建的函数&#xff0c;创建触发器&#xff0c;安全模式选择none 点击右上角管理 选刚创建的api&#xff0c;右边操作点…...

(高频面试1)Redis缓存穿透、缓存击穿、缓存雪崩

目录 一&#xff1a;缓存数据 1.1 应用场景 1.2&#xff1a;缓存数据出现的问题 1.2.1 缓存穿透 1.2.2 解决办法 1.2.3 缓存击穿 1.2.4 解决办法 1.2.5 缓存雪崩 1.2.6 解决办法 一&#xff1a;缓存数据 1.1 应用场景 数据库查询结果缓存是一种常见的缓存应用场景&a…...

c++推箱子小游戏

上代码: #include <stdio.h> #include <stdlib.h> #include <conio.h>int map[2][7][8] {//0:空的 1:■ :墙//3&#xff1a;☆ 4&#xff1a;★ //目的地和箱子//5&#xff1a;※ //人//7:⊙ //目的(3)和箱子(4)在一起//8&#xff1a;※ //人(5…...

SpringMVC:从入门到精通

一、SpringMVC是什么 SpringMVC是Spring提供的一个强大而灵活的web框架&#xff0c;借助于注解&#xff0c;Spring MVC提供了几乎是POJO的开发模式【POJO是指简单Java对象&#xff08;Plain Old Java Objects、pure old java object 或者 plain ordinary java object&#xff0…...

jmeter 数据库连接配置 JDBC Connection Configuration

jmeter 从数据库获取变量信息 官方文档参考&#xff1a; [jmeter安装路径]/printable_docs/usermanual/component_reference.html#JDBC_Connection_Configuration 引入数据库连接&#xff1a; 将MySQLjar包存放至jemter指定目录&#xff08;/apache-jmeter-3.3/lib&#xff09…...

TVC广告片制作成本多少

电视是广告传播的主要媒介之一&#xff0c;具有广泛的受众群体和较高的覆盖率。通过在电视上播放广告片&#xff0c;企业可以将产品或者服务的信息传达给大量潜在客户&#xff0c;提高知名度和曝光度。接下来由深圳TVC广告片制作公司老友记小编从以下几个方面浅析制作一条TVC广…...

【Express.js】代码规范

代码规范 编程规范&#xff0c;对于一个优秀的项目是不可或缺的&#xff0c;有了良好的代码规范&#xff0c;有益于项目的维护与拓展。 命名规范 命名的第一要义是明了&#xff0c;要让阅读者看到命名就能大概猜测出其意义或用处。 以用户身份&#xff08;userRole&#xff…...

Vue2+Vue3基础入门到实战项目(前接六 副线一)—— 面经 项目

day1 接口文档地址&#xff1a;https://www.apifox.cn/apidoc/project-934563/api-20384515 一、项目功能演示 1.目标 启动准备好的代码&#xff0c;演示移动端面经内容&#xff0c;明确功能模块 2.项目收获 二、项目创建目录初始化 vue-cli 建项目 1.安装脚手架 (已安装…...

QT tcpserver

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);// 服务端有QTcpServer库&#xff0c;封装了监听操作server new QTcpServer();// 直接监听&#xff0c;内部根…...

Android adb shell svc 知识详解

adb shell svc 详解 文章目录 adb shell svc 详解一、svc 常用命令&#xff1a; 二、svc 命令和使用示例&#xff1a;查看系统是否安装了svc1、svc2、svc help3、svc power svc wifi has been migrated to WifiShellCommand,simply perform translation to cmd wifi set-wifi-e…...

Debian12系统下LAMP环境中Nubuilder4.5的安装

一、环境搭建 按照官方的说法&#xff0c;Apache2和Nginx都可以的&#xff0c;实际上&#xff0c;你最好直接按照 Mariadb\Apache2\Php8.2 这个顺序&#xff0c;搭建LAMP环境较好。不然各种调试&#xff0c;还不一定能够成功。 相关搭建方法&#xff0c;属于一般操作&#xf…...

百度超级链BaaS服务平台调研

目录 一、菜单功能1.1、在线版1.2、服务版 二、其他说明2.1、服务平台的部署方式2.2、混合部署 百度超级链XuperChain管理平台文档地址&#xff1a;https://xuper.baidu.com/n/doc#/c8737c7b/1_0_0/c8737c7b 一、菜单功能 1.1、在线版 在线版功能稍多。 菜单子菜单/功能点子…...

计算机网络之TCP/IP协议第二篇:OSI参考模型详解

文章目录 写给自己的话 一:协议分层与OSI参考模型 二:通过对话理解分层 三:OSI参考模型...

Linux内核分析与应用2-内存寻址

本系列是对 陈莉君 老师 Linux 内核分析与应用[1] 的学习与记录。讲的非常之好&#xff0c;推荐观看 留此记录&#xff0c;蜻蜓点水,可作抛砖引玉 2.1 内存寻址 数据连续存储和选择读取思想,是目前我们使用的几乎所有机器运行背后的灵魂 计算机体系结构中的核心问题之一,就是如…...

苍穹外卖 day12 Echats 营业台数据可视化整合

苍穹外卖-day12 课程内容 工作台Apache POI导出运营数据Excel报表 功能实现&#xff1a;工作台、数据导出 工作台效果图&#xff1a; 数据导出效果图&#xff1a; 在数据统计页面点击数据导出&#xff1a;生成Excel报表 1. 工作台 1.1 需求分析和设计 1.1.1 产品原型 工作台是系…...

代码随想录算法训练营day45|70. 爬楼梯(进阶版)|322. 零钱兑换|279.完全平方数

70. 爬楼梯(进阶版) 一步一个台阶&#xff0c;两个台阶&#xff0c;三个台阶&#xff0c;…&#xff0c;直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢&#xff1f; 1阶&#xff0c;2阶&#xff0c;… m阶就是物品&#xff0c;楼顶就是背包。 每一阶可以重复使用&#…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...