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

算法训练(leetcode)二刷第二十五天 | *134. 加油站、*135. 分发糖果、860. 柠檬水找零、*406. 根据身高重建队列

刷题记录

  • *134. 加油站
  • *135. 分发糖果
  • 860. 柠檬水找零
  • *406. 根据身高重建队列

*134. 加油站

leetcode题目地址

当前站点可以剩余油量=gas[i] - cost[i];
将每站的剩余油量求和计算累计剩余油量,总剩余油量小于0,则无法行驶一周。
若在到达某一站时累计剩余油量为负时,则起始位置为i+1。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

// java
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;int totalSum = 0;int start = 0;for(int i=0; i<gas.length; i++){curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if(curSum < 0){curSum = 0;start = i+1;}}if(totalSum<0) return -1;return start;}
}

*135. 分发糖果

leetcode题目地址

需要从左右两侧分别考虑而不是同时考虑。
额外开辟一个数组记录每个人的糖果数。

先从左向右查看右侧比左侧大的赋值比左侧的糖果多1。
再从右向左查看左侧比右侧大的赋值比右侧的糖果多1。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

// java
class Solution {public int candy(int[] ratings) {int[] candies = new int[ratings.length];Arrays.fill(candies, 1);for(int i=1; i<ratings.length; i++){if(ratings[i]>ratings[i-1]) candies[i] = candies[i-1]+1;}int sum = candies[ratings.length-1];for(int i=ratings.length-2; i>=0; i--){if(ratings[i]>ratings[i+1]) candies[i] = Math.max(candies[i+1]+1, candies[i]);sum += candies[i];}return sum;}
}

860. 柠檬水找零

leetcode题目地址

题目要求是立即为顾客找零,不可以等待。也就是说只能第一个顾客收5元第二个收10元,不允许第一个收10元第二个收5元。

因此只需要分别记录三种面值的数量,在收到一份钱后立刻找零,若某种面值出现负值,则说明找不开,返回false。若全程没有出现负值,则在最后返回true。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

// java
class Solution {public boolean lemonadeChange(int[] bills) {int five=0, ten=0, twenty=0;for(int i=0; i<bills.length; i++){if(bills[i] == 5) five++;else if(bills[i] == 10) {five--;ten++;}else{if(ten>0){ten--;five--;}else{five-=3;}twenty++;}if(five<0 || ten<0 || twenty<0) return false;}return true;}
}

*406. 根据身高重建队列

leetcode题目地址

共有两个维度,h和k,分两次考虑,先考虑身高,对其由高向低排序,再考虑k,对其由小到大排序。

排序操作O(nlogn),单元素插入指定位置操作O(n),n个元素O(n2)。

时间复杂度: O ( n l o g n + n 2 ) O(nlogn+n^2) O(nlogn+n2)
空间复杂度: O ( n ) O(n) O(n)

// java
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) -> {if(a[0] == b[0]) return a[1]-b[1];return b[0]-a[0];});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people){// 将元素p插入p[1]位置que.add(p[1], p);}return que.toArray(new int[people.length][]);}
}

相关文章:

算法训练(leetcode)二刷第二十五天 | *134. 加油站、*135. 分发糖果、860. 柠檬水找零、*406. 根据身高重建队列

刷题记录 *134. 加油站*135. 分发糖果860. 柠檬水找零*406. 根据身高重建队列 *134. 加油站 leetcode题目地址 当前站点可以剩余油量gas[i] - cost[i]; 将每站的剩余油量求和计算累计剩余油量&#xff0c;总剩余油量小于0&#xff0c;则无法行驶一周。 若在到达某一站时累计剩…...

Springboot 整合 itext 实现PDF文件合并,识别图片则转成PDF拼接

目录 前言一、引用依赖二、使用步骤1.Controller2.Service接口3.实现类三、请求接口及结果前言 本文实现 Springboot 整合 itext 实现PDF文件合并,图片转PDF拼接。 一、引用依赖 <dependency><groupId>com.itextpdf</groupId><artifactId>itext7-co…...

TypeScript 中的 ! 和 ? 操作符

在 TypeScript 中&#xff0c;! 和 ? 是两个非常重要且常用的操作符&#xff0c;分别用于非空断言和可选链操作。下面简单介绍一下二者。 1. 非空断言操作符 ! 1.1 含义 非空断言操作符 !&#xff08;Non-null assertion operator&#xff09;用来告诉 TypeScript 编译器&a…...

开源三代示波器的高速波形刷新方案开源,支持VNC远程桌面,手机,Pad,电脑均可访问(2024-11-11)

说明&#xff1a; 1、本来这段时间是一年一度Hackaday硬件设计开源盛宴&#xff0c;但hackaday电子大赛在去年终结了。所以我开源个我的吧。 2、三代示波器的高速波形刷新方案&#xff0c;前两年就做好了&#xff0c;这两年忙H7-TOOL的更新比较多&#xff0c;三代示波器的更新…...

谷歌推出设备内置人工智能,实时向手机用户发出诈骗电话警报

Google 宣布推出适用于 Android 的新安全功能&#xff0c;可实时防御诈骗和有害应用。 这些功能由先进的设备内置 AI 提供支持&#xff0c;可在不损害隐私的情况下增强用户安全性。 这些新的安全功能首先在 Pixel 上推出&#xff0c;并将很快在更多 Android 设备上推出。 诈…...

AI换人脸facefusion项目口型同步‌API化改造及部署

