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

小哆啦解题记:加油站的奇幻冒险

小哆啦解题记:加油站的奇幻冒险

小哆啦开始力扣每日一题的第十三天

https://leetcode.cn/problems/gas-station/description/


在环形道路上,矗立着一串加油站,宛如等待挑战的谜题。这条路上的每个加油站都有一桶汽油,而开车到下一个加油站需要消耗一定的油量。问题是,能否从某个加油站出发,绕环路一周,回到原点?

小哆啦站在第一个加油站,双手叉腰,暗自思忖:“这么多加油站,总有一个是答案!不就是找个起点嘛,我肯定行!”


第一站:暴力出发,初尝苦涩

小哆啦决定从第一个加油站出发,一路尝试。它脑袋一拍,说:“简单!一个一个试,总能找到答案!”

它掏出自己的万能笔记本,开始写下计划:

  • 从加油站 i 出发,模拟行驶,看是否能绕一圈回到原点。
  • 如果油量不足,则换到下一个加油站,继续尝试。
  • 如果尝试了所有加油站都不行,那就返回 -1

于是,小哆啦写下了这段代码:

function canCompleteCircuitBruteForce(gas: number[], cost: number[]): number {const n = gas.length;for (let start = 0; start < n; start++) {let tank = 0;let valid = true;for (let i = 0; i < n; i++) {const current = (start + i) % n;tank += gas[current] - cost[current];if (tank < 0) {valid = false;break;}}if (valid) return start;}return -1;
}

小哆啦模拟了一遍,虽然结果对了,但它累得满头大汗。
“一个个试效率也太低了!”它嘀咕道,“我要找到更快的方法!”

就在这时,小哆啦的朋友,小智从远处走来。他拍了拍小哆啦的肩膀,笑着说:
“笨蛋,暴力试法虽然能解题,但要多聪明些,咱们得用点技巧!”


第二站:小智的点拨,优化路径

小智提了个问题:“你知道,如果所有加油站的油量总和小于总消耗,会发生什么吗?”
小哆啦认真思考了一会儿,回答道:“那肯定跑不完一圈啊!”
小智点点头:“对了!所以,第一步就是计算总油量。如果总油量不够,直接返回 -1,没必要继续试了。”

“可如果总油量够呢?”小哆啦问。
小智笑了笑:“那你还得聪明点儿。注意到没?如果当前油箱的油量在某个加油站变成负的,那从这之前的任何一个加油站出发都没戏。直接从下一个加油站开始试就行了!”

小哆啦恍然大悟:“所以,不需要暴力试法,只要一次遍历就能搞定!”
它重新设计了算法:

  1. totalTank 记录总油量和总消耗的差值。如果最终 totalTank 小于 0,直接返回 -1
  2. currentTank 记录当前油箱的油量。
  3. 遍历每个加油站,如果 currentTank < 0,说明起点无效,更新起点为下一个加油站。

小哆啦写下了优化后的代码:

function canCompleteCircuitOptimized(gas: number[], cost: number[]): number {let totalTank = 0; // 总油量let currentTank = 0; // 当前油量let startStation = 0; // 起始加油站for (let i = 0; i < gas.length; i++) {totalTank += gas[i] - cost[i];currentTank += gas[i] - cost[i];if (currentTank < 0) {startStation = i + 1;currentTank = 0;}}return totalTank >= 0 ? startStation : -1;
}

小哆啦运行代码,果然比之前快了很多,它开心地拍手大笑:“小智果然厉害!”


终点:智慧的结晶

小哆啦和小智站在环形路的终点,看着一路解题的过程。
小智问:“现在你明白了吗?解题最重要的是理解本质,不一定非要用蛮力。”
小哆啦点点头,笑着总结:

  • 暴力法:虽然简单,但效率低,适合小规模问题。
  • 优化法:从全局思维入手,利用规律筛选不可能的起点,大幅提升效率。

它拍了拍小智的肩膀,笑道:“下次再遇到这样的题,我肯定会用聪明的办法!”
小智笑着回应:“有你这份心,编程的路一定越走越宽!”

两人沿着环路继续前行,向着下一个谜题进发。

相关文章:

小哆啦解题记:加油站的奇幻冒险

