【Day25 LeetCode】贪心Ⅲ
一、贪心Ⅲ
1、加油站 134
这道题直接想法是采用二重循环暴力搜索,简单粗暴但是会超时,是因为以每个点为起点最坏的情况可能都要遍历完全部的序列,有大量重复的操作,那有没有优化的地方呢?有一个结论:如果以 i i i位置出发最远可达 j j j位置,那么在在这段区间里的任意一点出发都不可能达到比 j j j位置更远的地方。反证法可以得出。可以通过这个结论避免大量重复搜索,每个位置只会经过一次。
代码如下:
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size(), s = 0;for(int i=0; i<n; ++i){s = gas[i] - cost[i];int j = (i + 1) % n;while(s >= 0 && i != j){s += gas[j] - cost[j];j = (j + 1) % n;}if(j==i && s >= 0)return i;if(j <= i)return -1;i = j - 1;}return -1;}
};
2、分发糖果 135
分发糖果需要满足其左右孩子的评分高低,直接想着满足两边的条件比较困难,可以先满足一边的条件,在此基础上再满足另一边的条件。
先满足与左边孩子的条件,从前往后看,如果当前孩子评分高于左孩子,则当前孩子的糖果是左孩子的糖果数加1,如果不高于,则给最少的糖果,1个。
在此基础上,再去从后往前看每个孩子的右孩子,如果当前孩子评分高于右孩子,则 当前孩子糖果是在已有糖果 和 右孩子糖果+1之间取最大值,这样可以满足左右孩子两个条件。
代码如下:
class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> ans(n, 1);// 从前往后for(int i=1; i<n; ++i)if(ratings[i] > ratings[i-1])ans[i] = ans[i-1] + 1;// 从后往前int s = ans[n-1];for(int i=n-2; i>=0; --i){if(ratings[i] > ratings[i+1])ans[i] = max(ans[i], ans[i+1] + 1);s += ans[i];}return s;}
};
3、柠檬水找零 860
这题逻辑比较清楚,10美元只能用5美元找零,20美元可以用3个5美元 或者 1个5美元1个10美元找零。但10美元只能用于20美元找零,5美元可用于10、20美元找零,用处更多,所以应该优先使用10美元5美元去找零20美元,如果没有10美元再全用5美元找零。
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int num_5 = 0, num_10 = 0; // 5/10美元数量for(int bill : bills){switch(bill){case 5:num_5++;break;case 10:{num_5--;num_10++;break;}case 20:{// 优先使用10美元if(num_10 > 0)num_10--;elsenum_5 -= 2;num_5--;}}if(num_10 < 0 || num_5 < 0)return false;}return true;}
};
4、根据身高重建队列 406
有两个元素,一个是身高h,一个是前面不小于当前高度的人数k。可以先按考虑按身高h排序,确定之后再按 k进行插入
class Solution {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];}
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);vector<vector<int>> ans;for(auto p : people)ans.insert(ans.begin()+p[1], p);return ans;}
};
二、写在后面
加油站这题比较巧妙,如果能想到那个结论就很容易进行优化。分发糖果和根据身高重建队列这题主要是当需要满足两边条件时,同时兼顾两边处理起来麻烦, 可以先处理一边,再处理另一边。
相关文章:
【Day25 LeetCode】贪心Ⅲ
一、贪心Ⅲ 1、加油站 134 这道题直接想法是采用二重循环暴力搜索,简单粗暴但是会超时,是因为以每个点为起点最坏的情况可能都要遍历完全部的序列,有大量重复的操作,那有没有优化的地方呢?有一个结论:如果…...
蓝桥杯练习日常|递归-进制转换
未完待续,,,,,, 目录 蓝桥云课760数的计算 一、递归 题目: 我的解题代码: 二、进制转换 任意进制转十进制: 十进制转换为其他进制: 进制蓝桥杯题目…...
AI Agent:深度解析与未来展望
一、AI Agent的前世:从概念到萌芽 (一)早期探索 AI Agent的概念可以追溯到20世纪50年代,早期的AI研究主要集中在简单的规则系统上,这些系统的行为是确定性的,输出由输入决定。随着时间的推移,…...
《SwinIR:使用Swin-Transformer图像恢复》学习笔记
paper:2108.10257 GitHub:GitHub - JingyunLiang/SwinIR: SwinIR: 使用 Swin Transformer 进行图像修复 (官方仓库) 目录 摘要 1、Introduction 2、Related Work 2.1 图像修复 2.2 视觉Transformer…...
如何在Nginx服务器上配置访问静态文件目录并提供文件下载功能
引言 在搭建网站的过程中,我们经常需要让访客通过URL直接访问或下载存储在服务器特定目录下的静态文件。本文将详细介绍如何在Nginx服务器环境中配置一个名为"download"的文件目录,以便用户能够通过浏览器访问并下载其中的手册和其他文档。 …...
ansible自动化运维实战--script、unarchive和shell模块(6)
文章目录 一、script模块1.1、功能1.2、常用参数1.3、举例 二、unarchive模块2.1、功能2.2、常用参数2.3、举例 三、shell模块3.1、功能3.2、常用参数3.3、举例 一、script模块 1.1、功能 Ansible 的 script 模块允许你在远程主机上运行本地的脚本文件,其提供了一…...
理解深度学习pytorch框架中的线性层
文章目录 1. 数学角度: y W x b \displaystyle y W\,x b yWxb示例 2. 编程实现角度: y x W T b \displaystyle y x\,W^T b yxWTb3. 常见错误与易混点解析4. 小结参考链接 在神经网络或机器学习的线性层(Linear Layer / Fully Connect…...
电路研究9.2——合宙Air780EP使用AT指令
这里正式研究AT指令的学习了,之前只是接触的AT指令,这里则是深入分析AT指令了。 软件的开发方式: AT:MCU 做主控,MCU 发 AT 命令给模组的开发方式,模组仅提供标准的 AT 固件, 所有的业务控制逻辑…...
Qt数据库相关操作
目录 一、前言 二、类与接口介绍 1.连接管理类 2.数据操作类 3.数据模型类 4.其它类 三、主要操作流程 1.示例 2.绑定参数 3.事务操作 一、前言 要在Qt中操作数据库,首先要安装对应的数据库,还要确保安装了Qt SQL模块。使用MySQL时࿰…...
2025-01-22 Unity Editor 1 —— MenuItem 入门
文章目录 1 Editor 文件夹2 MenuItem3 使用示例3.1 打开网址3.2 打开文件夹3.3 Menu Toggle3.4 Menu 代码复用3.5 MenuItem 激活与失活4 代码示例 1 Editor 文件夹 Editor 文件夹是 Unity 中的特殊文件夹,Unity 中所有编辑器相关的脚本都需要放置在其中…...
解锁C#编程新姿势:Z.ExtensionMethods入门秘籍
一、引言 在 C# 的开发旅程中,我们常常会遇到各种重复性高、复杂度低的任务,这些任务虽然基础,但却占据了我们大量的开发时间。比如处理字符串时,经常需要进行非空判断、格式转换;操作日期时间时,计算某个…...
不使用 JS 纯 CSS 获取屏幕宽高
前言 在现代前端开发中,获取屏幕的宽度和高度通常依赖于 JavaScript。然而现代 CSS 也可以获取到屏幕的宽高,通过自定义属性(CSS Variables)和一些数学函数来实现这一目标。本文将详细解析如何使用 CSS 的 property 规则和一些数…...
Node.js NativeAddon 构建工具:node-gyp 安装与配置完全指南
Node.js NativeAddon 构建工具:node-gyp 安装与配置完全指南 node-gyp Node.js native addon build tool [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/no/node-gyp 项目基础介绍及主要编程语言 Node.js NativeAddon 构建工具(node-gyp…...
【ARTS】【LeetCode-704】二分查找算法
目录 前言 什么是ARTS? 算法 力扣704题 二分查找 基本思想: 二分查找算法(递归的方式): 经典写法(找单值): 代码分析: 经典写法(找数组即多个返回值) 代码分析 经典题目 题目描述: 官方题解 深入思考 模版一 (相错终止/左闭右闭) 相等返回情形…...
Vue.js 配置路由:基本的路由匹配
Vue.js 配置路由:基本的路由匹配 在 Vue.js 应用中,Vue Router 是官方提供的路由管理器,用于在单页应用(SPA)中管理不同的视图。通过配置路由,应用可以根据 URL 的变化展示相应的组件。 基本的路由匹配是…...
鸿蒙(HarmonyOS)Json格式转实体对象(2)
下面是一个复杂的json体。 怎么把json转实体类,首先要定义类 import List from ohos.util.List export class InfoModel{msg: stringcars: List<Cars>code: numberpermissions: List<string>roles: List<string>user: User}class Cars{createBy:…...
代码随想录 栈与队列 test 6
239. 滑动窗口最大值 - 力扣(LeetCode) 每次只取窗口中最大值,这个最大值可能在后面的滑动中保持不变,而比最大值小的值且在最大值之前出现的值没必要保留,因此可以通过单调队列利用这个特性。 这个单调队列具有如下…...
动手学深度学习2025.1.23
一、预备知识 1.数据操作 (1)数据访问: 一个元素:[1,2] //行下标为1,列下标为2的元素 一行元素:[1,:] //行下标为1的所有元素 一列元素:[:,1] //列下标为1的所有元素 子区域:[…...
生存网络与mlr3proba
在R语言中,mlr3包是一个用于机器学习的强大工具包。它提供了一种简单且灵活的方式来执行超参数调整。 生存网络是一种用于生存分析的模型,常用在医学和生物学领域。生存分析是一种统计方法,用于研究事件发生的时间和相关因素对事件发生的影响。生存网络可以用来预测个体在给…...
C#与AI的共同发展
C#与人工智能(AI)的共同发展反映了编程语言随着技术进步而演变,以适应新的挑战和需要。自2000年微软推出C#以来,这门语言经历了多次迭代,不仅成为了.NET平台的主要编程语言之一,还逐渐成为构建各种类型应用程序的强大工具。随着时…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
算法250609 高精度
加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...
欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!
多连接 BLE 怎么设计服务不会乱?分层思维来救场! 作者按: 你是不是也遇到过 BLE 多连接时,调试现场像网吧“掉线风暴”? 温度传感器连上了,心率带丢了;一边 OTA 更新,一边通知卡壳。…...
