LeetCode加油站(贪心算法/暴力,分析其时间和空间复杂度)


题目描述

 

 一.原本暴力算法

最初的想法是:先比较gas数组和cost数组的大小,找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点,就不能作为起始点)。当找到过后,再去依次顺序跑一圈,如果剩余的油为负数,再去寻找下一个满足条件的起始站点。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int index = -1; //定义初始起点int left = 0; //定义剩余油量bool flag = false;int n = gas.size();//寻找起始位置for(int i = 0;i<n;i++){if(gas[i] < cost[i]) {continue;}else{index = i; int j = index;int count = 0;cout<<"index="<<index<<endl;while(true){j = j%n;cout<<"j="<<j<<endl;if(left < 0) {left = 0;break;}if(count == n){flag = true;return index;}left = left + gas[j] - cost[j];cout<<"left="<<left<<endl;count++;j++;}   }}//判断if(flag){return index;}else{return -1;}}
};

 

但是代码最后超时了!!

时间复杂度是O(N^2) 因为循环遍历寻找起始站点,找到过后再去循环遍历走一圈是O(N^2)的时间复杂度!

巧妙思路算法二能通过的

转子大佬的代码。

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的

  • 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。

  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。

  • class Solution {
    public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX; // 从起点出发,油箱里的油量最小值for (int i = 0; i < gas.size(); i++) {int rest = gas[i] - cost[i];curSum += rest;if (curSum < min) {min = curSum;}}if (curSum < 0) return -1;  // 情况1if (min >= 0) return 0;     // 情况2// 情况3for (int i = gas.size() - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
    };

    在这里时间复杂度O(N)

  • 空间复杂度O(1)没有开辟新的空间