小哆啦解题记&#xff1a;加油站的奇幻冒险 小哆啦开始力扣每日一题的第十三天 https://leetcode.cn/problems/gas-station/description/ 在环形道路上&#xff0c;矗立着一串加油站&#xff0c;宛如等待挑战的谜题。这条路上的每个加油站都有一桶汽油&#xff0c;而开车到下一…...

【前端】CSS实战之音乐播放器

目录 播放器背景旋转音乐封面按钮进度条音量调节音乐信息按钮的效果JavaScript部分播放和暂停音乐切换音乐信息进度条 音量调节避免拖拽时的杂音音量调节条静音和解除静音 自动下一首实现一个小效果最终效果 播放器背景 <div class"play_box"></div>设置…...

Games104——渲染中光和材质的数学魔法

原文链接 渲染方程及挑战 挑战 对于任一给定方向如何获得radiance–阴影 对于光源和表面shading的积分运算&#xff08;蒙特卡洛积分&#xff09; 对于反射光多Bounce的无限递归计算 基础光照解决方案 Blinn-Phong模型&#xff1a; 简化阴影 最常见的处理方式就是Shadow M…...

impala增加字段,hsql查不到数据

impala增加字段&#xff0c;插入数据后直接查看文件有值&#xff0c;impala查询是有值的&#xff0c;但是hsq查出来就没有值&#xff01; Parquet格式的表&#xff0c;在重命名表的列名&#xff0c;或新增列名后&#xff0c;查询重名的列数据时显示当前列所有值为NULL。 原因&a…...

SpringBoot项目中的异常处理

定义错误页面 SpringBoot 默认的处理异常的机制&#xff1a;SpringBoot 默认的已经提供了一套处理异常的机制。一旦程序中出现了异常 SpringBoot 会像/error 的 url 发送请求。在 springBoot 中提供了一个叫 BasicExceptionController 来处理/error 请求&#xff0c;然后跳转到…...

ComfyUI实现老照片修复——AI修复老照片(ComfyUI-ReActor / ReSwapper)尚待完善

AI修复老照片&#xff0c;试试吧&#xff0c;不一定好~~哈哈 2023年4月曾用过ComfyUI&#xff0c;当时就感慨这个工具和虚幻的蓝图很像&#xff0c;以后肯定是专业人玩的。 2024年我写代码去了&#xff0c;AI做图没太关注&#xff0c;没想到&#xff0c;现在ComfyUI真的变成了工…...

NLTK命名实体识别(NER)

命名实体识别(Named Entity Recognition, NER)是自然语言处理(NLP)中的一项核心技术,旨在从文本中识别出具有特定意义的实体,如人名、地名、组织名等。通过对文本的自动化处理,NER能够帮助计算机理解和组织大量的非结构化数据,为信息抽取、搜索引擎优化、数据分析等领域…...

【游戏设计原理】78 - 持续注意力

这个原理指出&#xff0c;人类的注意力通常只能维持7至10分钟&#xff0c;因此游戏设计需要根据这一规律进行优化。具体建议包括&#xff1a; 短时间段设计&#xff1a;将游戏体验分解成7到10分钟的任务或场景&#xff0c;以符合玩家的注意力节奏。引入新刺激&#xff1a;在注…...

Android设备:Linux远程lldb调试

更多内容&#xff1a;XiaoJ的知识星球 目录 一、环境准备1.1 安装llvm/NDK1.2 开启lldb-server服务1.3 lldb连接lldb-server 二、使用lldb调试Android native源码2.1 运行调试2.2 .lldbinit文件 下面介绍Android设备&#xff08;Android手机为例&#xff09;&#xff0c;在Linu…...

多层 RNN原理以及实现

数学原理 多层 RNN 的核心思想是堆叠多个 RNN 层&#xff0c;每一层的输出作为下一层的输入&#xff0c;从而逐层提取更高层次的抽象特征。 1. 单层 RNN 的数学表示 首先&#xff0c;单层 RNN 的计算过程如下。对于一个时间步 t t t&#xff0c;单层 RNN 的隐藏状态 h t h_t…...

[Computer Vision]实验三:图像拼接

