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

代码随想录算法训练营day29

代码随想录算法训练营

—day29

文章目录

  • 代码随想录算法训练营
  • 前言
  • 一、134. 加油站
    • 暴力解法
    • 贪心算法
  • 二、135. 分发糖果
  • 三、860. 柠檬水找零
  • 四、406.根据身高重建队列
    • vector版
    • list版
  • 总结


前言

今天是算法营的第29天,希望自己能够坚持下来!
今日任务:
● 134. 加油站
● 135. 分发糖果
● 860.柠檬水找零
● 406.根据身高重建队列


一、134. 加油站

题目链接
文章讲解
视频讲解

暴力解法

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for (int i = 0; i < cost.size(); i++) {int rest = gas[i] - cost[i]; // 记录剩余油量int index = (i + 1) % cost.size();while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈(如果有rest==0,那么答案就不唯一了)rest += gas[index] - cost[index];index = (index + 1) % cost.size();}// 如果以i为起点跑一圈,剩余油量>=0,返回该起始位置if (rest >= 0 && index == i) return i;}return -1;}
};

贪心算法

思路:

  1. 如果总油量减去总消耗大于等于零那么一定可以跑完一圈,说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
  2. 每个加油站的剩余量rest[i]为gas[i] - cost[i]。
  3. i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。

解释第三点:
有没有可能 [0,i] 区间 选某一个作为起点,累加到 i这里 curSum是不会小于零呢?
在这里插入图片描述
如果是区间2开始累加不小于0,但从区间1+区间2是小于0的,可以得出区间1是小于0的。
但根据我们的代码逻辑,只要小于0就会更新起始位置,那么在遍历到区间1和区间2之间的时候就已经更新起始位置了,不会一直加到当前这个位置。

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) { //当前累加值小于0start = i + 1; //更新起始位置到i+1curSum = 0; //重新累加}}if (totalSum < 0) return -1; //说明不可能跑完一圈return start; //totalSum>=0时,将start之前的累加看作A, 之后的累加看作B, 已知A+B = total>=0,A<0,B>0,//那么B>|A|也就是B>=-A, 所以B+A>=0, 从start点出发可以跑完}
};

二、135. 分发糖果

题目链接
文章讲解
视频讲解

思路:
当有两个维度需要考虑的时候,先考虑其中一边,再考虑另一边。
本题是先考虑右孩子是否评分比较高,再考虑做孩子是否评分比较高。
1.创建一个糖果数数组,初始化为1(每个小孩至少有一个糖果);
2.从第二个元素开始从前往后遍历,判断当前元素是否比左边元素大;
3.是则当前元素需要比左边元素糖果+1;
4.从倒数第二个元素开始从后往前遍历,判断当前元素是否比右边元素大;
5.是则当前元素比右边元素糖果+1,与第一次遍历的结果做比较,取两者最大值;
6.遍历糖果数组计算糖果总数。

对于第二次遍历为什么要从后往前遍历:
因为取糖果+1的时候是取右边的糖果+1,如果是从前往后的话,右边的糖果是一直更新的,那么就导致当前正确的糖果数也一直需要更新。

代码如下:

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candys(ratings.size(), 1);//从第二个元素开始从前往后遍历,判断当前元素是否比左边元素大for (int i = 1; i < ratings.size(); i ++) {if (ratings[i] > ratings[i - 1]) candys[i] = candys[i - 1] + 1;}//从倒数第二个元素开始从后往前遍历,判断当前元素是否比右边元素大for (int i = ratings.size() - 2; i >= 0; i --) {if (ratings[i] > ratings[i + 1]) {candys[i] = max(candys[i], candys[i + 1] +  1);} }int result = 0;for (int candy:candys) {result += candy;}return result;}
};

三、860. 柠檬水找零

题目链接
文章讲解
视频讲解

思路:
记录拿到的5美金,10美金的张数。分三种情况处理:
1.收到5美金,直接5美金数量+1;
2.收到10美金,10美金数量+1,5美金数量-1;
3.收到20美金,优先找一张10美金和5美金;当没有10美金时,找3张5美金。