二.贪心算法

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。

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) {   // 当前累加rest[i]和 curSum一旦小于0start = i + 1;  // 起始位置更新为i+1curSum = 0;     // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};

时间复杂度O(N) 

转载于代码随想录,大佬的算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3224543.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

MATLAB备赛资源库(1)建模指令

一、介绍 MATLAB&#xff08;Matrix Laboratory&#xff09;是一种强大的数值计算环境和编程语言&#xff0c;特别设计用于科学计算、数据分析和工程应用。 二、使用 数学建模使用MATLAB通常涉及以下几个方面&#xff1a; 1. **数据处理与预处理**&#xff1a; - 导入和处理…

OpenAI与Thrive Global推出Thrive AI Health:AI驱动的健康教练应用

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

算法金 | 12 个最佳 Python 代码片段,帮我完成工作自动化,香~

​大侠幸会幸会&#xff0c;我是日更万日 算法金&#xff1b;0 基础跨行转算法&#xff0c;国内外多个算法比赛 Top&#xff1b;放弃 BAT Offer&#xff0c;成功上岸 AI 研究院 Leader&#xff1b; Python是一种多功能的编程语言&#xff0c;它提供了各种功能和库来有效地自动化…

更深入了解汽车与航空电子等安全关键型应用的IP核考量因素

作者&#xff1a;Philipp Jacobsohn&#xff0c;SmartDV高级应用工程师 中国已经连续十多年成为全球第一大汽车产销国&#xff0c;智能化也成为了汽车行业发展的一个重要方向&#xff0c;同时越来越多的制造商正在考虑进入无人机和飞行汽车等低空设备&#xff0c;而所有的这些…

语义言语流畅性的功能连接和有效连接

摘要 语义言语流畅性(SVF)受损在多种神经系统疾病中都存在。虽然已经报道了SVF相关区域的激活情况&#xff0c;但这些区域如何相互连接以及它们在脑网络中的功能作用仍存在分歧。本研究使用功能磁共振成像评估了健康被试SVF静态和动态功能连接(FC)以及有效连接。观察到额下回(…

Filter 过滤器

1. 什么是过滤器 拦截不符合过滤要求的请求&#xff0c;使其无法到达目的地。 执行过程 主要用在&#xff1a;统一认证&#xff0c;统一编码设置 2. 创建过滤器 两种方式&#xff1a;与 servlet 雷同 ① 注解方式 &#xff08;/* 拦截所有请求&#xff09; WebFilter(fil…

从数据仓库到数据湖(下):热门的数据湖开源框架

文章目录 一、前言二、Delta Lake三、Apache Hudi四、Apache Iceberg五、Apache Paimon六、对比七、笔者观点八、总结八、参考资料 一、前言 在上一篇从数据仓库到数据湖(上)&#xff1a;数据湖导论文章中&#xff0c;我们简单讲述了数据湖的起源、使用原因及其本质。本篇文章…

【Windows11】Edge卡顿问题精准解决

目录 背景问题解决 背景 本机配置&#xff1a; CPU&#xff1a;i5-13600KF 内存&#xff1a;威刚 XPG龙耀 D300G 32G 6400 D5 固态&#xff1a;威刚 XPG翼龙 S70B 1T PCIe4.0 7400MB/s 带缓存 理论上这个配置多开个Edge轻轻松松。 已经尝试网上各种方法未果&#xff0c;包括不…

【状态估计】非线性非高斯系统的状态估计——离散时间的批量估计

上一篇文章介绍了离散时间的递归估计&#xff0c;本文着重介绍离散时间的批量估计。 上一篇位置&#xff1a;【状态估计】非线性非高斯系统的状态估计——离散时间的递归估计。 离散时间的批量估计问题 最大后验估计 目标函数 利用高斯-牛顿法来解决估计问题的非线性版本&a…

Qt/QML学习-ListView

QML学习 ListView例程视频讲解代码 main.qml import QtQuick 2.15 import QtQuick.Window 2.15 import QtQuick.Controls 2.15Window {id: windowwidth: 640height: 480visible: truetitle: qsTr("ListView")Rectangle {height: listView.heightwidth: listView.wi…

文件操作和IO流(Java版)

前言 我们无时无刻不在操作文件。可以说&#xff0c;我们在电脑上能看到的图片、视频、音频、文档都是一个又一个的文件&#xff0c;我们需要从文件中读取我们需要的数据&#xff0c;将数据运算后也需要将结果写入文件中长期保存。可见文件的重要性&#xff0c;今天我们就来简…

262个地级市-市场潜力指数(do文件+原始文件)

全国262个地级市-市场潜力指数&#xff08;市场潜力计算方法代码数据&#xff09;_市场潜力数据分析资源-CSDN文库 市场潜力指数&#xff1a;洞察未来发展的指南针 市场潜力指数是一个综合性的评估工具&#xff0c;它通过深入分析市场需求、竞争环境、政策支持和技术创新等多个…

2025考研~数据结构试卷

作者主页&#xff1a;知孤云出岫 数据结构试题 [TOC](数据结构试题)数据结构试卷一、选择题&#xff08;每题2分&#xff0c;共20分&#xff09;二、填空题&#xff08;每题3分&#xff0c;共15分&#xff09;三、简答题&#xff08;每题10分&#xff0c;共40分&#xff09;四…

rsync远程同步--累了,明天继续再写~。

rsync官网链接 rsync(Remote Sync,远程同步)开源快速备份工具&#xff0c;是一个用于本地和远程文件同步的Unix-like命令行程序。它使用“快速数据传输算法”&#xff0c;只发送源和目标之间的差异&#xff0c;因此数据传输非常高效。 可以在不同主机之间镜像同步整 个目录树…

图论---哈密顿回路的实现

开始编程前分析设计思路和程序的整体的框架&#xff0c;以及作为数学问题的性质&#xff1a; 设计思路&#xff1a; 利用邻接表存储图的结构&#xff0c;存储对应顶点和边作为无向图存边时正反都进行存储便于寻找路径对顶点的访问和路径走向进行记录使用回溯法&#xff0b;深度…

这不是在搞技术,而是在玩心态~

正文 大家好&#xff0c;我是bug菌~ 如今为制造业提供大型设备的研发型公司大多数都是做系统集成&#xff0c;一部分有技术实力的公司会把核心部分自研&#xff0c;其他相对比较通用的周边设备由其他公司产品来集成&#xff1b;也有一部分公司只是做做方案和资源整合&#xff0…

SSE 和 WebSocket 的区别与选择指南

在构建现代网络应用时&#xff0c;实时通信技术扮演着至关重要的角色。本文将深入讨论 Server-Sent Events (SSE) 和 WebSocket ——两种主要的实时通信技术&#xff0c;对比它们的实现方式、优势和具体用途&#xff0c;以帮助开发人员根据自身项目需求选择合适的技术。 何为 …

常用的设计模式和使用案例汇总

常用的设计模式和使用案例汇总 【一】常用的设计模式介绍【1】设计模式分类【2】软件设计七大原则(OOP原则) 【二】单例模式【1】介绍【2】饿汉式单例【3】懒汉式单例【4】静态内部类单例【5】枚举&#xff08;懒汉式&#xff09; 【三】工厂方法模式【1】简单工厂模式&#xf…

PostgreSQL 中如何实现数据的增量更新和全量更新的平衡?

文章目录 一、增量更新与全量更新的概念增量更新全量更新 二、考虑的因素1. 数据量2. 数据更改的频率和规模3. 数据一致性要求4. 系统性能和资源利用5. 业务逻辑和流程 三、解决方案&#xff08;一&#xff09;混合使用增量更新和全量更新&#xff08;二&#xff09;使用临时表…

未羽研发测试管理平台

突然有一些觉悟&#xff0c;程序猿不能只会吭哧吭哧的低头做事&#xff0c;应该学会怎么去展示自己&#xff0c;怎么去宣传自己&#xff0c;怎么把自己想做的事表述清楚。 于是&#xff0c;这两天一直在整理自己的作品&#xff0c;也为接下来的找工作多做点准备。接下来…