目录 一、实验内容 二、实验过程及结果 2.1 单应性变换 2.2 RANSAC算法 三、实验小结 一、实验内容 理解单应性变换中各种变换的原理&#xff08;自由度&#xff09;&#xff0c;并实现图像平移、旋转、仿射变换等操作&#xff0c;输出对应的单应性矩阵。利用RANSAC算法优…...

【Vim Masterclass 笔记22】S09L40 + L41:同步练习11:Vim 的配置与 vimrc 文件的相关操作(含点评课内容)

文章目录 S09L40 Exercise 11 - Vim Settings and the Vimrc File1 训练目标2 操作指令2.1. 打开 vimrc-sample 文件2.2. 尝试各种选项与设置2.3. 将更改内容保存到 vimrc-sample 文件2.4. 将文件 vimrc-sample 的内容复制到寄存器2.5. 创建专属 vimrc 文件2.6. 对于 Mac、Linu…...

5.9 洞察 OpenAI - Translator:日志(Logger)模块的 “时光记录仪”

洞察 OpenAI - Translator:日志(Logger)模块的 “时光记录仪” 在开发和生产环境中,日志记录是确保应用程序正常运行和快速调试的核心机制之一。日志模块(Logger)用于记录应用程序的运行信息,包括错误、警告、调试信息、信息性事件等。通过日志,开发者可以实时监控程序…...

客户案例:电商平台对帐-账单管理(亚马逊amazon)

账单管理&#xff1a; 功能定义&#xff1a; 账单管理用于上传亚马逊&#xff08;amazon&#xff09;平台下载的原始账单数据&#xff0c;美国站、日本站、墨西哥站等账单模板直接进行数据上传&#xff0c;做到0调整&#xff0c;下载下来的账单数据无缝上传至对账平台-账单管…...

IP协议特性

在网络层中&#xff0c;最重要的协议就是IP协议&#xff0c;IP协议也有两个特性&#xff0c;即地址管理和路由选择。 1、地址管理 由于IPv4地址为4个字节&#xff0c;所以最多可以支持42亿个地址&#xff0c;但在现在&#xff0c;42亿明显不够用了。这就衍生出下面几个机制。…...

Kubernetes入门学习

kubernetes技术架构模型 一、kubernetes的Label标签 1.标签是以keyvalue的格式通过用户自定义指定&#xff0c;目的是将其加入到各种资源对象上来实现多维度的资源分组管理使其更方便的进行资源分配、调度、配置和部署管理工作。 2.标签可以结合Label Selector(标签选择器)查询…...

支持向量机SVM的应用案例

支持向量机&#xff08;Support Vector Machine,SVM&#xff09;是一种强大的监督学习算法&#xff0c;广泛应用于分类和回归任务。 基本原理 SVM的主要目标是周到一个最优的超平面&#xff0c;该超平面能够将不同类别的数据点尽可能分开&#xff0c;并且使离该超平面最近的数…...

Chrome 132 版本新特性

Chrome 132 版本新特性 一、Chrome 132 版本浏览器更新 1. 在 iOS 上使用 Google Lens 搜索 在 Chrome 132 版本中&#xff0c;开始在所有平台上推出这一功能。 1.1. 更新版本&#xff1a; Chrome 126 在 ChromeOS、Linux、Mac、Windows 上&#xff1a;在 1% 的稳定版用户…...

(5)STM32 USB设备开发-USB键盘

讲解视频&#xff1a;2、USB键盘-下_哔哩哔哩_bilibili 例程&#xff1a;STM32USBdevice: 基于STM32的USB设备例子程序 - Gitee.com 本篇为使用使用STM32模拟USB键盘的例程&#xff0c;没有知识&#xff0c;全是实操&#xff0c;按照步骤就能获得一个STM32的USB键盘。本例子是…...

Linux 系统服务开机自启动指导手册

一、引言 在 Linux 系统中&#xff0c;设置服务开机自启动是常见的系统配置任务。本文档详细介绍了多种实现服务开机自启动的方法&#xff0c;包括 systemctl 方式、通用脚本方式、crontab 方案等&#xff0c;并提供了生产环境下的方案建议和开机启动脚本示例。 二、systemct…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...