一. 简介 ‌FaceFusion‌是一款强大的AI换脸软件&#xff0c;它支持图片、视频以及直播换脸&#xff0c;官方将其称为“下一代脸部交换器和增强器”。FaceFusion的最新版本为2.6.1&#xff0c;这个版本在原有基础上增加了更多的模型和高清算法&#xff0c;显著提升了图片和视频…...

移动端问题

这里只是做一个记录&#xff0c;不一定大家都会有问题&#xff0c;参考就行 一、页面回弹 苹果有&#xff0c;安卓没有 解决&#xff1a;pages.json下 app-plus { bounce: none} 关闭回弹效果 二、onreachBottom触底生命周期&#xff0c;ios无法触发 修改触底数值&#xff1a…...

Linux网络——网络初识

目录 1. 认识协议 2. 协议的分层 3. OSI 七层模型 && TCP/IP 五层(四层)模型 4. 网络传输的基本流程 5. 以太网的通信原理 6. 数据的跨网络传播 7. 认识 IP 地址 ① IP 是什么 ② IP 与 MAC 的关系 ③ 为什么需要 IP 在谈及网络之前&#xff0c;我们要先对学…...

从华为到创业公司

我有一个朋友&#xff0c;在华为工作了很长一段时间&#xff0c;一年多前&#xff0c;他从华为出来到了一家创业公司。 周末趁着有时间&#xff0c;我跟他聊了下关于从华为到创业公司的一些问题&#xff0c;总结给大伙看看。 ▎1 在华为工作和在创业公司工作最大的差别是什么呢…...

Vue 组件通信及进阶语法

文章目录 一、scoped 样式冲突二、data 是一个函数三、组件通信1. 父子通信1.1 props 校验1.2 props 比较 data 2. 非父子通信2.1 event bus2.2 provide-inject 四、进阶语法1. v-model 详解2. sync 修饰符3. ref 和 $refs4. $nextTick 一、scoped 样式冲突 注意点&#xff1a;…...

vue文本高亮处理

在vue的v-for循环中处理搜索关键字高亮问题&#xff0c;通过截取文字判断&#xff0c;分成三段拼接起来 <div class"check-list" v-if"shopList.length >0"><a-checkbox change"onChangeShop($event,item)" :checked"checkedL…...

androidstudio入门到放弃配置

b站视频讲解传送门 android_studio安装包&#xff1a;https://developer.android.google.cn/studio?hlzh-cn 下载安装 开始创建hello-world 1.删除缓存 文件 下载gradle文件压缩&#xff1a;gradle-8.9用自己创建项目时自动生成的版本即可&#xff0c;不用和我一样 https://…...

NLP论文速读(谷歌出品)|缩放LLM推理的自动化过程验证器

论文速读|Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning 论文信息&#xff1a; 简介&#xff1a; 这篇论文探讨了如何提升大型语言模型&#xff08;LLM&#xff09;在多步推理任务中的性能。具体来说&#xff0c;它试图解决的问题是现有的基于结…...

【Linux学习】【Ubuntu入门】1-4 ubuntu终端操作与shell命令1

1.使用快捷键CtrlAltT打开命令终端&#xff0c;或者单击右键点击… 2.常用shell命令 目录信息查看命令&#xff1a;ls ls -a&#xff1a;显示目录所有文件及文件夹&#xff0c;包括隐藏文件&#xff0c;比如以.开头的 ls -l&#xff1a;显示文件的详细信息 ls -al&#xff1…...

【Qt】Qt在窗口中加载Web界面的方法汇总

1、Qt WebEngine 1)Qt版本:Qt5.4以上; 2)平台要求(https://doc.qt.io/archives/qt-5.9/qtwebengine-platform-notes.html): 例如:Windows下只能使用 MSVC 编译器,不支持MinGW编译器,会报错(: error: Unknown module(s) in QT: webenginewidgets) 并且不能用在Qt编…...

Java集合框架之Collection集合遍历

引言 在Java编程中&#xff0c;集合&#xff08;Collection&#xff09;框架是处理对象集合的核心工具。它提供了一套统一的接口和类来存储和操作对象集合。遍历集合是日常开发中的一项基本任务&#xff0c;本文将深入探讨Java Collection集合的遍历方法&#xff0c;并提供实际…...

基于STM32的智能充电桩:集成RTOS、MQTT与SQLite的先进管理系统设计思路

一、项目概述 随着电动车的普及&#xff0c;充电桩作为关键基础设施&#xff0c;其智能化、网络化管理显得尤为重要。本项目旨在基于STM32微控制器开发一款智能充电桩&#xff0c;能够实现高效的充电监控与管理。项目通过物联网技术&#xff0c;提供实时数据监测、远程管理、用…...

windows 查看yolo11 是否安装了cuda

一、通过python查看 import torch print(torch.cuda.is_available()) 二、通过 pip list 查看 在conda环境 可以看出torch 后面是2.1.4 cu124 说明GPU环境安装成功。 如果是cpu环境&#xff0c;则是&#xff1a;...

机器学习【激活函数】

笔记内容侵权联系删 激活函数的概念神经网络中的每个神经元节点接受上一层神经元的输出值作为本神经元的输入值&#xff0c;并将输入值传递给下一层&#xff0c;输入层神经元节点会将输入属性值直接传递给下一层(隐层或输出层)。在多层神经网络中&#xff0c;上层节点的输入在加…...

【OpenEuler】配置虚拟ip

OpenEuler系统手动配置虚ip 介绍操作方法临时生效永久生效 验证 介绍 我们知道通过keepalived服务可以为linux服务器设置虚拟ip&#xff0c;但是有些特殊场景下若无法安装部署keepalived服务&#xff0c;则需要通过手动设置的方式&#xff0c;配置服务器的虚拟ip。 本方案提供…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...