代码如下:

    class Solution {public:bool lemonadeChange(vector<int>& bills) {int num5 = 0;int num10 = 0;for (int i = 0; i < bills.size(); i++) {if (bills[i] == 5) num5++; //5美金++else if (bills[i] == 10) { //找5美金,10美金++num5--;num10++;}else { //20美金if (num10) { //优先给一张10美金和一张5美金num10--;num5--;} else { //不够的话就用3张5美金num5 -= 3;}}if (num5 < 0) return false;  //5美金不够}return true;}};

四、406.根据身高重建队列

题目链接
文章讲解
视频讲解

思路:
跟135. 分发糖果 一样,本题也需要考虑两个情况,身高和排在前面的人数。
那么先试试,先按其中一个元素来排序。

  1. 如果按照k来从小到大排序,排完之后,会发现k的排列并不符合条件,身高也不符合条件,两个维度哪一个都没确定下来。
  2. 如果按身高h来排序,身高一定是从大到小排(身高相同的话则k小的站前面),让高个子在前面。
  3. 那么此时优先按身高高的people的k来插入,后序插入节点也不会影响前面已经插入的节点,最终按照k的规则完成了队列。
    在这里插入图片描述

vector版

代码如下:

class Solution {
public://people[i] = [hi, ki]//按身高从高到低排列,身高相等时,k值小的排前面static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);vector<vector<int>> result;for (int i = 0; i < people.size(); i++) {int pos = people[i][1]; //获取people[i]的k值result.insert(result.begin() + pos, people[i]); //按照k值插入到结果集中}return result;}
};

list版

因为vector是动态数组,在插入的时候会触发扩容,且数组的插入效率低。而list底层是链表,插入的效率高得多。
但是需要注意的是vector是连续内存,所以可以用vector.begin()+pos的方式直接插入。
而链表不是连续内存,所以只能通过迭代器it++的形式找到要插入的位置再调用insert插入。

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);list<vector<int>> result; //list底层是链表实现,插入效率比vector高得多for (int i = 0; i < people.size(); i++) {int pos = people[i][1];auto it = result.begin(); //list<vector<int>> iterator it = result.begin();while (pos--) { //寻找插入位置it++;}result.insert(it, people[i]);}    return vector<vector<int>>(result.begin(), result.end());}
};

总结

贪心算法第三天,当遇到需要考虑两个维度的条件时,先处理好其中一个条件,再处理另一个条件。

明天继续加油!

相关文章:

代码随想录算法训练营day29

代码随想录算法训练营 —day29 文章目录 代码随想录算法训练营前言一、134. 加油站暴力解法贪心算法 二、135. 分发糖果三、860. 柠檬水找零四、406.根据身高重建队列vector版list版 总结 前言 今天是算法营的第29天&#xff0c;希望自己能够坚持下来&#xff01; 今日任务&a…...

android studio根据包名获取当前安装包信息

package com.example.myapplication2;import android.content.Context; import android.content.pm.PackageInfo; import android.content.pm.PackageManager; import android.util.Log;/**** 获取版本信息*/ public class SystemHelper {/*** 获取本地软件版本号*/public stat…...

学习第六十五行

仔细观察键盘&#xff0c;会发现一个$符号&#xff0c;其实是有含义的。 在 shell 脚本中&#xff0c;美元符号 $ 有几种重要的含义&#xff1a; 变量引用&#xff1a;$ 用于引用变量的值。例如&#xff0c;如果你有一个变量 name&#xff0c;可以通过 $name 来获取它的值。 n…...

零碎的知识点(七):线性二次调节器(LQR)是什么?

线性二次调节器&#xff08;LQR&#xff09;是什么&#xff1f; 1. LQR的定义与目标2. LQR的原理性能指标 J J J最优解的计算控制律 3. LQR的性质4. 举例说明问题描述解步骤仿真结果 5. 实际应用总结 线性二次调节器&#xff08;LQR&#xff09; 是一种经典的最优控制方法&…...

Matlab一些使用技巧

代码分段 两个百分号就可以实现代码的分段&#xff0c;不同段之间会以不同的背景色显示&#xff0c;方便调试 如下&#xff1a; %% 腐蚀 stlen TimeWidth*Fs/50; %线性算子的长度&#xff0c;1/100的脉宽&#xff0c;对应0.5us&#xff0c;15个采样点 stlen 100; SE strel…...

Linux 发行版介绍与对比:Red Hat、Ubuntu、Kylin、Debian

Linux 操作系统有众多发行版&#xff08;Distros&#xff09;&#xff0c;每个发行版的设计目标、目标用户、应用场景和使用方式有所不同。常见的 Linux 发行版包括 Red Hat、Ubuntu、Kylin 和 Debian。以下是这些发行版的详细介绍与对比&#xff0c;以及它们的应用场景和使用方…...

从CentOS到龙蜥:企业级Linux迁移实践记录(龙蜥开局)

引言&#xff1a; 在我们之前的文章中&#xff0c;我们详细探讨了从CentOS迁移到龙蜥操作系统的基本过程和考虑因素。今天&#xff0c;我们将继续这个系列&#xff0c;重点关注龙蜥系统的实际应用——特别是常用软件的安装和配置。 龙蜥操作系统&#xff08;OpenAnolis&#…...

java1-相对路径与绝对路径

注意注意~开始新部分啦! 开始正式分享java前,先为大家分享一下一个常用的概念---文件的相对路径与绝对路径. 开篇明义: 相对路径是指一个文件或目录相对于当前工作目录的路径。相对路径不包含根目录&#xff0c;而是从当前目录开始计算。 绝对路径是指一个文件或目录从根目录…...

iChainfo 品牌升級為 ichaingo,打造 Web3 數據基礎設施新標杆

Web3 數據基礎設施服務商 iChainfo 今⽇正式宣佈&#xff0c;全新名稱 「ichaingo」 重磅登場&#xff0c;新的官⽅網站 ichaingo.com 正式上線。此次品牌升級基於 Web3 ⾏業的發展趨勢和公司⾃⾝的戰略布局&#xff0c;旨在為全 球⽤戶提供更準確、即時、全⾯、深⼊的 Web3 數…...

Flink概念知识讲解之:Restart重启策略配置

Flink概念知识讲解之&#xff1a;Restart重启策略配置 当 Task 发生故障时&#xff0c;Flink 需要重启出错的 Task 以及其他受到影响的 Task &#xff0c;以使得作业恢复到正常执行状态。 Flink 通过重启策略和故障恢复策略来控制 Task 重启&#xff1a;重启策略决定是否可以…...

[java基础-集合篇]LinkedList源码粗析

LinkedList 的数据结构 实现List、Deque 接口&#xff0c;基于 双向链表实现的列表。与基于数组的 ArrayList 不同&#xff0c;基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。 Java中LinkedList实现了Deque&#xff0c;它提供了 add, offer, remove, poll, …...

面试:C++类成员初始化顺序

1、非静态数据成员&#xff1a;按它们在类定义的声明顺序初始化&#xff0c;不会按它们在初始化列表的顺序。 2、静态数据成员&#xff1a;在main函数启动之前&#xff0c;并且只初始化一次 3、基类构造函数&#xff1a;如果类从一个或多个基类继承而来&#xff0c;基类的构造…...

【Python】Python与C的区别

文章目录 语句结束符代码块表示变量声明函数定义注释格式Python的标识符数据输入input()函数数据输出print()函数 语句结束符 C 语言 C 语言中每条语句必须以分号;结束。例如&#xff0c;int a 10;、printf("Hello, World!");。分号是语句的一部分&#xff0c;用于…...

[开源]自动化定位建图系统(视频)

系统状态机&#xff1a; 效果展示&#xff1a; 1、 机器人建图定位系统-基础重定位&#xff0c;定位功能演示 2、 机器人建图定位系统-增量地图构建&#xff0c;手动回环检测演示 3、… 开源链接&#xff1a; https://gitee.com/li-wenhao-lwh/lifelong-backend Qt人机交互…...

ISP流程--去马赛克详解

前言 本期我们将深入讨论ISP流程中的去马赛克处理。我们熟知&#xff0c;彩色图像由一个个像元组成&#xff0c;每个像元又由红、绿、蓝&#xff08;RGB&#xff09;三通道构成。而相机传感器只能感知光的强度&#xff0c;无法直接感知光谱信息&#xff0c;即只有亮暗而没有颜色…...

Objective-C语言的软件工程

Objective-C语言的软件工程探讨 引言 在软件工程的领域中&#xff0c;编程语言的选择是至关重要的。Objective-C&#xff0c;作为一种为苹果公司的macOS和iOS操作系统而开发的编程语言&#xff0c;凭借其灵活性和强大的功能被广泛应用于应用开发。然而&#xff0c;随着Swift等…...

Objective-C语言的语法糖

Objective-C语言的语法糖探秘 在编程语言的发展历程中&#xff0c;语法糖&#xff08;Syntactic Sugar&#xff09;是一个颇具趣味性和重要性的概念。它让编程的表达更加简洁直观&#xff0c;同时提高了代码的可读性和可维护性。Objective-C 作为一种面向对象的编程语言&#…...

设计模式中的代理模式

在Java中&#xff0c;代理模式&#xff08;Proxy Pattern&#xff09;可以通过静态代理和动态代理两种主要方式实现。 一、静态代理模式 在编译时就已经确定了代理类和被代理类的关系。 代理类和目标对象通常实现相同的接口或继承相同父类。 缺点是对于每个需要代理的目标对象…...

15个学习Python 的编程游戏网站

从小很多人都会在想&#xff0c;那些枯燥的教学课程要是全部变成游戏就好了&#xff0c;这样的话那期末成绩不得立即起飞了嘛&#xff1f;那对于编程很多人也有这样的想法&#xff0c;边玩边学就好了 这不已经有很多程序员开发了多款边玩边学的编程游戏供大家使用&#xff0c;…...

微信小程序实现拖拽盒子效果

要实现一个当前盒子高度由里面的盒子进行支配高度拖拽的效果 // wxml<view class"exmation-item" wx:elif"{{type4}}"> <view class"exmation-item-drag-box" id"drag-box"> <!-- 内容 --><view class"exm…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...